Polygons: Fast points-in-polygon test and distances to polygons

Computes distances to polygon edges and vertices and can check whether points are inside/outside.

This library is optimized to perform well with hundreds or thousands of polygons and thousands or millions of points.

Example timings (190 polygons, 1 M reference points, run on i7-10710U): - distances to nearest edges: 0.7 s - distances to nearest vertices: 0.6 s - check whether points are inside or outside: 0.1 s

Installation using pip

$ pip install polygons

Supported versions

Python: 3.6, 3.7, 3.8, 3.9
Operating systems: Linux, macOS, and Windows

Capabilities

Check whether points are inside or outside polygons
Nearest distances to edges
Nearest distances to vertices

Recommended citation

If you use this tool in a program or publication, please acknowledge its author(s):

bibtex @misc{polygons, author = {Bast, Radovan}, title = {Polygons: Fast points-in-polygon test and distances to polygons}, month = {2}, year = {2021}, publisher = {Zenodo}, version = {v0.2.0}, doi = {10.5281/zenodo.3825616}, url = {https://doi.org/10.5281/zenodo.3825616} }

Python example

```python import polygons

polygon_points is a list of lists

the library has been developed to perform

with very many polygons - this is just to have a simple example

in this example the polygons have the same number of points but there

is no restriction like this, this is only an example

polygon_points = [ [(0.0, 0.0), (1.0, 0.0), (1.0, 1.0), (0.0, 1.0)], [(0.0, 2.0), (1.0, 2.0), (1.0, 3.0), (0.0, 3.0)], ]

the more points you compute in one go, the better

here using two points to make a simple example but if you have many points

then compute a thousand or a million in one go

so that the library can parallelize over the points

points = [(0.5, 0.5), (0.5, -0.5)]

parameters for the tree construction:

- each tree node has 4 children nodes

- each leaf collects 4 edges

you can try different parameters and check the timing

they (should) have no effect on the results apart from timing

numedgeschildren = 4 numnodeschildren = 4 tree = polygons.buildsearchtree( polygonpoints, numedgeschildren, numnodes_children )

inside = polygons.pointsareinside(tree, points) print(inside) # [True, False]

indices are the indices of the nearest polygon vertices (counted

consecutively)

indices, distances = polygons.distancesnearestvertices(tree, points) print(indices) # [0, 0] print(distances) # [0.7071067811865476, 0.7071067811865476]

distances = polygons.distancesnearestedges(tree, points) print(distances) # [0.5, 0.5]

indices, distances = polygons.distancesnearestvertices( tree, [(0.6, 0.6), (0.5, -0.5)] ) print(indices) # [2, 0] print(distances) # [0.5656854249492381, 0.7071067811865476] ```

References which were used during coding

Development notes

Running the benchmark: $ cargo test --release -- --ignored --nocapture

Python interface inspired by https://github.com/dev-cafe/rustafarian.

Building and testing the Python interface: $ maturin develop

Image

Social media preview generated using https://github.com/qrohlf/trianglify.