有效找出哪些3D线与哪些3D点相交

Question

给出

1. 3D空间中的许多点的集合（每个表示为3个浮点坐标(x, y, z)）
2. 一组3D空间中的许多无穷线（每个都由直线上的任意点和3D方向矢量表示）

有没有一种方法可以找出哪些点位于哪条线（对浮点误差有一点容忍度]，这比普通的O(n²)测试方法更有效嵌套循环中每条线的每个点？

我正在考虑将两组中的一组存储在特殊的数据结构中，这有助于进行相交测试。但是这样的数据结构是什么样的？

（也感谢相关学术文献的链接。）

Answer 1

将3d空间划分为N边的多维数据集，以便一个多维数据集可以包含多个点。无限线将与无限数量的立方体相交，但是检查立方体是否具有点需要O（1）。当一条线与一个具有多个点的多维数据集相交时，您仅检查该多维数据集中的点，如果1）它们均匀分布2）您正在使用摊余常数（[[ C0]）。从平均方案的角度来看，如果所有点都装在一个多维数据集中，则仅一次检查O（N ^ 2）处的所有点。您也可以在多维数据集内放置多维数据集，但这更多的是记账。

[这个想法是受四叉树启发的：Constant Amortized Time

我得到了零个被接受的答案...因此，请带着一点盐，或者接受我的答案并帮助一个朋友：）

Answer 2

这是Pinhead答案的补充。

考虑https://en.wikipedia.org/wiki/Quadtree点的边界框，假定其大致为三次方，然后将其细分为P单元格。如果这些点的散布均匀，则每个单元平均将包含C³个点。

现在，对于每一行，您都可以通过类似于绘制数字线的过程找到与之相交的所有像元，并且您将平均与P/C³个像元相交，其中αC是一个小常数。因此，搜索的总工作量与α成正比。

无论如何，您必须考虑网格的初始化时间，与L P/C³成比例。因此，包括初始化在内的总数为C³形式，并由C³+ ß L P/C²最小化，从而使时间和空间复杂度C~(L P)^(1/5)大大超过了O((L P)^(3/5))。

---

您还可以想到一个二叉树，其中包含键合球的层次结构，从每个点周围的公差半径开始。您可以通过在某个维度上递归细分来创建树，方法与创建kD树的方法相同。

要精确估计加速比要困难得多，但是您可能会期望像O(L P)这样的时间复杂度。