如何查询所有位于aline的点

Question

假设我有一组积分,

然后我定义了行L.如何获得b,d和f？

这可以用kd-tree解决(略有修改)？

== ==编辑

我的程序如何工作:

1. 定义一组点
2. L后面定义,它与点集无关

我现在唯一的想法:

1. 获得L线的中间点m
2. 基于点m,使用KD-Tree获取长度(L)/ 2半径内的所有点
3. 对于每个点,测试它是否位于L行
4. 如果某些点稍微位于查询行上,我可能会添加共线阈值.

我的方法的运行时间取决于L长度,线越长,查询越大,需要检查的点数越多.

Answer 1

您可以进行对数时间查找.我的算法以巨大的内存使用量(高达立方数的点数)为代价来实现:

如果您事先知道线的方向,则可以非常容易地实现对数时间查找:a*x + b*y = c设为线的等式,然后a / b描述方向,并c描述线的位置.对于每一个a,b(除[0, 0])和点,c是唯一的.然后根据它们的值对点进行排序c为索引; 当你得到这条线时,在这个索引中搜索.

如果你的所有行都是正交的,它需要两个索引,一个用于x,一个用于y.如果使用四个索引,也可以按45°的线条查找.你不需要准确的方向; 如果您知道所有点的边界区域,则可以搜索平行于跨越边界区域内查询线的索引方向的条带中的每个点:

_{以上段落将"方向"定义为比率a / b.然而,这产生无限比率.一个更好的定义定义的"方向"为一对(a, b),其中的至少一个a,b是非零和两对(a1, b1),(a2, b2)定义相同的方向IFF a1 * b2 == b1 * a2.然后{ (a / b, 1)for bnonzero,(1, 0)for bzero}是描述方向空间的一种特殊方式.然后我们可以选择(1, 0)"无穷远处的方向",然后按照第一个分量排序所有其他方向.}

注意浮点不准确.建议使用有理算法.如果选择浮点运算,请务必在检查点线入射时使用epsilon比较.

算法1:只需选择一些值n,准备n索引,然后在查询时选择一个.不幸的是,缺点很明显:查找仍然是范围扫描,因此是线性的,并且随着方向越来越远离索引的速度,预期的加速下降.如果边界区域比大多数点的区域大得多,那么它也没有提供任何有用的东西(你可以分别从密集区域中搜索极值点).

理论查找速度仍然是线性的.

为了以这种方式实现对数查找,我们需要每个可能方向的索引.不幸的是,我们不能拥有无限多的索引.幸运的是,类似的方向仍然会产生类似的指数 - 只有少数交换的指数不同.如果方向足够相似,它们将产生相同的索引.因此,我们可以在整个方向范围内使用相同的索引.即,只有两个不同点位于同一条线上的方向才能引起索引的变化.

算法2以巨大的索引为代价实现了对数查找时间:

准备时:

• 对于每对点(A,B),确定从A到B的方向.将方向收集到有序集中,将集合称为重要方向集.
• 将此设置转换为列表,并在两端添加"无穷远方向".
• 对于每对连续的重要方向,选择该范围内的任意方向,并为该方向准备所有点的索引.将索引收集到列表中.不要在此索引中存储任何特定的键值,只能引用点.
• 为这些索引准备索引,其中方向是关键.

在按行查找点时:

• 确定线方向.
• 在索引索引中查找正确的点索引.如果线方向落在两个范围之间的边界,则任意选择一个.如果没有,您可以保证在线上最多找到一个点.
  由于只有O(n^2)重要的方向,因此O(n^2)该指数中有范围.查找将花费O(log n)时间找到正确的.
• 使用相对于线方向的位置作为键,查找该范围的索引中的点.这种查找需要O(log n)时间.

如果"无穷远处的方向"不在重要方向之间,则第一个和最后一个索引是相同的,因此可以获得轻微的改进.可以根据使用的索引进行进一步的改进.进入点数组的索引数组非常紧凑,但如果使用二进制搜索树(例如红黑树或AVL树)作为点索引,则可以通过合并相同的子树来进一步改进值通过引用相同.