1. 임의의 점이 다각형 내부에 있는지 판정하는 방법
단순한 다각형과 외부의 점을 생각해봅시다.
외부의 점에서 반직선을 그리면 다각형과 만나는 점의 개수가 0개 아니면 2개입니다.
만약 다각형 내부에 점이 있다면 어떨까요?
점에서 반직선을 그리면 다각형과 만나는 점의 개수가 1개입니다.
오목 다각형과 같이 복잡한 다각형에서는 어떨까요?
외부의 점은 0개 또는 짝수 개의 교점이 생깁니다.
내부의 점은 홀수 개의 교점이 생깁니다.
특정 점에서 반직선을 그렸을 때, 다각형과의 교점의 개수가 홀수 개이면 내부에 있는 점으로 판정할 수 있습니다.
2. 반직선과 선분의 교차 여부 판정
이제 특정 점에서 그린 반직선과, 다각형의 모든 선분이 교차하는지 확인하여 교점의 개수를 세면 됩니다.
반직선과 선분의 교차 여부는 어떻게 판정할 수 있을까요?
먼저, 반직선은 가장 간단하게 x축과 나란하게 그리겠습니다.
해당 반직선은 함수 \(y = b\)의 그래프 위에 있습니다.
따라서 점\((a, b)\)가 점\((x_1, y_1)\)과 점\((x_2, y_2)\)를 연결하는 선분과 교차하려면,
우선 \(y_1 \le b \le y_{2}\) 을 만족해야합니다.
그리고 점 \((a, b)\)는 교점보다 왼쪽에 있어야합니다.
이것을 어떻게 알 수 있을까요?
선분을 포함하는 직선을 그래프로 하는 함수는 다음과 같습니다.
\( y = \frac{y_2-y_1}{x_2-x_1}x + C \)
점 \( (x_1, y_1) \)을 대입하면 y절편 C는 다음과 같습니다.
\(C = y_1 - \frac{y_2-y_1}{x_2-x_1}x_1 \)
정리하면,
\(y = \frac{y_2-y_1}{x_2-x_1}x + (y_1 - \frac{y_2-y_1}{x_2-x_1}x_1)\)
점 \((a, b)\)가 교점보다 왼쪽에 있으려면,
\( b \ge \frac{y_2-y_1}{x_2-x_1}a + (y_1 - \frac{y_2-y_1}{x_2-x_1}x_1) \)
양변에 \( (x_2 - x_1) \)을 곱하면,
\(b(x_2-x_1) \ge (y_2-y_1)a + y_1(x_2-x_1) - (y_2-y_1)x_1\)
이항하여 묶어주면,
\( (b - y1)(x_2-x_1) \ge (y_2-y_1)(a-x_1) \)
이 조건식으로 프로그래밍하면 나누기가 없기 때문에 정확히 교차하는지 판정할 수 있습니다.
(단 x1과 x2의 비교 결과에 따라 부등호의 방향에 주의)
def is_crossed(p, p1, p2):
a, b = p
x1, y1 = p1
x2, y2 = p2
# 조건1
if not (min(y1, y2) <= b <= max(y1, y2)):
return False
if x1 > x2:
x1, y1, x2, y2 = x2, y2, x1, y1
# 조건2
if not ((b-y1)*(x2-x1) >= (y2-y1)*(a-x1)):
return False
return True
print(is_crossed((1, 2), (2, 1), (3, 4)))
# True
print(is_crossed((3, 2), (2, 1), (3, 4)))
# False
3. 조심해야 할 경계 조건
가. 다각형 변 위에 점이 있는 경우
다각형 변 위에 점이 있다면 문제가 생길 수 있으므로, 정확히 변 위에 점이 위치하는지 판정하고 미리 처리해야 합니다.
만약 미리 처리하지 않을 경우,
변 위에 점을 교차라고 판정하면, 왼쪽 그림은 외부, 오른쪽 그림은 내부로 판정이 됩니다.
반대로 변 위의 점을 교차라고 판정하지 않으면, 왼쪽 그림은 내부, 오른쪽 그림은 외부로 판정이 됩니다.
나. 반직선 위에 다각형의 꼭짓점이 있는 경우
다. 다각형의 꼭짓점 위에 점이 있는 경우
