볼록다각형 내부 점 빠르게 판별

(TODO: 설명 더 추가하기)

볼록N각형이 주어졌을 때, 점이 주어질 때마다 그 점이 다각형 내부에 들어있는지를 O(logN)에 구할 수 있습니다. 이렇게 하면 됩니다.

• 다각형을 전처리하여 "윗부분"과 "아랫부분"으로 나눕니다. 다각형의 둘레를 시계방향으로 돌았을 때 x좌표가 증가하는 부분이 윗부분, 감소하는 부분이 아랫부분입니다.
• 점 (xp, yp)가 주어졌다고 합시다. 만약 xp가 다각형의 최소 x값보다 작거나, 최대 x값보다 크다면, 이 점은 다각형 외부에 들어있습니다.
• 이 점이 "윗부분"의 아래에 놓여있는지 판별합니다. 어떻게? "윗부분"의 선분 중에서, 선분의 x좌표의 범위가 xp를 포함하는 선분 하나를 이분 탐색으로 찾습니다. 그 선분의 아래에 (xp, yp)가 있는지만 판별하면 됩니다. 이는 간단한 CW/CCW 판별로 구할 수 있습니다.
• 이 점이 "아랫부분"의 위에 놓여있는지 판별합니다. 똑같은 방법으로 판별할 수 있습니다.
• "윗부분"의 아래, "아랫부분"의 위에 놓여있으면 이 점은 다각형 내부에 들어있습니다.