สมมติว่าเรามีรายการจุดคาร์ทีเซียน [(x1, y1), (x2, y2), ..., (xn, yn)] ซึ่งเป็นตัวแทนของรูปหลายเหลี่ยม และยังมีค่า x และ y สองค่า เราต้อง ตรวจสอบว่า (x, y) อยู่ภายในรูปหลายเหลี่ยมนี้หรือบนขอบเขต
ดังนั้น หากอินพุตเหมือนกับคะแนน =[(0, 0), (1, 3), (4, 4), (6, 2), (4, 0)] pt =(3, 1)
แล้วผลลัพธ์จะเป็น True
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- ตอบ :=ผิด
- สำหรับฉันในช่วง 0 ถึงขนาดของรูปหลายเหลี่ยม - 1 ทำ
- (x0, y0) :=รูปหลายเหลี่ยม[i]
- (x1, y1) :=รูปหลายเหลี่ยม[(i + 1) ขนาด mod ของรูปหลายเหลี่ยม]
- ถ้า pt[1] ไม่อยู่ในช่วงต่ำสุด y0, y1 และสูงสุด y0, y1 แล้ว
- ติดตามตอนต่อไป
- ถ้า pt[0] <ขั้นต่ำ x0 และ x1 แล้ว
- ติดตามตอนต่อไป
- cur_x :=x0 ถ้า x0 เหมือนกับ x1 มิฉะนั้น x0 + (pt[1] - y0) *(x1 - x0) /(y1 - y0)
- ans :=ans XOR (1 เมื่อ pt[0]> cur_x เป็นจริง มิฉะนั้น 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
