algorithm - 计算 'local convex hulls'并集的快速算法

Question

我有一组二维点，我想从中生成一个多边形(或多边形集合)来勾勒出这些点的“形状”，使用以下概念:

对于集合中的每个点，计算该点半径 R 内所有点的凸包。对每个点执行此操作后，将这些凸包合并以生成最终形状。

实际构建所有这些凸包的蛮力方法类似于 O(N^2 + R^2 log R)。是否有已知的、更有效的算法来产生相同的结果？或者可能是表达问题的不同方式？

注意:我知道 alpha 形状，它们是不同的；我正在寻找一种算法来执行上述内容。

---

以下解决方案无效 - 在 MATLAB 中被实验证明无效。

<罢工>更新:我有一个建议的解决方案。

命题:对点集进行Delaunay三角剖分，去掉所有外接半径大于R的三角形，然后对剩余的三角形进行并集。

Answer 1

A sweep line algorithm可以改进对 R 邻居的搜索。或者，您可以只考虑在宽度为 R 的正方形网格的相邻正方形中的点对。这两种想法都可以摆脱 N^2 - 当然前提是点相对稀疏。

我相信，即使点不稀疏(如 Olexiy 的示例)，扫描和凸包查找 cat 的巧妙组合也可以摆脱 N^2，但无法提出具体的算法。