ตรวจสอบจุดอยู่ใน Polygon หรือบนขอบ (Point in Polygon) ใน Python

ปัญหา: กำหนด Polygon = List of Points `[(x1,y1), (x2,y2), ..., (xn,yn)]` และ Point `pt = (x,y)` หาว่า pt อยู่ใน Polygon หรือบนขอบ (Boundary)

ใช้ Ray Casting Algorithm (Even-Odd Rule): ยิง Ray แนวนอนไปทางขวา นับจำนวนครั้งที่ตัด Edge ของ Polygon → คี่ = ใน, คู่ = นอก

อัลกอริทึม

1. Loop ทุก Edge `(x0,y0)` → `(x1,y1)` ของ Polygon
2. ถ้า `pt.y` ไม่อยู่ระหว่าง `y0` และ `y1` → Skip (Ray ไม่ตัด Edge นี้)
3. ถ้า `pt.x < min(x0,x1)` → Skip (Ray ตัด Edge ก่อนถึง pt)
4. คำนวณ `cur_x` = จุดตัดของ Ray กับ Edge
5. Flip `ans` (XOR) ถ้า `pt.x > cur_x`

การติดตั้ง

class Solution:
    def solve(self, polygon, pt):
        ans = False
        n = len(polygon)
        
        for i in range(n):
            x0, y0 = polygon[i]
            x1, y1 = polygon[(i + 1) % n]  # Wrap around
            
            # Check if horizontal ray at pt.y intersects this edge
            if not (min(y0, y1) < pt[1] <= max(y0, y1)):
                continue
            
            # Ray starts at pt.x, goes right
            if pt[0] < min(x0, x1):
                continue
            
            # Intersection x-coordinate
            if x0 == x1:  # Vertical edge
                cur_x = x0
            else:
                cur_x = x0 + (pt[1] - y0) * (x1 - x0) / (y1 - y0)
            
            # Flip if intersection is to the right of point
            ans ^= (pt[0] > cur_x)
        
        return ans

# Test
ob = Solution()
points = [(0, 0), (1, 3), (4, 4), (6, 2), (4, 0)]
pt = (3, 1)
print(ob.solve(points, pt))  # True

คำอธิบาย

• Loop Edge ทุกคู่ (i, i+1 mod n)

• เงื่อนไข `min(y0,y1) < pt[1] <= max(y0,y1)`: Ray ตัด Edge ได้ก็ต่อเมื่อ pt.y อยู่ในช่วง Y ของ Edge (ใช้ < และ <= เพื่อจัดการ Vertex ให้ถูกต้อง)

• `pt[0] < min(x0,x1)`: Ray เริ่มต้นซ้ายกว่า Edge → ไม่ตัด

• `cur_x`: จุดตัด X ของ Ray (y=pt.y) กับ Line Segment

• `ans ^= (pt[0] > cur_x)`: XOR Flip เมื่อ Ray ตัด Edge ขวาของ Point

Edge Cases การจัดการ

Complexity

• Time: O(n) น = จำนวน Vertices
• Space: O(1)

Alternative: Shapely Library (Production)

from shapely.geometry import Point, Polygon

poly = Polygon([(0,0), (1,3), (4,4), (6,2), (4,0)])
point = Point(3, 1)
print(point.within(poly) or point.touches(poly))  # True

Note: Ray Casting ใช้ได้กับ Simple Polygon (Non-self-intersecting) สำหรับ Complex Polygon ใช้ Winding Number Algorithm

นับ Subsets ที่มีผลรวมเท่ากับ k ใน Python (Subset Sum Count)

หาความยาว Longest Circular Increasing Subsequence ใน Python