如何计算Python中特定区域有哪些Voronoi单元格？

Question

我有一些点可以说明每帧 experiment 期间行人的头部。我需要计算特定区域中有哪些 Voronoi 元胞 - 测量方块：

x_range = (-0.4, 0.4)
y_range = (0.5, 1.3)

所以我调整了 a sample of generating Voronoi cells from points + 我添加了测量区域（蓝线）和墙壁（黑色），这是第 0 帧的结果：

这里是部分代码（改编自the sample）：

entries_for_frame = get_entries_at_frame(entries, frame)
points = points_from_entries(entries_for_frame)

vor = scipy.spatial.Voronoi(points)
scipy.spatial.voronoi_plot_2d(vor)

plt.show()

据我所知，为了计算哪些单元格在测量区域内，我需要检查哪些单元格线与测量方块交叉或在其内部。所以根据 documentation of scipy.spatial.Voronoi the interesting attributes are: vertices, which is returning those orange vertices. I need also to have edges of vertices inside the measurement area, the attribute according to the documentation of scipy.spatial.Voronoi 是 ridge_vertices，但不幸的是它返回了一些奇怪的东西：

[[0, 19], [0, 2], [1, 17], [1, 3], [2, 3], [17, 19], [-1, 22], [-1, 15], [15, 16], [16, 21], [21, 22], [-1, 0], [2, 23], [22, 23], [28, 32], [28, 29], [29, 30], [30, 31], [31, 32], [12, 13], [12, 28], [13, 25], [25, 29], [-1, 24], [-1, 31], [24, 30], [-1, 26], [26, 27], [27, 32], [-1, 33], [19, 20], [20, 34], [33, 34], [35, 36], [-1, 35], [36, 37], [-1, 37], [-1, 4], [4, 5], [5, 35], [6, 37], [6, 7], [7, 36], [38, 39], [38, 40], [39, 41], [40, 41], [-1, 40], [-1, 8], [8, 38], [-1, 9], [9, 10], [10, 41], [10, 43], [39, 42], [42, 43], [52, 53], [52, 57], [53, 54], [54, 55], [55, 56], [56, 57], [13, 52], [25, 57], [48, 49], [48, 54], [49, 55], [9, 50], [24, 56], [49, 50], [17, 59], [18, 61], [18, 20], [59, 61], [11, 46], [11, 60], [18, 47], [46, 47], [60, 61], [58, 63], [58, 60], [59, 62], [62, 63], [26, 64], [27, 65], [64, 65], [21, 67], [23, 68], [67, 68], [42, 45], [43, 69], [44, 45], [44, 72], [69, 72], [50, 70], [69, 70], [48, 71], [70, 71], [4, 76], [5, 75], [75, 76], [33, 77], [76, 77], [34, 78], [77, 78], [47, 79], [78, 79], [80, 82], [80, 81], [81, 83], [82, 84], [83, 84], [14, 53], [14, 80], [71, 82], [72, 84], [14, 51], [51, 87], [81, 85], [85, 87], [88, 90], [88, 89], [89, 93], [90, 91], [91, 92], [92, 93], [44, 88], [83, 89], [85, 86], [86, 93], [11, 91], [58, 92], [94, 95], [94, 97], [95, 96], [96, 98], [97, 99], [98, 99], [12, 94], [51, 95], [65, 97], [101, 104], [101, 102], [102, 103], [103, 105], [104, 105], [15, 101], [16, 104], [64, 102], [99, 103], [66, 67], [66, 105], [1, 106], [3, 107], [106, 107], [68, 108], [107, 108], [8, 73], [45, 109], [73, 110], [109, 110], [111, 115], [111, 113], [112, 113], [112, 114], [114, 115], [46, 74], [74, 111], [79, 113], [75, 112], [7, 114], [116, 117], [116, 118], [117, 120], [118, 119], [119, 121], [120, 121], [96, 118], [98, 100], [100, 116], [87, 119], [86, 121], [63, 120], [122, 127], [122, 123], [123, 124], [124, 125], [125, 126], [126, 127], [100, 127], [117, 122], [62, 123], [106, 124], [108, 125], [66, 126], [128, 129], [128, 130], [129, 132], [130, 131], [131, 133], [132, 134], [133, 134], [90, 128], [109, 129], [74, 130], [110, 132], [115, 131], [6, 133], [73, 134]]

在文档中我看不到如何理解返回的数字。还在教程中解释如何解决我的问题。 所以我的问题是：如何计算哪些Voronoi元胞在至少单点的测量区域内？

Answer 1

我相信您最好的选择是使用某种 multiple polygon intersection algorithm 使用单元格顶点来描述多边形。

您可以减少多边形的数量，方法是丢弃最右边的顶点在蓝色矩形左侧的多边形、最左边的顶点在右边的多边形，依此类推上下。这只剩下黄色多边形。

您也可以快速消除（只是，在这种情况下您将它们标记为“相交”）所有中心或顶点位于矩形内的那些。这也很快。

在这个示例中，这足以定位所有单元格。

在其他情况下（例如，在下图中，如果左下角的黄色单元格稍微向上移动）您将拥有所有顶点和矩形外的 Delaunay 中心的单元格，但有一条边交叉它，所以是一个交叉路口。要识别这些，您可以利用矩形是凸形这一事实，并检查在您留下的单元格中是否有一个至少包含矩形的一个角。这是一个稍微复杂的检查（“一个点是否位于凸多边形内”），但并不复杂，因为单元格也是凸的并且可以简单地分解成三角形。

伪算法为：

对于所有 Voronoi 单元：
- 获取顶点列表。
- 都是left/below/above/right的长方形吗？
- YES：此单元格不相交。继续。
- 对于所有顶点加上像元中心：
  - 这个点在矩形内吗？
  - 是：我们有交集。报告此小区并继续。
- 分解三角形列表中的单元格，顶点在 Delaunay 中心，采用有序的顶点对。
- 每个三角形
  - 对于矩形的每个顶点
    - is the vertex inside the triangle?
    - 是：我们有交集。报告并继续
- 此单元格不与矩形相交。

如何计算Python中特定区域有哪些Voronoi单元格？

How to calculate which Voronoi cells are in specific area in Python?

python

voronoi

cell

scipy-spatial