快速查询线路的数据结构？

Question

4

我知道可以使用KD-Tree来存储点并快速迭代与另一个给定点接近的一小部分点。我想知道是否有类似于此的东西用于线段。

给定在3D中的一组线段L（要存储在该数据结构中）和另一条“查询线”q，我希望能够快速迭代所有靠近q的线段L。我计划使用的距离是两个点u和v之间的最小欧几里得距离，其中u是第一条线上的某个点，v是第二条线上的某个点。计算这个距离不是问题（有一个很好的技巧涉及到叉积）。

也许你们有好的想法或知道在哪里寻找论文、描述等等...

谢谢！ s.

- sellibitze

除非这些线段平行，否则该距离始终为0。或者你是在说线段吗？ - Thomas

其实无所谓。如果需要的话，我可以将它们变为线段。但是无限长度的直线也没关系。我不期望结果会有改变。我目前使用两个点来参数化我的线段，并且我希望点u/v会在这些线段上。 - sellibitze

1

嗯，在三维空间中，两条线段如果不平行，就不能相交，因为它们可能在不同的平面上。 - Matthieu M.

抱歉，我漏掉了“3D”这一部分。现在一切都清楚了。 - Thomas

顺便说一下，这是一个有趣的问题。 - Thomas

2个回答

3

您也可以使用KD-Tree进行此操作。

有可能构建一个基于原语而非点的KD-Tree。许多光线追踪器都这样做，以使三角形碰撞测试更快。我见过的最好的描述在这里ray tracing tutorial。

一种潜在的更快但不完全准确的解决方案是仅针对每个线段保留点列表，并将其插入到标准基于点的KD-Tree中。找到最近的点，然后用该线段标记它们，并使用它来获取最近的线段。这很粗糙，但通常比其他选项快得多。"诀窍"是找到保持线段上点之间的大空间（更快）与将线段分成更多点（更慢但更准确）之间的正确平衡。

- Reed Copsey

+1 感谢您的建议。我需要检查您提供的链接并考虑一下。 - sellibitze

不必在每个叶子节点中存储点，我可以存储线段并将这些线段分割。无论哪种方式，我最终都会以某种方式冗余地存储该线。也许其他数据结构更合适（松散八叉树、R-Tree等）。 - sellibitze

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

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

- Nick Johnson · Accepted Answer

另一种选择 - 也是磁盘数据库系统中最常用的空间索引方式 - 是R-Tree。它比KD-Tree更复杂，但通常被认为更快，并且可以轻松索引线和多边形。