在恒定时间内在折线上找到最接近的2d点

Question

是否存在一种算法,对于给定的2d位置,在恒定时间内找到由n-1个线段(n个线顶点)组成的2d折线上的最近点？天真的解决方案是遍历所有段,测试每个段到给定位置的最小距离,然后对于最近的段,计算到给定位置的精确最近点,其具有O(n)的复杂度.不幸的是,硬件约束阻止我使用任何类型的循环或指针,这意味着也没有像四叉树这样的优化来对O(log n)中最近的段进行分层查找.

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

所以它归结为如何在没有任何循环的情况下找到2d位置的折线或其索引的最近段.这可能吗？

编辑:关于给定的位置......它可以是非常随意的,但仅考虑一条线的较近邻域中的位置是合理的,由恒定的最大距离给出.

Answer 1

创建一个单轴对齐的框,其中包含带有一些填充的所有线段.将其分解为整数索引的WxH网格.对于每个网格单元,计算最近的线段,并将其索引存储在该网格单元中.

要查询一个点,在O(1)时间内计算它所属的网格单元.查找最近的线段的索引.使用标准O(1)算法精确计算线上最近的点.

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

例如,以下是某些线段强加的空间细分:

这是一个9x7的空间平铺,每个颜色对应一个边缘索引:红色(0),绿色(1),蓝色(2),紫色(3).注意空间的离散是如何引入一些错误的.您当然会使用更精细的空间细分来将错误减少到您想要的数量,但代价是必须存储更大的网格.这种粗糙的平铺仅用于说明.

您可以保留算法O(1),并通过获取查询点,识别它所在的单元格,然后查看除该单元格之外的8个相邻单元格,使其更加精确.确定这9个单元格识别的边缘集合.(该组最多包含9个边.)然后,对于每个边找到最近的点.然后保持最接近的点(最多9个).

在任何情况下,对于某些病态情况,这种方法总是会失败,因此您必须将其考虑在决定是否要使用它.