폴리곤을 나타내는 데카르트 포인트 목록 [(x1, y1), (x2, y2), ..., (xn, yn)]이 있고 두 개의 값 x와 y가 있다고 가정하면 다음을 수행해야 합니다. (x, y)가 이 다각형 내부에 있는지 또는 경계에 있는지 확인하십시오.
따라서 입력이 점 =[(0, 0), (1, 3), (4, 4), (6, 2), (4, 0)] pt =(3, 1)
그러면 출력은 True
가 됩니다.이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- ans :=거짓
- 범위 0에서 다각형 크기 - 1에 있는 i에 대해
- (x0, y0) :=폴리곤[i]
- (x1, y1) :=폴리곤[(i + 1) 폴리곤의 모드 크기]
- pt[1]이 최소 y0, y1 및 최대 y0, y1 범위에 없으면
- 다음 반복으로 이동
- pt[0]
- 다음 반복으로 이동
- cur_x :=x0이 x1과 같으면 x0, 그렇지 않으면 x0 + (pt[1] - y0) *(x1 - x0) /(y1 - y0)
- ans :=ans XOR(pt[0]> cur_x가 참일 때 1, 그렇지 않으면 0)
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
class Solution: def solve(self, polygon, pt): ans = False for i in range(len(polygon)): x0, y0 = polygon[i] x1, y1 = polygon[(i + 1) % len(polygon)] if not min(y0, y1) < pt[1] <= max(y0, y1): continue if pt[0] < min(x0, x1): continue cur_x = x0 if x0 == x1 else x0 + (pt[1] - y0) * (x1 - x0) / (y1 - y0) ans ^= pt[0] > cur_x return ans ob = Solution() points = [(0, 0), (1, 3), (4, 4), (6, 2), (4, 0)] pt = (3, 1) print(ob.solve(points, pt))
입력
[(0, 0), (1, 3), (4, 4), (6, 2), (4, 0)], (3, 1)
출력
True