时间戳

首页 > 解决方案 > 根据点云的圆将区域划分为子区域

geometry - 根据点云的圆将区域划分为子区域

问题描述

我有一个边长为 lx（水平）和 lz（垂直）的矩形 R，面积为 A = lx*lz。在这个矩形中，有 N 个随机分布的点。我想将 A 分成 N 个子区域，其中每个子区域是根据点云每个点周围的半径增大的圆确定的。一旦两个生长圈相交，生成的激进线应该划定两个点的子区域之间的局部边界。矩形 R 的边界应另外界定子区域。

预期结果如下图所示： 6 点示例中的预期子区域

这部 Youtube 短片艺术性地说明了大致的过程： https ://www.youtube.com/watch?v=BXNvcQTNWXM&ab_channel=stopmotionkim

为了找到子区域，我正在寻找一种近似或精确的算法，它（第一优先级）是有效的并且可以很好地与 N 扩展（优于 O[N^2]，理想情况下是 O[N]，尽管我怀疑这是可能）和（第二优先级），如果近似，则尽可能准确。

有谁知道如何做到这一点或暗示如何开始？非常感谢你的帮助！

标签： geometrycomputational-geometryarea

解决方案

您正在寻找的是裁剪 Voronoi 图。它可以在 O(nlogn) 中计算。我建议您查看这些论文/课程，以更好地了解基础理论和计算方法：

3D裁剪Voronoi图
计算几何的高效计算

有关 Python 实现，请参阅这篇文章

推荐阅读