Skip to main content

Fast points-in-polygon test and distances to polygons.

Project description

test status license badge link to Crates link to PyPI link to Zenodo/DOI

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

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

No source distribution files available for this release.See tutorial on generating distribution archives.

Built Distributions

polygons-0.3.3-cp312-none-win_amd64.whl (178.5 kB view hashes)

Uploaded CPython 3.12 Windows x86-64

polygons-0.3.3-cp312-cp312-manylinux_2_34_x86_64.whl (280.5 kB view hashes)

Uploaded CPython 3.12 manylinux: glibc 2.34+ x86-64

polygons-0.3.3-cp312-cp312-macosx_10_12_x86_64.whl (247.6 kB view hashes)

Uploaded CPython 3.12 macOS 10.12+ x86-64

polygons-0.3.3-cp311-none-win_amd64.whl (178.4 kB view hashes)

Uploaded CPython 3.11 Windows x86-64

polygons-0.3.3-cp311-cp311-manylinux_2_34_x86_64.whl (280.7 kB view hashes)

Uploaded CPython 3.11 manylinux: glibc 2.34+ x86-64

polygons-0.3.3-cp311-cp311-macosx_10_12_x86_64.whl (254.7 kB view hashes)

Uploaded CPython 3.11 macOS 10.12+ x86-64

polygons-0.3.3-cp310-none-win_amd64.whl (178.3 kB view hashes)

Uploaded CPython 3.10 Windows x86-64

polygons-0.3.3-cp310-cp310-manylinux_2_34_x86_64.whl (280.7 kB view hashes)

Uploaded CPython 3.10 manylinux: glibc 2.34+ x86-64

polygons-0.3.3-cp310-cp310-macosx_10_12_x86_64.whl (254.7 kB view hashes)

Uploaded CPython 3.10 macOS 10.12+ x86-64

polygons-0.3.3-cp39-none-win_amd64.whl (178.6 kB view hashes)

Uploaded CPython 3.9 Windows x86-64

polygons-0.3.3-cp39-cp39-manylinux_2_34_x86_64.whl (281.2 kB view hashes)

Uploaded CPython 3.9 manylinux: glibc 2.34+ x86-64

polygons-0.3.3-cp39-cp39-macosx_10_12_x86_64.whl (254.7 kB view hashes)

Uploaded CPython 3.9 macOS 10.12+ x86-64

polygons-0.3.3-cp38-none-win_amd64.whl (178.1 kB view hashes)

Uploaded CPython 3.8 Windows x86-64

polygons-0.3.3-cp38-cp38-manylinux_2_34_x86_64.whl (281.0 kB view hashes)

Uploaded CPython 3.8 manylinux: glibc 2.34+ x86-64

polygons-0.3.3-cp38-cp38-macosx_10_12_x86_64.whl (254.4 kB view hashes)

Uploaded CPython 3.8 macOS 10.12+ x86-64

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page