是否有一种算法可以针对给定的 2d 位置找到由 n - 1 条线段(n 线顶点)组成的 2d 折线上的最近点在常数时间内？天真的解决方案是遍历所有段，测试每个段到给定位置的最小距离，然后对于最近的段，计算到给定位置的精确最近点，其复杂度为 O(n)。不幸的是，硬件限制阻止我使用任何类型的循环或指针，这意味着也没有像四叉树这样的优化来对 O(log n) 中最近的段进行分层查找。
理论上我有无限的时间来预先计算任何可用于查找的数据结构，并且这种预先计算可以任意复杂，只有运行时查找本身需要在 O(1) 中。然而，硬件的第二个限制是我只有非常有限的内存，这意味着为域的每个数字可能位置找到线上最近的点并将其存储在一个巨大的数组中是不可行的。换句话说，内存消耗应该在 O(n^x)。
因此归结为一个问题，如何在没有任何循环的情况下找到给定 2d 位置的多段线或其索引的最近段。这可能吗？
编辑:关于给定的位置……它可以是相当任意的，但只考虑直线附近的位置是合理的，由恒定的最大距离给定。
最佳答案
创建一个轴对齐的框，其中包含所有带有一些填充的线段。将其离散化为整数索引的 WxH 网格。对于每个网格单元，计算最近的线段，并将其索引存储在该网格单元中。
要查询一个点，在 O(1) 时间内计算它落在哪个网格单元格中。查找最近线段的索引。执行标准 O(1) 算法以准确计算直线上最近的点。
这是一个 O(1) 几乎精确的算法，它将占用 O(WH) 空间，其中 WH 是网格中的单元格数。
例如，这里是一些线段强加的空间的分割:
这是空间的 9x7 平铺，其中每种颜色对应一个边缘索引:红色 (0)、绿色 (1)、蓝色 (2)、紫色 (3)。注意空间的离散化是如何引入一些误差的。您当然会使用更精细的空间分割来尽可能多地减少该错误，但代价是必须存储更大的网格。这种粗糙的平铺仅用于说明。
您可以保持算法的复杂度为 O(1)，并通过获取查询点、识别它所在的单元格，然后查看该单元格之外的 8 个相邻单元格，使其更加精确。确定这 9 个单元格标识的边集。 (该集合最多包含 9 条边。)然后为每条边找到最近的点。然后保留那些(最多 9 个)最近点中最接近的点。
无论如何，对于某些病理情况，这种方法总是会失败，因此您必须考虑到这一点才能决定是否要使用它。
关于algorithm - 在常数时间内找到折线上最近的 2d 点，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34795628/