1

在每一帧的实验中，我有一些点可以说明行人的头部。我需要计算特定区域中的 Voronoi 细胞 - 测量正方形：

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

所以我改编了一个从点生成 Voronoi 细胞的样本+ 我添加了测量区域（蓝线）和墙壁（黑色），这是第 0 帧的结果：

绘制的 Voronoi 单元的第 0 帧

这是代码的一部分（改编自示例）：

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()

据我所知，为了计算哪些单元格在测量区域内，我需要检查哪些单元格线与测量正方形交叉或在其内。因此，根据scipy.spatial.Voronoi 的文档，有趣的属性是：vertices，它返回那些橙色顶点。我还需要在测量区域内有顶点的边缘，根据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 细胞？

4

1 回答 1

2

我相信您最好的选择是使用某种多多边形相交算法，使用单元顶点来描述多边形。

您可以通过丢弃最右边的顶点在蓝色矩形的左侧、最左边的顶点在右边的多边形来减少多边形的数量，以此类推。这只剩下黄​​色多边形。

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

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

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

在此处输入图像描述

伪算法将是：

  • 对于所有 Voronoi 细胞：
    • 获取顶点列表。
    • 它们都是矩形的左/下/上/右吗？
    • 是：此单元格不相交。继续。
    • 对于所有顶点加上单元中心：
      • 这个点在矩形内吗？
      • 是的：我们有交叉点。报告此单元格并继续。
    • 在 Delaunay 中心以顶点为顶点的三角形列表中分解单元格，并采用有序的顶点对。
    • 对于每个三角形
    • 此单元格不与矩形相交。
于 2021-12-05T19:52:27.610 回答