INPOLY: A fast points-in-polygon test

A fast test to determine point inclusion for general polygonal geometries.
13.6K Downloads
Updated 19 Dec 2020

INPOLY computes the intersection between a set of points and a general polygonal region in the plane, returning the 'inside', 'outside' and 'boundary' status for each vertex. General non-convex and multiply-connected polygonal regions can be handled. INPOLY is intended as a fast replacement for MATLAB's default INPOLYGON routine.

See POLYDEMO to get started with a set of example problems:

polydemo(1); % a simple example
polydemo(2); % multiply-connected domains
polydemo(3); % speed comparison

INPOLY implements a sorted 'crossing-number' test designed to achieve fast performance for complex inputs. Given a configuration with N points and M polygon edges, INPOLY runs in approximately O((N+M)*LOG(N)) time on average, improving on the O(N*M) scaling of naive implementations.

Cite As

Darren Engwirda (2024). INPOLY: A fast points-in-polygon test (https://github.com/dengwirda/inpoly), GitHub. Retrieved .

MATLAB Release Compatibility
Created with R2018b
Compatible with any release
Platform Compatibility
Windows macOS Linux
Categories
Find more on Elementary Polygons in Help Center and MATLAB Answers

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Versions that use the GitHub default branch cannot be downloaded

Version Published Release Notes
3.0.0.0

Linked to GitHub

2.0.0.0

Major updates, Octave support, bug fixes.

1.0.0.0

Floating point error reduced

To view or report issues in this GitHub add-on, visit the GitHub Repository.
To view or report issues in this GitHub add-on, visit the GitHub Repository.