polygons 0.3.5

Fast points-in-polygon test and distances to polygons.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135

[![test status](https://github.com/bast/polygons/workflows/Test/badge.svg)](https://github.com/bast/polygons/actions)
[![license badge](https://img.shields.io/badge/license-%20GPL-blue.svg)](LICENSE)
[![link to Crates](https://img.shields.io/crates/v/polygons.svg)](https://crates.io/crates/polygons)
[![link to PyPI](https://badge.fury.io/py/polygons.svg)](https://badge.fury.io/py/polygons)
[![link to Zenodo/DOI](https://zenodo.org/badge/DOI/10.5281/zenodo.3825616.svg)](https://doi.org/10.5281/zenodo.3825616)


# 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.10 - 3.13
- 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     = {03},
  year      = {2025},
  publisher = {Zenodo},
  version   = {v0.3.5},
  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
num_edges_children = 4
num_nodes_children = 4
tree = polygons.build_search_tree(
    polygon_points, num_edges_children, num_nodes_children
)

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

# indices are the indices of the nearest polygon vertices (counted
# consecutively)
indices, distances = polygons.distances_nearest_vertices(tree, points)
print(indices)  # [0, 0]
print(distances)  # [0.7071067811865476, 0.7071067811865476]

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

indices, distances = polygons.distances_nearest_vertices(
    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

- <http://geomalgorithms.com/a03-_inclusion.html>
- <https://en.wikipedia.org/wiki/Point_in_polygon>
- <https://en.wikipedia.org/wiki/Binary_space_partitioning>


## 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.