5 Best Ways to Check if a Point is Inside a Polygon in Python

by

💡 Problem Formulation: Determining whether a specific point lies within the boundaries of a polygon is a common computational geometry problem. This article explores 5 efficient methods to achieve this in Python. As an example, given a polygon defined by its vertices, and a point represented by its coordinates, we seek to return a boolean indicating whether the point lies inside the polygon.

Method 1: Ray Casting Algorithm

The Ray Casting algorithm operates by extending a line from the point in question and counting how many times the line crosses the polygon’s edges. If it crosses an odd number of times, the point is inside; if even, it’s outside.

Here’s an example:

from matplotlib.path import Path

polygon = Path([(0,0), (5,5), (5,0)])
point = (3,3)

def is_inside(point, polygon):
    return polygon.contains_point(point)

print(is_inside(point, polygon))

Output: True

This Python snippet uses Matplotlib’s Path class to create a polygon and its contains_point() method to determine if the point is inside. It’s an efficient and easy-to-use method for convex and concave polygons alike.

Method 2: Winding Number Algorithm

Winding Number Algorithm calculates the number of times the polygon winds around the point. If this number is non-zero, the point lies inside the polygon.

Here’s an example:

import numpy as np

def is_inside(point, vertices):
    winding_number = 0
    x, y = point
    for i in range(len(vertices)):
        x1, y1 = vertices[i]
        x2, y2 = vertices[(i + 1) % len(vertices)]
        if y1 <= y = y > y2:
            if x < (x2 - x1) * (y - y1) / (y2 - y1) + x1:
                winding_number += 1 if y1 < y2 else -1
    return winding_number != 0

polygon_vertices = [(0,0), (5,0), (5,5), (0,5)]
point = (3,3)
print(is_inside(point, polygon_vertices))

Output: True

This function computes the winding number for the given point relative to the polygon vertices. It iterates over each edge of the polygon and updates the winding number accordingly to give a result.

Method 3: Using Shapely library

Shapely is a Python package for set-theoretic analysis and manipulation of planar features using functions from the GEOS library.

Here’s an example:

from shapely.geometry import Point, Polygon

polygon = Polygon([(0, 0), (5, 0), (5, 5), (0, 5)])
point = Point(3,3)

print(polygon.contains(point))

Output: True

This code creates a Polygon and a Point object via the Shapely library, and then verifies if the polygon contains the point with its contains() method, returning a boolean value.

Method 4: Using scipy.spatial library

The scipy.spatial library provides spatial algorithms and data structures. The ConvexHull class can be used for convex polygons to check point inclusion.

Here’s an example:

from scipy.spatial import ConvexHull, convex_hull_plot_2d
import matplotlib.pyplot as plt
import numpy as np

points = np.array([(0, 0), (5, 0), (5, 5), (0, 5)])
point_to_check = np.array([3, 3])
hull = ConvexHull(points)

def in_hull(p, hull):
    if hull.find_simplex(p) >= 0:
        return True
    return False
print(in_hull(point_to_check, hull))

Output: True

This example uses the ConvexHull class to create a convex hull from the polygon points. The find_simplex() method checks if the point is inside the hull.

Bonus One-Liner Method 5: Using matplotlib.path

As a quicker one-liner alternative, you can use the matplotlib.path module that provides a Path class with a contains_point() method.

Here’s an example:

from matplotlib.path import Path

print(Path([(0,0), (5,5), (5,0)]).contains_point((3,3)))

Output: True

This succinct example offers a rapid way to check point inclusion by directly calling contains_point() on a Path object with the polygon’s vertices and the point in question.

Summary/Discussion

  • Method 1: Ray Casting. Applicable to any polygon shape. Requires external libraries such as matplotlib.
  • Method 2: Winding Number. Handles complex polygons. May be computationally intensive for large polygons.
  • Method 3: Shapely Library. Accurate and handles complex geometries. External dependency.
  • Method 4: Scipy.spatial. Works with convex shapes efficiently. Not suitable for concave polygons.
  • Method 5: Matplotlib.path One-Liner. Quick and concise. Limited to very simple use cases without additional context.