Point in polygon

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.

Exercise 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)).

Show example 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))

Test yourself

ray crossing condition

if ((yi > py) != (yj > py)) and (px < (xj - xi) * (py - yi) / (yj - yi) + ____):

Show answer

if ((yi > py) != (yj > py)) and (px < (xj - xi) * (py - yi) / (yj - yi) + xi):

Ray casting concepts

odd crossings

Inside
even crossings

Outside
rightward ray

Direction
O(n)

Complexity
If the ray crosses an even number of times, where is the point?
```
inside = not inside
```
- Unknown
- Inside
- On the boundary
- Outside
Show answer

Outside — An even number of crossings means outside.

Next lesson: Summary - Geometry

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies