[💬] 점이 다각형에 포함되는지 구하기

[vertex(4321vertex)]

특정한 점이 다각형 안에 포함되는지를 구하는 방법에 대한 글이에요

그리고 저도 수학이나 프로그래밍을 잘 아는게 아니라, 틀리거나 잘못된 내용이 있을수도 있어요

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

1. 점이 다각형에 포함되는지 구하는 알고리즘을 이용하는 방법

첫번째는 특정 점이 특정 다각형에 포함되는지를 구하는 알고리즘을 이용하는 방법이에요

위에 올려놓은 그림처럼, 어떤 점이 특정 다각형 안에 포함된다면

이때 해당 점에서 오른쪽으로 직선을 그었을때, 그 직선은 다각형의 모서리와 홀수번 교차해요

즉, 직선이 다각형과 짝수번 만나거나, 아예 만나지 않으면, 해당 점은 다각형 안에 포함되어있지 않은거에요

그리고 이 알고리즘은 앞의 그림처럼 볼록다각형에서만이 아니라 위에 올려놓은 그림처럼 오목다각형에도 적용될수 있어요

역시 마찬가지로 점이 다각형 내부에 포함되어있다면 오른쪽으로 그은 직선이 홀수번 만나고

포함되어있지 않으면 만나지 않거나 짝수번 만나게 되요

그리고 이때 특정 점에서 오른쪽으로 그은 직선이, 다각형의 모서리와 교차하는지를 판별하기 위해서는

두가지 단계를 거치게 되요

첫번째는 해당 점의 y좌표가, 해당 모서리의 y좌표의 상하 범위 내에 있는지를 체크하는거에요,

즉 위의 그림에서는 y값이 y1과 y2사이에 있어야 해요,

그리고 두번째는 해당 모서리의 두 양 끝 점을 지나는 직선의 방정식을 구해서, 해당 방정식에 점의 y좌표를 대입했을때 나오는 x값이

원래 점의 x값보다 커야해요, 즉 오른쪽에 있어야 해요

즉, 위의 그림에서 점 (x1,y1) (x2,y2) 를 지나는 직선의 방정식을 구한다음

그때 그 방정식에 파란 점의 y좌표를 대입해서 나오는 x값, 즉 주황색 점의 x값이 파랑색 점의 x값보다 커야해요

2. 꼭짓점의 좌표를 모서리로 바꿔주는 함수

여기서부터는 실제로 사용되는 코드에 대한 설명이에요

우선, 위에 올려놓은 그림처럼 다각형의 각 꼭짓점의 좌표가 배열로 주어졌을때

해당 좌표를 모서리들로 변환해서 배열로 출력해주는 함수에요

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

def sort(p)

line = Array.new

i = 0

until p[i] == nil

if p[i+1] == nil

line.push([p[i][0],p[i][1],p[0][0],p[0][1]])

else

line.push([p[i][0],p[i][1],p[i+1][0],p[i+1][1]])

end

i += 1

end

return line

end

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

위에 올려놓은 코드가 해당 함수의 코드에요, ruby프로그래밍 언어로 작성한거에요

[ [x1,y1],[x2,y2],[x3,y3] ] 형식의 배열로 다각형의 꼭짓점의 좌표를 입력하면

[ [x1,y1,x2,y2],[x2,y2,x3,y3],[x3,y3,x1,y1] ] 형식의 배열로 다각형의 각각의 모서리들을 출력해줘요

이때 꼭짓점들의 좌표는 시계방향, 혹은 반시계방향으로 순서대로 입력해야해요

3. 오른쪽으로 그은 직선이 모서리와 교차하는지 판별하는 함수

다음은 점에서 오른쪽으로 그은 직선이, 다각형의 특정 모서리와 교차하는지를 구하는 함수에요

ㅡㅡㅡㅡㅡ

def line_x(x1,y1,x2,y2,y)

if x1 == x2

x1 += 0.001

end

if y1 == y2

y1 += 0.001

end

return (y-y1)*((x2-x1)/(y2-y1))+x1

end

ㅡㅡㅡㅡㅡ

첫번째는 위의 그림처럼 두 점(x1,y1) (x2,y2)가 주어졌을때

이 두 점을 지나는 방정식을 구해서, 그 방정식에 특정 y값을 대입했을때 나오는 x값을 구해주는 함수에요

위의 그림에서 첫번째 줄이 두 점(x1,y1) (x2,y2)을 지나는 직선의 방정식이고

두번째 줄은 해당 방정식을 x = 의 형태로 정리한거에요, 함수에서 실제로 이용하는건 두번째 식이에요

그리고 이때 x1=x2 거나 y1=y2면 오류가 생길수도 있어서 그럴때만 x1과 y1에 미세한 값을 더해서 서로 같지 않게 조정하도록 했어요

(x1,y1,x2,y2,y) 형태로 입력하면, (x1,y1) (x2,y2)를 지나는 직선의 y에서의 x값을 출력해줘요

ㅡㅡㅡㅡㅡ

def right_cross(x1,y1,x2,y2,x,y)

if y < [y1,y2].min || y > [y1,y2].max

return 0

end

if line_x(x1,y1,x2,y2,y) < x

return 0

end

return 1

end

ㅡㅡㅡㅡㅡ

그리고 위에 올려놓은 함수가 첫번째 함수를 이용해서 오른쪽으로 그은 직선이 다각형의 모서리와 교차하는지를 판별하는 함수에요

우선 점의 y값이 모서리의 y값 사이 범위에 있는지 체크한다음

앞의 함수를 이용해서, 모서리의 양 끝 점을 지나는 직선의 방정식에 점의 y값을 대입해서 나온 x값이

원래 점의 x값보다 오른쪽에 있는지를 체크해요

그리고 둘 다 해당되면, 점에서 오른쪽으로 그은 직선이 모서리와 만난다고 판별하는거에요

(x1,y1,x2,y2,x,y) 형식으로 모서리의 양 끝 점의 좌표(x1,y1,x2,y2)과 점의 좌표(x,y)를 입력하면 되요

4. 점이 다각형에 포함되는지 구하는 함수

ㅡㅡㅡㅡㅡ

def point_polygon(x,y,p)

line = sort(p)

i = 0

j = 0

until line[i] == nil

x1,y1,x2,y2 = line[i][0],line[i][1],line[i][2],line[i][3]

if right_cross(x1,y1,x2,y2,x,y) == 1

j += 1

end

i +=1

end

if j%2 == 0

return 0

else

return 1

end

end

ㅡㅡㅡㅡㅡ

그리고 이게 앞의 함수들을 이용해서 최종적으로 점이 특정 다각형에 포함되는지를 구하는 함수의 코드에요

(x,y)에 구하고자 하는 점의 좌표를 입력하고, p애 [ [x1,y1],[x2,y2],[x3,y3] ] 형식으로 구하고자 하는 다각형들의 좌표를 입력하면

해당 점이 해당 다각형에 포함되어있다면 1을, 포함되어있지 않다면 0을 출력해줘요

이때 역시 꼭짓점들의 좌표는 시계방향 혹은 반시계방향으로 순서대로 입력해야해요

우선 2에서 이야기한 함수로 다각형의 꼭짓점의 좌표들을 모서리로 바꾸고

그 다음에 3에서 이야기한 함수로 다각형의 각각의 모서리들마다 주어진 점에서 오른쪽으로 그은 직선이 교차하는지를 체크해요

그렇게해서 최종적으로 교차한 횟수가 짝수번(2로 나눴을때 나머지가 0)이면 포함되어있지 않다고 판단하고

홀수번(2로 나눴을때 나머지가 0이 아닐경우)이면 포함되어 있다고 판단하는거에요

5. CCW알고리즘을 이용하는 방법

두번째로 이야기할 방법은 CCW알고리즘을 이용해서 특정 점이 특정 다각형 내부에 포함되어 있는지를 구하는 방법이에요

https://gall.dcinside.com/m/game_dev/162026

벡터의 연산과 활용

CCW알고리즘에 대한 설명은 위에 올려놓은 글의 22번 부분에 나와있어요, 

여기서 설명하는 방법은 위의 글의 24번에 나와있는 삼각형의 내부 판별을 다각형의 경우로 확장한거에요

즉, 위에 올려놓은 그림처럼

어떤 점이 특정 다각형의 내부에 있으면

다각형의 꼭짓점들에서 순서대로 해당 점에 CCW알고리즘을 실행했을때,

즉 1번-2번-파랑점, 2번-3번-파랑점, 이런식으로 5번-1번-파랑점까지 전부 실행했을때

모든 값들이 0보다 커야해요, 

그리고 이때 x좌표가 오른쪽이 +고, y좌표가 위쪽이 +일때 기준으로

다각형의 꼭짓점들의 좌표는 반시계방향으로 순서대로 주어져있어야해요

또, 앞에서 설명한 첫번째 방법과는 다르게, 이 방법은 볼록다각형일때만 사용할수 있어요, 첫번째 방법처럼 오목다각형에는 사용할수 없어요

ㅡㅡㅡㅡㅡ

def ccw(x1,y1,x2,y2,x3,y3)

return (x1*y2+x2*y3+x3*y1)-(y1*x2+y2*x3+y3*x1)

end

ㅡㅡㅡㅡㅡ

ㅡㅡㅡㅡㅡ

def point_polygon2(x,y,p)

i = 0

until p[i] == nil

if p[i+1] == nil

x1,y1,x2,y2,x3,y3 = p[i][0],p[i][1],p[0][0],p[0][1],x,y

else

x1,y1,x2,y2,x3,y3 = p[i][0],p[i][1],p[i+1][0],p[i+1][1],x,y

end

if ccw(x1,y1,x2,y2,x3,y3) <= 0

return 0

end

i += 1

end

return 1

end

ㅡㅡㅡㅡㅡ

그리고 위에 올려놓은 코드가 이렇게 CCW알고리즘을 이용하는 방법의 코드에요

첫번째는 CCW알고리즘의 코드고, 두번째가 실제로 점이 다각형의 내부에 있는지를 판별하는 코드에요

x,y로 구하려는 점의 좌표를 입력하고

p에 [ [x1,y1],[x2,y2],[x3,y3] ] 형태로 다각형의 꼭짓점의 각각의 좌표를 입력하면(단 이때 반시계방향으로 순서대로 입력해야해요)

다각형의 모든 꼭짓점들에서 순서대로 해당 점과 CCW알고리즘을 실행해서 만약 그 값이 모두 0보다 크면 포함된다고 1을 출력하고

만약 값이 0보다 같거나 작은 경우가 있다면 포함되지 않는다고 판별하고 0을 출력해요

그리고 위에 올려놓은 영상이 해당 코드들을 이용해서 실제로 인게임에서 점이 다각형에 포함되는지를 구하는 영상이에요

첫번째가 점이 다각형에 포함되는지를 구하는 알고리즘을 사용한 부분이고

두번째가 CCW알고리즘을 사용한 부분이에요

빨강색 점이 플레이어가 움직이는 점이에요, 해당 점이 다각형의 내부에 포함된다면 다각형과 점 둘다 반투명하게 표시되요

그리고 이런식으로 하면 점이 다각형에 포함되는지를 구할수 있어요

[얀테이(lose7560)]

고수ㄷㄷ..

[얀테이(lose7560)]

[익명(121.139)]

컨벡스훌 문제 아닌가

[불타는키보드(1bnmaker)]

[SR4(succeed4464)]

고수....

[ㅇㅇ 1(1.249)]

존나 신기하다