在常数时间内找到折线上最接近的二维点

Question

在常数时间内找到折线上最接近的二维点

algorithmdata-structures2dlinecomputational-geometry

3

是否有一种算法，可以在常数时间内找到二维位置上距离由n-1条线段（n个顶点）构成的二维折线中最近的点？朴素的解决方案是遍历所有线段，测试每个线段与给定位置的最小距离，然后对于最近的线段，计算到给定位置的确切最近点，这样的复杂度为O(n)。不幸的是，硬件限制阻止我使用任何类型的循环或指针，这也意味着不能使用诸如四叉树之类的优化来进行层次查找以在O(log n)内查找最近的线段。

我在理论上有无限的预计算时间来准备任何数据结构以供查找使用，这个预先计算可以是任意复杂的，只需在运行时进行的查找本身需要处于O(1)。然而，硬件的第二个限制是我只有非常有限的内存，这意味着为定义域中的每个可能的位置找到线路上的最近点并将其存储在一个巨大的数组中是不可行的。换句话说，内存消耗应该是O(n^x)。

因此，问题就变成了如何在没有循环的情况下找到二维位置上的折线的最近线段或其索引。这是可能的吗？

编辑：关于给定的位置...它可以是相当任意的，但合理的做法是仅考虑由常数最大距离给出的线附近的位置。

- mOfl

您的“line”通常被称为折线，这样可以减少一些混淆。 - Jim Mischel

你说内存消耗应该是O(n^x)。我知道n是顶点数。那么x是什么？n和x的合理范围是多少？你们的世界中x和y的范围是多少？例如，我需要支持查询位置[0,0]和[987654321,123456789]吗？让我们定义所有约束条件。 - Jim Mischel

3个回答

0

在编程中，你可以在O(1)的时间内找到一条直线上最接近的几何点，但这并不会告诉你哪个给定的顶点最接近它。对此，你能做的最好选择是二分查找，这需要循环或递归，时间复杂度为O(log n)。

如果你正在设计VLSI或FPGA，你可以并行评估所有顶点。然后，你可以比较相邻的顶点，并进行大规模的有线或运算来编码跨越最接近的几何点的线段索引。从技术上讲，根据有线或运算中元素的数量，你可能会获得一种近似为O(log n)的延迟，但这种情况通常被视为近似恒定。

- comingstorm

-1

您可以使用R-Tree来优化这种类型的搜索，它是一种通用的空间数据结构，支持快速搜索。它不是一个常数时间算法；它的平均情况是O(log n)。

您说过您可以预先计算数据结构，但您不能使用任何循环。然而，是否有一些限制阻止了任何循环？任意搜索不太可能命中现有数据点，因此它至少必须在树中向左和向右查找。

这个SO答案包含一些库的链接：

Java商业友好的R-tree实现？

- John Scattergood

感谢您的输入，我知道R-Tree。不幸的是，在我的情况下无法遍历R-Tree。否则，它将是首选工具。 - mOfl

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Timothy Shields · Accepted Answer

创建一个包含所有线段的单一轴对齐框，并添加一些填充。将其离散化为一个WxH整数索引网格。对于每个网格单元，计算最近的线段，并将其索引存储在该网格单元中。

要查询一个点，在O(1)时间内计算它落入哪个网格单元。查找最近线段的索引。执行标准的O(1)算法，以计算线上确切的最近点。

这是一个几乎精确的O(1)算法，将占用O(WH)空间，其中WH是网格中单元格的数量。

例如，这是一些线段所施加的空间细分：

这里是一个9x7的空间平铺，每种颜色对应一种边缘索引：红色（0）、绿色（1）、蓝色（2）、紫色（3）。请注意，空间的离散化会引入一些误差。当然，您可以使用更细的空间划分来将误差降低到任何程度，但代价是需要存储更大的网格。这种粗糙的平铺仅用于说明。

您可以保持算法的O(1)并通过将查询点识别为所在单元格，然后查看除该单元格外的8个相邻单元格来使其更加准确。确定这9个单元格所标识的边集（该集合最多包含9条边）。然后对于每条边找到最近的点。然后保留其中最近的一个（最多9个）最近点。无论如何，这种方法总会在某些病态情况下失败，因此您必须考虑这一点来决定是否要使用它。