5 Best Methods to Check If a Point is Inside or on the Boundary of a Polygon in Python

Rate this post

πŸ’‘ Problem Formulation: Determining whether a given point resides within or on the boundary of a polygon can be essential for geometric computations in Python. For instance, given a point with coordinates (x,y) and a polygon defined by a list of vertices [(x1,y1), (x2,y2), …, (xn,yn)], the objective is to develop a program that returns True if the point lies inside or on the edge of the polygon and False otherwise.

Method 1: Ray Casting Algorithm

The Ray Casting algorithm determines the status of a point by extending a “ray” from the point in question and counting its intersections with the polygon’s edges. If the count of intersections is odd, the point is inside; if even, it is outside. However, edge cases need careful handling, specifically when the ray intersects a vertex of the polygon.

Here’s an example:

from matplotlib.path import Path

def is_point_inside_polygon(point, polygon):
    path = Path(polygon)
    return path.contains_point(point)

# Define the polygon and the point
polygon = [(0,0), (0,10), (10,10), (10,0)]
point = (5, 5)

# Check if point is inside the polygon
print(is_point_inside_polygon(point, polygon))

The output of this code snippet:

True

This code uses the Matplotlib library’s Path class to define the polygon, then it applies the contains_point method to check whether the specified point lies within the defined path. It is a concise and straightforward implementation of the Ray Casting algorithm in Python.

Method 2: Winding Number Algorithm

The Winding Number algorithm involves counting the number of times the polygon winds around the point. A nonzero winding number indicates that the point is inside, while a zero value implies the point is outside the polygon.

Here’s an example:

import math

def is_point_inside_polygon(point, polygon):
    winding_number = 0
    x, y = point
    for i in range(len(polygon)):
        x1, y1 = polygon[i]
        x2, y2 = polygon[(i + 1) % len(polygon)]
        if y1  y and is_left((x1, y1), (x2, y2), (x, y)):
                winding_number += 1
        elif y2  0

# Define the polygon and the point
polygon = [(0,0), (0,10), (10,10), (10,0)]
point = (5, 5)

# Check if point is inside the polygon
print(is_point_inside_polygon(point, polygon))

The output of this code snippet:

True

This code snippet demonstrates the Winding Number algorithm in action. The function is_point_inside_polygon() iterates over the edges of the polygon, checking if a line from the point to infinity crosses the edge. The is_left() function assists in determining the orientation of the crossing. The winding number’s parity provides the answer regarding whether the point is inside or outside the polygon.

Method 3: Angle Summation Algorithm

The Angle Summation algorithm adds up the angles between consecutive vertices of the polygon from the perspective of the point in question. If the sum is close to 2Ο€, the point is inside; otherwise, it is outside.

Here’s an example:

import numpy as np

def is_point_inside_polygon(point, polygon):
    n = len(polygon)
    angles_sum = 0
    for i in range(n):
        p1 = np.array(polygon[i]) - point
        p2 = np.array(polygon[(i + 1) % n]) - point
        angles_sum += np.arctan2(np.cross(p1, p2), np.dot(p1, p2))
    return np.isclose(angles_sum, 2 * np.pi)

# Define the polygon and the point
polygon = [(0,0), (0,10), (10,10), (10,0)]
point = (5, 5)

# Check if point is inside the polygon
print(is_point_inside_polygon(point, polygon))

The output of this code snippet:

True

This code snippet uses NumPy for vector arithmetic to perform the Angle Summation algorithm. It calculates the angle between each pair of consecutive edges w.r.t. the given point and sums them up. If the sum is approximately 2Ο€, NumPy’s isclose() function confirms that the point lies within the bounds of the polygon.

Method 4: Shoelace Formula for Polygon Area

The Shoelace formula calculates the area of a polygon. If the area calculated with the point in question as a vertex is equal to the area of the polygon without the point, then the point lies on the boundary of the polygon.

Here’s an example:

def polygon_area(polygon):
    n = len(polygon)
    area = 0.0
    for i in range(n):
        x1, y1 = polygon[i]
        x2, y2 = polygon[(i + 1) % n]
        area += x1 * y2 - x2 * y1
    return abs(area) / 2.0

def is_point_on_boundary(point, polygon):
    for i in range(len(polygon)):
        temp_polygon = polygon[:i] + [point] + polygon[i:]
        if polygon_area(temp_polygon) == polygon_area(polygon):
            return True
    return False

# Define the polygon and the point
polygon = [(0,0), (0,10), (10,10), (10,0)]
point = (0, 0)

# Check if point is on the boundary of the polygon
print(is_point_on_boundary(point, polygon))

The output of this code snippet:

True

In this snippet, the polygon_area() function applies the Shoelace formula to compute the area of a given polygon. The is_point_on_boundary() function then substitutes each vertex with the point in question and compares the resulting area with the original polygon’s. If they match, the point lies on the boundary.

Bonus One-Liner Method 5: Using Shapely Library

Shapely is a BSD-licensed Python package for manipulation and analysis of planar geometric objects. It has straightforward methods for checking if a point is inside or on the boundary of a polygon.

Here’s an example:

from shapely.geometry import Point, Polygon

# Define the polygon and the point
polygon = Polygon([(0,0), (0,10), (10,10), (10,0)])
point = Point(5, 5)

# Check if point is inside or on the boundary of the polygon
print(polygon.contains(point) or polygon.touches(point))

The output of this code snippet:

True

This code utilizes the Shapely library to first create objects for the point and the polygon. The contains() and touches() methods are then used to determine if the point is within or on the boundary of the polygon. It’s a very concise and readable way to solve the problem.

Summary/Discussion

  • Method 1: Ray Casting Algorithm. Widely used. Handles complex polygons well. Requires careful implementation to deal with edge cases.
  • Method 2: Winding Number Algorithm. Good for determining point inclusion robustly. More complex to implement. May be less performant than other methods for simple cases.
  • Method 3: Angle Summation Algorithm. Theoretical appeal by leveraging geometric properties. Computationally intensive due to angle calculations. Sensitive to numerical precision.
  • Method 4: Shoelace Formula for Polygon Area. Good for determining if a point is on the border. Not useful for determining if a point is within the polygon. Depends on computation of area.
  • Bonus One-Liner Method 5: Using Shapely Library. Pythonic and concise. The best choice if external libraries are allowed. Not suitable for environments where dependencies are restricted.