在常数时间内找到折线上最近的 2d 点
Find closest 2d point on polyline in constant time
是否有一种算法可以针对给定的 2d 位置找到由 n - 1 条线段组成的 2d 折线上的最近点 (n 线顶点）在恒定时间内？天真的解决方案是遍历所有段，测试每个段到给定位置的最小距离，然后对于最近的段，计算到给定位置的精确最近点，其复杂度为 O(n)。不幸的是，硬件限制阻止我使用任何类型的循环或指针，这意味着也没有像四叉树这样的优化来对 O(log n) 中最近的段进行分层查找。
理论上我有无限的时间来预计算任何可用于查找的数据结构，并且这个预计算可以任意复杂，只有运行时的查找本身需要在 O(1) 中。然而，硬件的第二个限制是我只有非常有限的内存，这意味着为域的每个数字可能位置找到线上最近的点并将其存储在一个巨大的数组中是不可行的。换句话说，内存消耗应该在 O(n^x).
因此归结为一个问题，如何在给定 2d 位置的情况下找到折线的最近线段或其索引，而没有任何循环。这可能吗？
编辑：关于给定的位置……它可以是相当任意的，但只考虑直线附近的位置是合理的，由恒定的最大距离给出。
您可以使用 R-Tree 优化此类搜索，它是支持快速搜索的通用空间数据结构。这不是恒定时间算法；它的平均情况是 O(log n).
你说你可以pre-calculate数据结构，但是你不能使用任何循环。但是是否有一些限制可以防止任何循环？任意搜索不太可能命中现有数据点，因此它必须至少在树中左右查看。
这个 SO 答案包含一些指向库的链接：
Java commercial-friendly R-tree implementation?
您可以在 O(1) 时间内找到直线上最近的几何点，但这不会告诉您哪个给定顶点最接近它。你能做的最好的是二分查找，也就是 O(log n)，但当然需要循环或递归。
如果您正在设计 VLSI 或 FPGA，则可以并行评估所有顶点。然后，您可以比较邻居，并做一个大 wired-or 来编码跨越最近几何点的线段的索引。根据 wired-or 中元素的数量，技术上你会得到某种 O(log n) 延迟，但这种事情通常被视为 near-constant.
创建一个 axis-aligned 框，其中包含所有带有一些填充的线段。将其离散化为整数索引的 WxH 网格。对于每个网格单元，计算最近的线段，并将其索引存储在该网格单元中。
要查询一个点，在O(1)时间内计算它落在哪个网格单元格中。查找最近线段的索引。执行标准 O(1) 算法以准确计算直线上最近的点。
这是一个 O(1) almost-exact 算法，需要 O(WH) space，其中 WH 是网格中的单元格数。
例如这里是space一些线段强加的细分：
这是 space 的 9x7 平铺，其中每种颜色对应一个边缘索引：红色 (0)、绿色 (1)、蓝色 (2)、紫色 (3)。注意 space 的离散化是如何引入一些错误的。您当然会使用 space 的更精细的细分来尽可能多地减少该错误，但代价是必须存储更大的网格。这种粗糙的平铺仅用于说明。
您可以保持算法 O(1) 的复杂度，并通过获取查询点、确定它所在的单元格，然后查看除该单元格之外的 8 个相邻单元格，使算法的复杂度更高 almost-exact .确定这 9 个单元格标识的边集。 （该集合最多包含 9 条边。）然后为每条边找到最近的点。然后保留那些（最多9个）最接近的点中最接近的。
无论如何，对于某些病态情况，此方法总是会失败，因此您必须考虑到这一点才能决定是否要使用它。
是否有一种算法可以针对给定的 2d 位置找到由 n - 1 条线段组成的 2d 折线上的最近点 (n 线顶点）在恒定时间内？天真的解决方案是遍历所有段，测试每个段到给定位置的最小距离，然后对于最近的段，计算到给定位置的精确最近点，其复杂度为 O(n)。不幸的是，硬件限制阻止我使用任何类型的循环或指针，这意味着也没有像四叉树这样的优化来对 O(log n) 中最近的段进行分层查找。
理论上我有无限的时间来预计算任何可用于查找的数据结构，并且这个预计算可以任意复杂，只有运行时的查找本身需要在 O(1) 中。然而，硬件的第二个限制是我只有非常有限的内存，这意味着为域的每个数字可能位置找到线上最近的点并将其存储在一个巨大的数组中是不可行的。换句话说，内存消耗应该在 O(n^x).
因此归结为一个问题，如何在给定 2d 位置的情况下找到折线的最近线段或其索引，而没有任何循环。这可能吗？
编辑：关于给定的位置……它可以是相当任意的，但只考虑直线附近的位置是合理的，由恒定的最大距离给出。
您可以使用 R-Tree 优化此类搜索，它是支持快速搜索的通用空间数据结构。这不是恒定时间算法；它的平均情况是 O(log n).
你说你可以pre-calculate数据结构，但是你不能使用任何循环。但是是否有一些限制可以防止任何循环？任意搜索不太可能命中现有数据点，因此它必须至少在树中左右查看。
这个 SO 答案包含一些指向库的链接：
Java commercial-friendly R-tree implementation?
您可以在 O(1) 时间内找到直线上最近的几何点，但这不会告诉您哪个给定顶点最接近它。你能做的最好的是二分查找，也就是 O(log n)，但当然需要循环或递归。
如果您正在设计 VLSI 或 FPGA，则可以并行评估所有顶点。然后，您可以比较邻居，并做一个大 wired-or 来编码跨越最近几何点的线段的索引。根据 wired-or 中元素的数量，技术上你会得到某种 O(log n) 延迟，但这种事情通常被视为 near-constant.
创建一个 axis-aligned 框，其中包含所有带有一些填充的线段。将其离散化为整数索引的 WxH 网格。对于每个网格单元，计算最近的线段，并将其索引存储在该网格单元中。
要查询一个点，在O(1)时间内计算它落在哪个网格单元格中。查找最近线段的索引。执行标准 O(1) 算法以准确计算直线上最近的点。
这是一个 O(1) almost-exact 算法，需要 O(WH) space，其中 WH 是网格中的单元格数。
例如这里是space一些线段强加的细分：
这是 space 的 9x7 平铺，其中每种颜色对应一个边缘索引：红色 (0)、绿色 (1)、蓝色 (2)、紫色 (3)。注意 space 的离散化是如何引入一些错误的。您当然会使用 space 的更精细的细分来尽可能多地减少该错误，但代价是必须存储更大的网格。这种粗糙的平铺仅用于说明。
您可以保持算法 O(1) 的复杂度，并通过获取查询点、确定它所在的单元格，然后查看除该单元格之外的 8 个相邻单元格，使算法的复杂度更高 almost-exact .确定这 9 个单元格标识的边集。 （该集合最多包含 9 条边。）然后为每条边找到最近的点。然后保留那些（最多9个）最接近的点中最接近的。
无论如何，对于某些病态情况，此方法总是会失败，因此您必须考虑到这一点才能决定是否要使用它。