Introduction

Determining whether a point is inside an arbitrary shape is a fundamental problem in computational geometry with numerous practical applications in computer graphics, geographic information systems (GIS), collision detection in physics engines, and game development. The solution depends on the complexity of the shape, which could range from simple convex polygons to complex concave polygons with holes.

Problem Definition

Given a point $P(p_x, p_y)$ and an arbitrary polygon defined by its vertices, the goal is to determine if $P$ lies inside the polygon, outside it, or on its boundary. For most practical purposes, we focus on the inside-vs-outside distinction.

Geometric Definitions

1. Polygon: A plane figure described by a finite number of straight line segments connected to form a closed shape.
2. Convex Polygon: A polygon where any line segment connecting two interior points lies entirely inside or on the polygon. All interior angles are less than $180°$.
3. Concave Polygon: A polygon that is not convex, meaning at least one interior angle exceeds $180°$. A line segment between two interior points may pass outside the polygon.

Ray Casting Algorithm

The ray casting method (also called the crossing number algorithm) is one of the most common techniques for determining whether a point is inside a polygon. The principle is straightforward:

1. Cast a ray from the point $P$ in an arbitrary direction (typically along the positive x-axis).
2. Count how many times the ray intersects with the edges of the polygon.
3. If the number of intersections is odd, the point is inside. If even, the point is outside.

This works because a ray starting inside a closed polygon must cross an odd number of edges to escape, while a ray starting outside crosses an even number (including zero).

Algorithm Steps

1. Initialize an intersection counter to zero.
2. For each edge of the polygon defined by consecutive vertices $(x_1, y_1)$ and $(x_2, y_2)$:
   • Check if the ray from $P$ (going in the positive x-direction) could intersect this edge. The edge must straddle the y-coordinate of $P$, meaning one endpoint is above and one is below $p_y$.
   • Compute the x-coordinate of the intersection point using linear interpolation: $x_{intersect} = x_1 + \frac{(p_y - y_1)}{(y_2 - y_1)} \cdot (x_2 - x_1)$.
   • If $x_{intersect} > p_x$, the intersection is to the right of $P$, so increment the counter.
3. If the counter is odd, $P$ is inside the polygon. If even, $P$ is outside.

Implementation in Python

1def point_in_polygon(px, py, polygon):
2    """
3    polygon: list of (x, y) tuples forming a closed polygon.
4    Returns True if point (px, py) is inside the polygon.
5    """
6    n = len(polygon)
7    inside = False
8
9    x1, y1 = polygon[0]
10    for i in range(1, n + 1):
11        x2, y2 = polygon[i % n]
12        if min(y1, y2) < py <= max(y1, y2):
13            x_intersect = x1 + (py - y1) / (y2 - y1) * (x2 - x1)
14            if px < x_intersect:
15                inside = not inside
16        x1, y1 = x2, y2
17
18    return inside

The time complexity is $O(n)$ where $n$ is the number of edges. This is optimal since every edge must be checked at least once.

Winding Number Algorithm

The winding number algorithm is another approach that counts how many times the polygon winds around the point. A non-zero winding number means the point is inside.

1. For each edge, determine whether it crosses upward or downward relative to $P$.
2. For upward crossings where $P$ is to the left of the edge, increment the winding number.
3. For downward crossings where $P$ is to the right of the edge, decrement the winding number.
4. If the final winding number is non-zero, the point is inside.

The winding number approach handles complex polygons (including self-intersecting ones) more robustly than ray casting.

Handling Special Cases

Several edge cases need careful treatment:

• Point on an edge: Both algorithms may give inconsistent results when the point lies exactly on a polygon edge. Most implementations treat boundary points as either inside or outside consistently.
• Ray passing through a vertex: The ray casting algorithm can double-count or miss intersections at vertices. The standard fix is to treat edges as closed on one endpoint and open on the other (for example, include the lower vertex but exclude the upper vertex).
• Degenerate edges: Zero-length edges (duplicate consecutive vertices) should be skipped.

Extending to Complex Shapes

Polygons with Holes

For shapes with holes, test the point against the outer boundary and each hole boundary separately. The point is inside the shape if it is inside the outer boundary and outside all holes.

Curved Boundaries

For shapes with curved edges (circles, ellipses, Bezier curves), the ray casting approach still works but intersection calculations become more involved. For a circle centered at $(c_x, c_y)$ with radius $r$, the point is inside if $(p_x - c_x)^2 + (p_y - c_y)^2 < r^2$.

Comparison Table

Summary

The ray casting and winding number algorithms are the two primary methods for determining point-in-polygon containment. Both run in $O(n)$ time and handle convex and concave polygons. Ray casting is simpler to implement, while the winding number provides more robust results for complex shapes. For convex polygons specifically, binary search methods can achieve $O(\log n)$ time. Choosing the right algorithm depends on the shape complexity, the need for boundary handling, and whether the polygon may self-intersect.