高效边界近似
Efficient Boundary Approximation
假设我在一个数组中表示以下结构：
蓝色单元格代表"boundaries"，红色单元格代表结构起源。我有一个函数可以计算每个内部单元格（不是边界的单元格）到其最近边界和原点的距离。
目前，我使用嵌套的 for 循环执行此操作，该循环实质上是将所有单元格位置测试到我的当前位置，并选择距离最小的单元格，该单元格也被标记为边界单元格。
对于小型数据集，这没问题，但是当您有大量可能的点要遍历时，这会变得非常慢。
我正在寻找一种速度更快但交易准确性更高的解决方案。目前我能够 return 最接近任何给定内部单元格的边界单元格，但我真的只需要一个最接近的单元格的近似值。
数组中的每个单元格已经有以下信息：
- 任意位置（用于计算距离）
- 是边界单元格
- 邻居列表（共享边的任何单元格）
注意事项：
- 该结构不一定符合任何类型的特定多边形形状
- 数组不一定以任何逻辑方式排序
- 阵列是平面的（即一维）
我想到的可能的解决方案（但尚未测试）：
- A* 方法（因为每个细胞都知道它的邻居，所以我可以这样做，但我认为它的性能比我目前的蛮力方法更差
- 一个优先队列，从原点的距离从最小到最大排序（但不确定如何实现近似最近的边界）
我假设细胞是无关紧要的。一切都取决于细胞中的区别点。找到到原点的距离是一种计算，无法改进。所以你的问题减少到：你有红点和白点（坚持你的配色方案），你想找到最接近每个白点的蓝点。
这是 nearest-neighbor search 的一个版本。有广泛的
关于这个问题的文献，以及近似最近邻搜索等变体。这是一篇可以引导您找到其他文章的论文：
Connor, Michael, and Piyush Kumar. "Practical Nearest Neighbor Search in the Plane." SEA. 2010. (Springer link.)
最重要的是，通过适当的数据结构，您可以实现
O(log n) 每个白点的查询时间，这比朴素的线性搜索快得多。
假设我在一个数组中表示以下结构：
蓝色单元格代表"boundaries"，红色单元格代表结构起源。我有一个函数可以计算每个内部单元格（不是边界的单元格）到其最近边界和原点的距离。
目前，我使用嵌套的 for 循环执行此操作，该循环实质上是将所有单元格位置测试到我的当前位置，并选择距离最小的单元格，该单元格也被标记为边界单元格。
对于小型数据集，这没问题，但是当您有大量可能的点要遍历时，这会变得非常慢。
我正在寻找一种速度更快但交易准确性更高的解决方案。目前我能够 return 最接近任何给定内部单元格的边界单元格，但我真的只需要一个最接近的单元格的近似值。
数组中的每个单元格已经有以下信息：
- 任意位置（用于计算距离）
- 是边界单元格
- 邻居列表（共享边的任何单元格）
注意事项：
- 该结构不一定符合任何类型的特定多边形形状
- 数组不一定以任何逻辑方式排序
- 阵列是平面的（即一维）
我想到的可能的解决方案（但尚未测试）：
- A* 方法（因为每个细胞都知道它的邻居，所以我可以这样做，但我认为它的性能比我目前的蛮力方法更差
- 一个优先队列，从原点的距离从最小到最大排序（但不确定如何实现近似最近的边界）
我假设细胞是无关紧要的。一切都取决于细胞中的区别点。找到到原点的距离是一种计算，无法改进。所以你的问题减少到：你有红点和白点（坚持你的配色方案），你想找到最接近每个白点的蓝点。
这是 nearest-neighbor search 的一个版本。有广泛的 关于这个问题的文献，以及近似最近邻搜索等变体。这是一篇可以引导您找到其他文章的论文：
Connor, Michael, and Piyush Kumar. "Practical Nearest Neighbor Search in the Plane." SEA. 2010. (Springer link.)
最重要的是，通过适当的数据结构，您可以实现 O(log n) 每个白点的查询时间，这比朴素的线性搜索快得多。