Giả sử chúng ta có một danh sách các điểm Cartesian [(x1, y1), (x2, y2), ..., (xn, yn)], đại diện cho một đa giác và cũng có hai giá trị x và y, chúng ta phải kiểm tra xem (x, y) nằm bên trong đa giác này hay trên ranh giới.
Vì vậy, nếu đầu vào giống như điểm =[(0, 0), (1, 3), (4, 4), (6, 2), (4, 0)] pt =(3, 1)
thì đầu ra sẽ là True
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- ans:=Sai
- đối với tôi trong phạm vi từ 0 đến kích thước của đa giác - 1, thực hiện
- (x0, y0):=polygon [i]
- (x1, y1):=polygon [(i + 1) kích thước mod của đa giác]
- nếu pt [1] không nằm trong phạm vi tối thiểu là y0, y1 và tối đa là y0, y1, thì
- chuyển sang lần lặp tiếp theo
- nếu pt [0]
- chuyển sang lần lặp tiếp theo
- cur_x:=x0 nếu x0 giống với x1 nếu không x0 + (pt [1] - y0) * (x1 - x0) / (y1 - y0)
- ans:=ans XOR (1 khi pt [0]> cur_x là true, ngược lại là 0)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
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))
Đầu vào
[(0, 0), (1, 3), (4, 4), (6, 2), (4, 0)], (3, 1)
Đầu ra
True