알고리즘/기하
2021. 2. 26.
다각형 내부 점 판정
어떤 다각형과 점이 주어질 때, 점이 다각형 내부에 있는지 여부를 판별해 봅시다. 다음과 같이 다각형과 점들이 있다고 가정합시다. 각각의 점에서 시작하면서, x축에 평행한 반직선을 그어 봅시다. (반직선의 방향은 상관없습니다) 이 반직선이 다각형의 변과 홀수번 교차한다면, 이 점은 다각형 내부에 있습니다. 짝수번 교차한다면, 이 점은 다각형 외부에 있습니다. 선분과 반직선의 교차판정은 역시 CCW를 이용하면 편리합니다. 교차 판정시 다음과 같은 예외를 조심합시다. 1. 반직선이 다각형의 꼭짓점을 지날 때 꼭짓점 기준 위쪽에 있는 변/아래쪽에 있는 점 중 한가지 경우에만 교차한다고 판정하면 됩니다. 2. 반직선이 일부 변을 완전히 포함할 때 이 변과는 교차하지 않는다고 판정하면 됩니다. 시간복잡도는 다각형..
