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.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):
@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.0-cp39-none-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 807527b452bfa7e3aa1895d6c2035f6df7d1c8c9372dca5ef2ad930b8ccd6248 |
|
MD5 | 0fe26ed71d81e29ec1b7f4bcd5660d46 |
|
BLAKE2b-256 | 3eeb1f56046b05786ba928380722b2899115aa542a3b2cc1d83a47bc130c5aab |
Hashes for polygons-0.3.0-cp39-cp39-manylinux_2_24_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c003ab0ee3992147c38f7209566a353b4ca0abd03cfc3062d03e5382b58e5490 |
|
MD5 | b71230e87601a0afee22cdc32cfc73f6 |
|
BLAKE2b-256 | eff65fd5c90f8128706788d2901e8fbc395023c314e3bcac781272e639a01010 |
Hashes for polygons-0.3.0-cp39-cp39-macosx_10_7_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b3d399d7e688d4a682710f4271264b16cc704d1012024b29967b1c15e27d488e |
|
MD5 | ddd73146882669a49ce43b1d65b78c07 |
|
BLAKE2b-256 | 501ae448cc0c72d05834191a5be92b5843fe9f41bd89d42df5e18638b8c615a4 |
Hashes for polygons-0.3.0-cp38-none-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 84bd52db73b9e5222145b86f3d813c8aeab1b5116ce18668641c6eaa57d9c155 |
|
MD5 | 6359d376eadc9ebac74c93f06e9c2f14 |
|
BLAKE2b-256 | 571822d08ae08cc58ca142c6a636d0fe15f66b2208d663b3c21cc117c84f5866 |
Hashes for polygons-0.3.0-cp38-cp38-manylinux_2_24_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6323ea9c7226a384b3025912b49fc3d07120790190e973bfa7ec72c2e6d27de4 |
|
MD5 | f3721ee596ac193a2ed1e4da461c423c |
|
BLAKE2b-256 | 53e68774ae8843f49337b3396575bc95a32cdfa11abe2f736d16330ec1c5ee46 |
Hashes for polygons-0.3.0-cp38-cp38-macosx_10_7_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 12de18953feed19abca4fbbef4401e452df2ce42040b1ab97d1579e3532735d0 |
|
MD5 | 3c4b52535f23a397b9d8520b3d2d4ff0 |
|
BLAKE2b-256 | 04b765b027485891bcf6e7b233d73b99f0b4eef6edabae22e4f998d1205c303e |
Hashes for polygons-0.3.0-cp37-none-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e9e8892abde713e70acfbd4b817dc0751aaf5da89375fa22ff7627845c56e30c |
|
MD5 | cc68f2b2cf5522ea2fc7580b06fd009a |
|
BLAKE2b-256 | 19a9a0add4b8bbf19cf570d522b69740960ee69d637af53d021924d038a9f7f6 |
Hashes for polygons-0.3.0-cp37-cp37m-manylinux_2_24_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | bb0a854e8871fd0322bbaa9def4724162c29c2d6d5390b9498e9f7139218563c |
|
MD5 | 42b3a6b7fbecb75c31c0114b0ad5f98d |
|
BLAKE2b-256 | 64b5ecdd1f9f901f8f73c9664325f09af0179be9b5b4635a7d1fbf22c4b5db9b |
Hashes for polygons-0.3.0-cp37-cp37m-macosx_10_7_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ed79ca4f15aa722405e8df8ef9a1a7d03d2f064f949a2a28e636d2f73b9c45da |
|
MD5 | 6395bd22251ee33e882512dce12d5d0d |
|
BLAKE2b-256 | e5a8a22ecd297c298829ca3f0fcb8d843410f186d277e9f6065694719ed7bde5 |
Hashes for polygons-0.3.0-cp36-none-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | cbac19bb0effc26af94a9cd06fceb6533c5345fd3a33a079eadc01e7a983d81e |
|
MD5 | e2084b61102ff37fb841fa2ebe1f1ccd |
|
BLAKE2b-256 | 006a80744df1123315ed234ecc1b4103342e5e47e1f5c0b219091530d8aaae1a |
Hashes for polygons-0.3.0-cp36-cp36m-manylinux_2_24_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8b66a7f22600ade464715dfac92d196401ca39bb65a16913e1394d5dcd87fd99 |
|
MD5 | cf7870f6b5d265abc1720f3c28a594d5 |
|
BLAKE2b-256 | 39056801dc942c2eee6c6901924f179a0d8160af98a734a4181d1f08cd6730ff |
Hashes for polygons-0.3.0-cp36-cp36m-macosx_10_7_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 042320c29499088029c9f306adb47f86b9782e728b244424a208d318ae89112a |
|
MD5 | a575404e8d14658a30ba5dcda517b122 |
|
BLAKE2b-256 | 040e29e2d49dd6436e94dce2b9268b7b0f469737cc59c7906e5e0abe89054d81 |