2

我在无限（嗯，双精度）二维平面上有一组点。

给定这个集合的凸包，如何在凸包内部找到一些与输入集中所有点相对较远的点？

在下图中，黑点是原始集合的一部分，阴影区域表示如果我们以半径 R“增长”所有点所占据的空间。

橙色点是我想要得到的例子。它们到底在哪里并不重要，只要它们离所有黑点相对较远。

最远点搜索 http://en.wiki.mcneel.com/content/upload/images/point_far_search.png

更新：使用 delaunay 算法查找大的空三角形似乎是一个很好的方法： Delaunay 解决方案 http://en.wiki.mcneel.com/content/upload/images/DelaunaySolutionToInternalFurthestPoints.png

4

2 回答 2

1

这是一个简单的算法：

  1. 获取凸形内的点列表。
  2. 其中，找到到任何其他点的最小距离。
  3. 按各自的 R 值对所有点进行排名
  4. 选择前 x 个点。

对于（2），将其视为半径搜索仍然意味着您最终会计算每个点到其他点的距离，因为找出一个点是否位于另一个点的给定半径内与找到距离是一回事点之间。

为了优化搜索，您可以将空间划分为一个网格，并将每个点分配给一个网格位置。然后，您对上述 (2) 的搜索将首先在同一个方格内和周围的 8 个方格内进行检查。如果到另一个点的最小距离在同一个正方形内，则返回该值。如果它来自 8 个中的一个，并且距离使得 9 个之外的点可能更近，那么您必须检查 9 个之外的网格位置的下一个轮廓是否比 9 个中找到的更接近。冲洗/重复.

于 2009-09-25T00:30:59.777 回答
1

这是可以使用KD-Trees解决的问题的一个很好的例子……在 Numerical Recipes 3rd Addition 中有一些很好的注释。

如果您试图找到相对孤立的点位置......也许最大的四边形元素的中心将是一个很好的候选者。

创建 KD-Tree 的复杂度为 O(n log^2 n)，而创建四边形大小的排序列表的复杂度为 O(n Log n)。即使是大量积分似乎也是合理的（当然，取决于您的要求）。

于 2009-09-25T01:04:32.860 回答