algorithm - 在 3 维中分段相交

Question

我们可以在 O(nlgn) 时间内解决 2D 中线段相交的问题。在这个问题中，我们得到了一组线段，我们必须看是否有交点。现在她是来自 CLRS 的问题。

问题。 Charon 教授有一套 n 根棍子，它们以某种方式相互叠放配置。每根棍子都由它的端点指定，每个端点都是一个有序的三元组，给出了它的 (x, y, z) 坐标。没有棍子是垂直的。他希望一次捡起所有的棍子，条件是只有当一根棍子上面没有其他棍子时他才可以捡起来。A。给出一个程序，它拿两根棍子 a 和 b 并报告 a 是否在上方、下方、或与 b 无关。b.描述一种确定是否可以拾起所有木棍的高效算法，如果可以，则提供一个合法的木棍拾取顺序。

我发现它是 3D 中线段相交的延伸。在 2D 中，扫描线在“y”方向移动，数组根据“x”坐标排序。我认为在 3D 中，扫描线应该在“z”维度上移动，但我现在不确定如何排序，因为我必须同时处理“x”和“y”。

如果我们以某种方式弄清楚，我想，如果存在交叉点，那么对于 (b) 部分，不可能选择所有的棍子。

我的方向对吗？？

Answer 1

可以在二维中使用线段相交来解决这个问题。

检查一段在另一段之上与检查 XY 投影中是否存在交点相同，如果它们相交则比较每个段上交点的 Z 坐标。例如。对于段 a=((0,0,0), (2,2,2)) 和 b=((0,2,3), (2,0,5) )，在 XY 上的投影是 ((0,0), (2,2)) 和 ((0,2), (2,0))。二维交集为(1,1)，(1,1)中的Z值对于a为1，对于b 是 4。这意味着 b 高于 a。

因此，使用 2D 中的线段交集来查找相关的线段。要查找删除段的顺序，请使用 topological sorting .