有效边界逼近

Question

假设我在数组中表示了以下结构：

​

蓝色细胞代表“边界”，红细胞代表结构起源。我有一个函数来计算每个内部细胞(不是边界的细胞)到其最近的边界和原点的距离。

目前，我使用嵌套的for循环来完成这个任务，它实际上测试所有单元格到我当前位置的位置，并选择距离最小的单元格，该单元格也标记为边界单元格。

对于小数据集，这是可以的，但当您有大量可能的点来迭代时，速度会缓慢得令人痛苦。

我正在寻找一个解决方案，这将是更快，但交易的准确性。目前，我能够将最接近的边界单元返回到任何给定的内部单元，但我只需要一个最接近的单元格。

数组中的每个单元格已经具有以下信息：

• 任意位置(用于计算距离)
• 是一个边界单元
• 邻居列表(任何共享边缘的单元格)

要注意的事情：

• 该结构不一定符合任何特定的多边形形状。
• 数组不一定以任何逻辑方式排序
• 该阵列是平坦的(即1D)。

我想出了可能的解决方案(但没有经过测试)：

• A*方法(每个单元都知道它的邻居，我可以这样做，但我认为这会比我目前的蛮力方法更糟糕
• 优先级队列，从最小到最大的距离(但不确定如何实现最接近的边界)。

Answer 1

我假设这些细胞是不相关的。一切都取决于细胞中的区分点。找出到原点的距离是一种计算，不能改进。所以你的问题减少到:你有红点和白点(坚持你的配色方案)，你想找到最接近每个白点的蓝色点。

这是https://en.wikipedia.org/wiki/Nearest_neighbor_search的一个版本。关于这个问题有大量的文献，也有变体，例如近似最近邻搜索。这是一篇可以引导你找到其他人的论文：

康纳迈克尔还有皮尤什·库马尔。“飞机上实用的最近邻搜索”大海。2010年。(斯普林格链.)

底线是，通过适当的数据结构，可以实现每个白点的O(log )查询时间，这比简单的线性搜索要快得多。