Point in polygon
- Algorithms course
- Expert
- Lesson 23/41
- 4 min
Test point inclusion with ray casting.
Point in polygon
The point in polygon problem decides whether a point lies inside or outside a polygon. The best-known method is the ray casting algorithm.
We cast an infinite ray in a fixed direction (typically to the right) and count how many polygon edges it crosses. An odd count means inside, an even count means outside.
For each edge a single comparison suffices; total complexity is O(n).
Ray casting in practice
In practice we test two conditions for each edge: whether the ray falls in the y range and whether it crosses to the right of the point.
The first condition is (yi > py) != (yj > py). The second computes the x intersection via linear interpolation and compares it to px.
When both conditions hold we flip the inside variable. After the loop we return the inside value.
Practice point_in_polygon function
Write point_in_polygon(poly, px, py). Return True if the point is inside, False otherwise. Print True with print(point_in_polygon([(0,0), (4,0), (4,3), (0,3)], 2, 1)).
Starter code
def point_in_polygon(poly, px, py):
# Ray casting methodSample solution
def point_in_polygon(poly, px, py):
# Ray casting method
n = len(poly)
inside = False
j = n - 1
for i in range(n):
xi, yi = poly[i]
xj, yj = poly[j]
if ((yi > py) != (yj > py)) and (px < (xj - xi) * (py - yi) / (yj - yi) + xi):
inside = not inside
j = i
return inside
print(point_in_polygon([(0,0), (4,0), (4,3), (0,3)], 2, 1))Expected output
True
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 ray crossing condition
if ((yi > py) != (yj > py)) and (px < (xj - xi) * (py - yi) / (yj - yi) + ____):if ((yi > py) != (yj > py)) and (px < (xj - xi) * (py - yi) / (yj - yi) + xi):Explanation: xi gives the x intersection offset.
2 Ray casting concepts
| Term | Meaning |
|---|---|
odd crossings |
Inside |
even crossings |
Outside |
rightward ray |
Direction |
O(n) |
Complexity |
3 If the ray crosses an even number of times, where is the point?
inside = not inside- Unknown
- Inside
- On the boundary
- Outside Correct answer
Explanation: An even number of crossings means outside.