Fast points-in-polygon test and distances to polygons.
Project description
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.8 - 3.10
- 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):
@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
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.
Project details
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distributions
Built Distributions
Hashes for polygons-0.3.2-cp310-none-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a807a88a12c3c070a61172dcb65966d73b0012cad95e31013fbf3d9376880043 |
|
MD5 | c0ec29f688ef93e4518434b0e0096e31 |
|
BLAKE2b-256 | 5c6c3e49f219d6bada513348c9ac68c7326a10a1332980d430ac1424f89048d5 |
Hashes for polygons-0.3.2-cp310-cp310-manylinux_2_34_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f282dd409a918c9a0b484d3645a26052cef71cd1ad05ea709bb750e4432ba51a |
|
MD5 | 63ca917ec3a1158ea863a6e90eee970e |
|
BLAKE2b-256 | 95a0377e0385a94a9dd66be8b2be36d9ceb9ed0095eafabf19e30ee118389ef9 |
Hashes for polygons-0.3.2-cp310-cp310-macosx_10_7_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8a6bb710aedeaa83a65e471b23f1d7f564f23903b64961cb003436a261182d5a |
|
MD5 | e8bb36577970edac6bf70d81d3e6e7bd |
|
BLAKE2b-256 | 9c68d59e81fa92f4e17513065b65f59fac47e638d051a9e57bc28571b8d72ad7 |
Hashes for polygons-0.3.2-cp39-none-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4886b525d4e3f659bfe7bca279e723ce34c04d0448dcf707b416783b2bbcb407 |
|
MD5 | 15f13f312f6cc305ad74b4f86433a524 |
|
BLAKE2b-256 | 59ad4151744a66f09be18ef5c200619cbbf955910d8e7f87a4f31415b10d2d5e |
Hashes for polygons-0.3.2-cp39-cp39-manylinux_2_34_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a804226fa3c5650d63016493bc461425d98f85154676a4c1471f06b3c8af0ddd |
|
MD5 | c784a4bdd09bf992cd73d8f5f245618d |
|
BLAKE2b-256 | d23306712616c077f0575ed52837fc94d2b27c4db5a30819590a9b0511b45c48 |
Hashes for polygons-0.3.2-cp39-cp39-macosx_10_7_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9ddee8e069826fe741b3fe702694799f2d3d79b05597ab0375f2b7caafcdd232 |
|
MD5 | e4329106c679971facde5bdeecf440f3 |
|
BLAKE2b-256 | 5a46c6e3c2d9a6a9c2acbe22b3097f089577fdd2d1992222f31e7e8aeb1093c8 |
Hashes for polygons-0.3.2-cp38-none-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d619ffe98db532b492b212d223925ae2471467665d3e515a809251de0119c316 |
|
MD5 | 57f2d75be6a87533f41a20804aeeccbe |
|
BLAKE2b-256 | c09e89df3fa2553386168f2ee2ed0fb30877d98cce219e21abf80b094d15c3a9 |
Hashes for polygons-0.3.2-cp38-cp38-manylinux_2_34_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8e114d07f7389d4e3fedf836bbf49efc54e45b4c48062f20adabfcdf3160db57 |
|
MD5 | 9cd10ea7120d6736a1d78fbfe98b3463 |
|
BLAKE2b-256 | 47382c342abe28682c2a69b9bcfbac5d6f792f442e381ae5335f64140d17169e |
Hashes for polygons-0.3.2-cp38-cp38-macosx_10_7_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | bb2f15f17e6e03a87d6c91691db9e0e46e8fad1d1644f093e99a5112f6ceb3db |
|
MD5 | fcf3bd4304cd8afcb3f78ddedc45f771 |
|
BLAKE2b-256 | 7a0bdead1c58a81381a806c7efa30b2b413d8f112c970f8e6e2535cbf05ad83a |