[python] 한 점이 다각형 내부에 위치하는지 판별하기
업데이트:
[머신러닝] 한 점이 다각형 내부에 위치하는지 판별하기
참고링크
참고 링크
1. 서론
이미지 자료를 다루다보면 다각형 내부의 점만 선별해야할 경우가 생깁니다. 오늘은 이 때 사용하는 알고리즘에 대해 알아보겠습니다. 본 포스팅은 Determining if a point lies on the interior of a polygon 을 참고 했습니다.
2. 이미지 데이터에서의 x, y축
우리는 어렸을 때 좌표평면에 대해 배웠습니다.
우리가 어렸을 때 배운 좌표평면은 위와 같이 좌측 하단이 원점이 되고 오른쪽 방향으로 x축, 위쪽 방향으로 y축을 구성합니다. 그리고 좌표를 표현할 때는 x축과 y축 선이 만나는 교차지점이 좌표가 됩니다.
그러나 이미지 데이터를 다룰 때는 조금 다릅니다. 이미지 데이터를 다룰 때는 위 그림과 같이 좌측 상단이 원점이 되고 아래 방향으로 x축, 오른쪽 방향으로 y축을 구성합니다. 또한 좌표를 표현할 떄는 선과 선이 만나는 지점이 아니라 선과 선이 만나서 구성하는 면이 좌표가 됩니다. 이 면(plane)은 흔히 말하는 픽셀(pixel)입니다.
3. 다각형 표현하기
다음은 파이썬으로 다각형을 표현해보겠습니다.
다각형은 위 그림과 같이 리스트 자료형으로 구현할 수 있습니다. 각 꼭지점을 리스트로 담으면 되는데 각 점은 (x좌표, y좌표)로 구성됩니다.
그리고 다각형은 닫힌 형태(closed form)이 되어야하므로 위 그림처럼 리스트 첫 원소와 마지막 원소는 동일해야합니다. 이는 한 붓 그리기를 생각하면 쉽습니다.
그리고 다각형을 구성하는 점을 추출하고 싶다면 위와 같이 리스트의 인덱스를 이용해 추출할 수 있습니다.
4. (기존 좌표평면)특정 좌표가 다각형 내부에 있는지 외부에 있는지 판별
그렇다면 특정 좌표가 다각형 내부에 있는지 외부에 있는지는 어떻게 판별할 수 있을까요? 이는 특정 좌표가 다각형을 구성하는 점들끼리 이은 직선과 x축 방향으로 얼마나 교차하는지 체크하는 방법으로 확인할 수 있습니다.
논문을 보면, 위 그림과 같이 x축 방향으로 직선을 그었을때 다각형을 구성하는 직선과 교차하는지 판별하는 방법으로 내부/외부를 확인할 수 있습니다. 위 그림과 같이 다각형 내부의 점은 x축 방향으로 직선을 그었을때 다각형 직선과 한번 교차하는 것을 알 수 있습니다. 교차하는 횟수를 counter라고 하면 해당 좌표가 다각형 내부에 존재한다면 counter=1인 것입니다.
위 그림을 보면 좌표의 위치에 따른 coutner를 비교할 수 있습니다. counter가 0이라는 말의 의미는 x축 방향으로 선을 그었을때, 아무 직선과 만나지 않는다는 것이고, counter가 2라는 말은 2개의 직선과 만난다는 것입니다. 위 그림을 잘보면 해당 좌표가 다각형 내부에 있다면 counter는 홀수이고, 해당 좌표가 다각형 외부에 있다면 coutner는 짝수 인 것을 알 수 있습니다.
5. (이미지 데이터)특정 좌표가 다각형 내부에 있는지 외부에 있는지 판별
위 그림은 기존 좌표 평면을 고려했을 때이고, 이번에는 이미지 데이터를 고려했을 때, 해당 픽셀이 다각형 내부에 존재하는지 판별하는 방식을 알아보겠습니다.
이미지 데이터는 x축과 y축의 방향이 바뀝니다. x축 방향이 바뀌었으므로 바뀐 x축 방향으로 counter를 체크해야합니다.
6. 알고리즘 생성
앞서 기본적인 판별식을 알아냈으니, 이제 본격적으로 알고리즘을 생성해 보겠습니다.
먼저 가장 첫 조건은 해당 좌표의 y 좌표 값이 기존 다각형 점 2개에 대해 y 좌표의 최소값보다 해당 좌표의 y 좌표값이 큰 지 확인합니다.
그리고 두 번째 조건은 해당 좌표의 y 좌표 값이 기존 다각형 점 2개에 대해 y 좌표의 최대값보다 해당 좌표의 y 좌표값이 작은 지 확인합니다.
그리고 세번째 조건으로 x좌표의 최대값보다 작은지에 대해서도 비교해줍니다. 그리고 마지막 조건으로 파란색 두점의 y 좌표는 서로 달라야합니다. 그 이유는 이후 나올 상세 조건으로 x좌표가 서로 동일하다면 내부의 점으로 취급하기 때문입니다.
우리는 어렸을 때 두 점을 지나는 직선의 방정식을 배웠습니다. 다각형을 이루고 있는 두 점에 대해 직선의 방정식을 구하고 우리가 내/외부를 판별하고 싶은 빨간점의 y좌표를 해당방정식에 넣으면 해당 직선의 방정식 위에 있는 x좌표를 구할 수 있습니다. 이렇게 구한 값을 xinters라고 하겠습니다.
따라서 앞서 구한 xinters에 대해 빨간점의 x좌표값이 xinters보다 작다면 해당 좌표는 다각형 내부에 존재하는 것입니다.
7. 함수 구현
위와 같은 식을 바탕으로 함수로 구현하면 다음과 같습니다.
def inside_or_outside(polygon, point):
"""
한 점(point)이 다각형(polygon)내부에 위치하는지 외부에 위치하는지 판별하는 함수
입력값
polygon -> 다각형을 구성하는 리스트 정보
point -> 판별하고 싶은 점
출력값
내부에 위치하면 res = 1
외부에 위치하면 res = 0
"""
N = len(polygon)-1 # N각형을 의미
counter = 0
p1 = polygon[0]
for i in range(1, N+1):
p2 = polygon[i%N]
if point[1] > min(p1[1], p2[1]) and point[1] <= max(p1[1], p2[1]) and point[0] <= max(p1[0], p2[0]) and p1[1] != p2[1]:
xinters = (point[1]-p1[1])*(p2[0]-p1[0])/(p2[1]-p1[1]) + p1[0]
if(p1[0]==p2[0] or point[0]<=xinters):
counter += 1
p1 = p2
if counter % 2 == 0:
res = 0 # point is outside
else:
res = 1 # point is inside
return res
위 함수에서 보다시피, 해당 좌표가 내부에 있으면 출력값 1을 리턴하고, 해당 좌표가 다각형 외부에 있으면 출력값 0을 리턴합니다. 앞서 만든 함수가 잘 작동하는지 확인하면 다음과 같습니다.
>>> polygon = [[5,4], [10,8], [2,11], [5,4]]
>>> point = [6,7]
>>> inside_or_outside(polygon, point)
1
8. 참고. 다각형 내부 점만 빨간색으로 바꾸는 함수
def polygon_plot(path, wave, polygon):
"""
특정 파장의 이미지에서 다각형 내부에 있는 점들만 빨간색으로 표시해서 plot
이 함수는 시각화 용이고 계산에는 사용되지 않음
"""
img_path = path+'image_0{}_001.png'.format(wave)
img_color = cv2.imread(img_path, cv2.IMREAD_COLOR)
nrow = img_color.shape[0]
ncol = img_color.shape[1]
for i in range(0, nrow):
for j in range(0, ncol):
point = [i,j]
res = inside_or_outside(polygon, point)
if res == 1 :
img_color[i,j,0] = 0
img_color[i,j,1] = 0
img_color[i,j,2] = 255
#cv2.imwrite('inspect_img_{}_{}_{}.png'.format(NOW, threshold1, threshold2),img_color)
cv2.imshow('inspect_img_{}.png'.format(NOW), img_color)
cv2.waitKey(0)
cv2.destroyAllWindows()
사용법
polygon = [[200,150], [300,150], [170,300], [200,150]]
polygon_plot(master_img_path, 773, polygon)
