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.12
- 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.3-cp312-none-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ae9c9a3a9d8091be48c4c2063a54929228e4216ad17479ef8b9d62fe48a958de |
|
MD5 | e8b6451b5db081904869445dd990419e |
|
BLAKE2b-256 | 7c07d1d641f2a01ba6711c540b3732c6b7eb17e83d88d881a7a013a32d71a60e |
Hashes for polygons-0.3.3-cp312-cp312-manylinux_2_34_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 10bb074c2d8428175589af93a2722a98594137b07ceea0139ea74a433d212474 |
|
MD5 | 6fae6acdbba5c22612d51a7b8631c93d |
|
BLAKE2b-256 | 4d038707929aa0565e08cf07e79607c78272eab3bd5a90cf87807dced7dbfaac |
Hashes for polygons-0.3.3-cp312-cp312-macosx_10_12_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a5def154428b2e835983e0abeb3b9ee3cf275aa461056d2b9f22525f9ee5e758 |
|
MD5 | cf075822015f4f6c7dd83867eb612d01 |
|
BLAKE2b-256 | d0c02ecbf1f2d537d14a1831f976bebd89953d15dd9b40bbc5ca06492b902372 |
Hashes for polygons-0.3.3-cp311-none-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f0599bdbefcefbc0950876e8cf127dd6c9858c0f469aed58110bf570fff11dec |
|
MD5 | 21cdc5920d2424b80fe584daeed5466a |
|
BLAKE2b-256 | 476e03542ecd333620b71b01dc86ad3ab6c1190dd1112ae15f12e7df8ffc2f0d |
Hashes for polygons-0.3.3-cp311-cp311-manylinux_2_34_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5e6f88b5b230be5620113f97d02de87ed628ff17f18479fea8d6dca89b1fc1b0 |
|
MD5 | bad1339180ec44fae99134b46690b8e7 |
|
BLAKE2b-256 | b673ae251e18e849b5c534d19ef9656d179736015e0bf3cfab56177a32a6e71b |
Hashes for polygons-0.3.3-cp311-cp311-macosx_10_12_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 538efba52a46a77540b6c270ceaec052c14a20abc9bfe20297a0d79934a5d3e1 |
|
MD5 | 2962f9b0a6395dc471827edc2a2ab8a5 |
|
BLAKE2b-256 | a0eb9cadc0244c26a4fe3b18a4124b1173198506bb9dc18b5d190461d930cf6d |
Hashes for polygons-0.3.3-cp310-none-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | cbd03da96f02707d1877b5538f76d08061c69c23ad7a5c7b7fdc446647e9e5e8 |
|
MD5 | 9c012671696eb4be601d78a7496d4020 |
|
BLAKE2b-256 | 5083044e9acd86fde055634b299659386b96e83dcc360c57ffc6d07d7e632fa3 |
Hashes for polygons-0.3.3-cp310-cp310-manylinux_2_34_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 26f634a9b32998726f790ef4d778ade5e3f7e01246bb9f6cd70c9f90882bc684 |
|
MD5 | 6397b2dfa01490a7d13ad42179e510fb |
|
BLAKE2b-256 | 064806c84a21bfc79c88011f184538c212b5e027713b357fc1a885cc8e08f1cc |
Hashes for polygons-0.3.3-cp310-cp310-macosx_10_12_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3bffa0d6d0de35471890eeabee47f57d17fd30044a7e41469533b3afbc93c478 |
|
MD5 | d0ba67b75872c06ef1f129fcdccc7f3f |
|
BLAKE2b-256 | c025814ec90b48a4439676fc0cf37bad6d0dfba1eb8287fa0359c45313d343e5 |
Hashes for polygons-0.3.3-cp39-none-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b1eb955a333b7a82b39908e0b80bda0d47d90f78724a11d53558a81338176bb3 |
|
MD5 | dfcbf1bcc5f191a0d23b08cd3f322849 |
|
BLAKE2b-256 | 86608a19b39e08f4c5950bd1e69f0b3f5c9dd372ae7fcc6c6d21db80564d0238 |
Hashes for polygons-0.3.3-cp39-cp39-manylinux_2_34_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c4e51c08bafc07c8ca16c37079e52bbf35d9c120cfe1b142c7acefda4433e7fa |
|
MD5 | f5825d58cc17e11599f711cfb6e37808 |
|
BLAKE2b-256 | 9482a832241138da44ef3f9348f586f506e91df26a350417c666543f25b47b03 |
Hashes for polygons-0.3.3-cp39-cp39-macosx_10_12_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a3cbb81e12dcece18bdd53e765f1800a3d389cccaa7468c1c021b24e1f4696d1 |
|
MD5 | 0b539bed99960c90f4d84d828628aa12 |
|
BLAKE2b-256 | 4aed15ab33897608d3db6c612848b0a24dfb595af8cb3e6ea77e3b40807312bf |
Hashes for polygons-0.3.3-cp38-none-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 98151c8cf2a3919977b8bf261ac5b7cf63b2d15bbf8c2acc372ab05526a0d0d8 |
|
MD5 | b4494e5e3c133165ef5818014b83315a |
|
BLAKE2b-256 | e50993c1aa833b00b1512e3b950bb27d4733d9a2ca319f055580f37db8d89382 |
Hashes for polygons-0.3.3-cp38-cp38-manylinux_2_34_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | bbd67f4f22398a6a648c9980ff38487b7ff1a1946cadde78439e28f9a8da05f7 |
|
MD5 | 3f46fe98412d5e303e13f5045b5c8c14 |
|
BLAKE2b-256 | 7ebd5a09e06a76a9e636f3e026455b846a0f73ab9a930d0232831b40b6e84b3c |
Hashes for polygons-0.3.3-cp38-cp38-macosx_10_12_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | dc33d6c932bc6dd22e47103ac5ac0f1d9db6ce53489f500adf19aab5101704d9 |
|
MD5 | 7bdb1f2357f7eae254b416d7382017b8 |
|
BLAKE2b-256 | d46ca19ce26dab5691e763d0d03ba5d6898d2ea4e6cc97de271a74e92f828e68 |