algorithm - 如何查询在线上的所有点

Question

假设我有一套观点，
然后定义线l，如何得到b，d，f？
可以用kd树（稍加修改）解决这个问题吗？
==编辑==
我的程序工作原理：
定义一组点
l是稍后定义的，它与点集无关
我现在唯一的想法是：
得到L线的中点m。
以m点为基础，用kd树求出长度（l）/2半径内的所有点
对于每一点，测试它是否在L线上
如果查询行上有一些点稍微倾斜，我可能会添加共线阈值。
我的方法的运行时间取决于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)定义相同的方向iffa1 * b2 == b1 * a2。那么{(a / b, 1)表示b非零，(1, 0)表示b零}是描述方向空间的一种特殊方式。然后我们可以选择(1, 0)作为“无穷远方向”，然后根据它们的第一个分量对所有其他方向进行排序。
注意浮点错误。建议使用有理算法如果选择浮点运算，请确保在检查点线关联时使用epsilon比较。
算法1：只需选择一些值n，准备n索引，然后在查询时选择一个。不幸的是，缺点是显而易见的：查找仍然是一个范围扫描，因此是线性的，并且随着方向离索引的方向越来越远，预期的加速比会下降。如果边界区域比大多数点所在的区域大得多，它也不会提供任何有用的信息（但是，可以从密集区域中单独搜索极值点）。
理论查找速度仍然是线性的。
为了以这种方式实现对数查找，我们需要为每个可能的方向建立索引。不幸的是，我们不能有无限多的索引。幸运的是，类似的方向仍然会产生类似的索引——这些索引只在很少的交换中有所不同如果方向足够相似，它们将产生相同的索引因此，我们可以对整个方向范围使用相同的索引也就是说，只有两个不同点位于同一条线上的方向才能引起指数的变化。
算法2以巨大的索引为代价实现对数查找时间：
准备时：
对于每对点（a，b），确定从a到b的方向。将方向集合成有序集合，将集合称为有效方向集合。
将此集合转换为列表，并在两端添加“无限方向”。
对于每对连续有效方向，选择该范围内的任意方向，并为该方向准备所有点的索引将索引收集到列表中不要在此索引中存储任何键的特定值，只引用点。
在这些索引上准备一个索引，其中方向是关键。
按直线查找点时：
确定线的方向。
在索引索引中查找右点索引。如果直线方向落在两个范围之间的边界处，则任意选择一个如果没有，你保证最多能在线上找到一个点。
由于只有O(n^2)显著方向，因此该指数存在O(n^2)范围。查找需要O(log n)时间才能找到正确的。
使用相对于线方向的位置作为键，在索引中查找此范围的点此查找将花费O(log n)时间。
如果“无穷远方向”不在有效方向中，则第一个和最后一个索引是相同的，因此可以获得轻微的改进。根据使用的索引，可以执行进一步的改进。索引数组到点数组非常紧凑，但是如果使用二叉搜索树（如red-black tree或AVL tree）作为点的索引，则可以通过将按值相同的子树合并为按引用相同的子树来做进一步的改进。