多边形：快速多边形内点测试和到多边形的距离

计算到多边形边和顶点的距离，并可以检查点是否在内部/外部。

此库针对处理数百或数千个多边形以及数千或数百万个点进行了优化。

示例时间（190个多边形，1 M 个参考点，在 i7-10710U 上运行）

• 到最近边的距离：0.7 秒
• 到最近顶点的距离：0.6 秒
• 检查点是否在内部或外部：0.1 秒

使用 pip 安装

$ pip install polygons

支持的版本

• Python: 3.8 - 3.12
• 操作系统：Linux、macOS 和 Windows

功能

• 检查点是否在多边形内部或外部
• 到边的最近距离
• 到顶点的最近距离

推荐引用

如果您在程序或出版物中使用此工具，请认可其作者

@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 示例

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]

编码过程中使用的引用

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

开发笔记

运行基准测试

$ cargo test --release -- --ignored --nocapture

Python 接口灵感来源于 https://github.com/dev-cafe/rustafarian。

构建和测试 Python 接口

$ maturin develop

图像

使用 https://github.com/qrohlf/trianglify 生成社交媒体预览。