Jam*_*hen 1 python 3d geometry line-segment
只需检查\xef\xbc\x8c就不需要找到点了。
\n坐标 z 不= 0。\n堆栈溢出中的老问题都是关于 2d 的。\n提前感谢
有多种方法可以进行线-线相交测试。经典的方法是使用线性代数（即求解线性矩阵系统），但从软件开发的角度来看，我更喜欢几何代数方法，以普鲁克坐标的形式，它只需要实现向量代数运算（即，叉积和点积），这比求解线性系统的矩阵运算更容易编码。
\n\n向量代数解
\n\n给定由点 P1 和 P2 限定的线段 P 和由点 Q1 和 Q2 限定的线段 Q。
\n\n线的参数形式由下式给出：
\n\nP(t) = P1 + t (P2 - P1)
\n\nQ(t) = Q1 + t (Q2 - Q1)
\n\n其中t是区间[0 1]内的实数。
\n\n如果两条线相交，则以下等式成立：
\n\nP(t0) = Q(t1)
\n\n假设两个未知数t0和t1存在。将上式展开我们得到：
\n\nt0 (P2 - P1) - t1 (Q2 - Q1) = Q1 - P1
\n\n为了避免处理矩阵代数，我们可以尝试使用向量代数和替换方法来求解系统：
\n\nt0 (P2 - P1) - t1 (Q2 - Q1) = Q1 - P1
\n\nt0 = a + t1 b
\n\nt1 = C \xe2\x80\xa2 (Q1 - (1 - a) P1 - a P2) / |C|^2
\n\n在哪里：
\n\na = (P2 - P1) \xe2\x80\xa2 (Q1 - P1) / |P2 - P1|^2
\n\nb = (P2 - P1) \xe2\x80\xa2 (Q2 - Q1) / |P2 - P1|^2
\n\nC = b (P2 - P1) - (Q2 - Q1)
\n\n其中 (\xe2\x80\xa2) 是点积。如果 t0 和 t1 都在区间 [0 1] 内，则存在交点 P(t0)（或 Q(t1)）。
\n\n采毛机坐标方式
\n\n给定由点 P1 和 P2 限定的线段 P 和由点 Q1 和 Q2 限定的线段 Q。
\n\n线 P 的 Plucker 坐标由一对 3d 向量 (Pd, Pm) 给出：
\n\nPd = P2 - P1
\n\nPm = P1 \xc3\x97 P2
\n\n其中 Pm 是 P1 和 P2 的叉积。线 Q 的 Plucker 坐标（Qd，Qm）可以用完全相同的方式计算。
\n\n直线 P 和 Q 仅在共面时才能相交。线 P 和 Q 共面 iif：
\n\nPd \xe2\x80\xa2 Qm + Qd \xe2\x80\xa2 Pm = 0
\n\n其中 (\xe2\x80\xa2) 是点积。由于机器的精度有限，因此稳健的测试不应检查零，而应检查小数。如果 Pd \xc3\x97 Qd = 0 则直线是平行的（这里 0 是零向量）。同样，稳健的测试应该是例如 (Pd \xc3\x97 Qd) 的平方长度很小。
\n\n如果这些线不平行，那么它们是共面的，并且它们的交点（在 Plucker 的行话中称为“相遇”）将是点：
\n\nx = ((Pm \xe2\x80\xa2 N) Qd - (Qm \xe2\x80\xa2 N) Pd - (Pm \xe2\x80\xa2 Qd) N) / (Pd \xc3\x97 Qd) \xe2 \x80\xa2 N
\n\n其中 N 是任意坐标轴向量（即 (1,0,0) 或 (0,1,0) 或 (0,0,1)），使得 (Pd \xc3\x97 Qd) \xe2\x80\ xa2 N 不为零。
\n\n如果 P 和 Q 都不经过原点，则它们的 Plucker 坐标 Pm 和 Qm 分别将不为零，并且以下 sinpler 公式将起作用
\n\nx = Pm \xc3\x97 Qm / Pd \xe2\x80\xa2 Qm
\n\n有关 Plucker 坐标的介绍，请参阅：
\n\nhttps://en.m.wikipedia.org/wiki/Pl\xc3\xbccker_坐标
\n\nhttp://www.realtimerendering.com/resources/RTNews/html/rtnv11n1.html#art3
\n\n对于一般的交集公式，请参阅以下的“推论 6”：
\n\nhttp://web.cs.iastate.edu/~cs577/handouts/plucker-coordinates.pdf
\n\n线性代数方式
\n\n给定由点 P1 和 P2 限定的线段 P 和由点 Q1 和 Q2 限定的线段 Q。
\n\n线的参数形式由下式给出：
\n\nP(t) = P1 + t (P2 - P1)
\n\nQ(t) = Q1 + t (Q2 - Q1)
\n\n其中t是区间[0 1]内的实数。
\n\n如果两条线相交，则以下等式成立：
\n\nP(t0) = Q(t1)
\n\n假设两个未知数t0和t1存在。将上式展开我们得到：
\n\nt0 (P2 - P1) - t1 (Q2 - Q1) = Q1 - P1
\n\n我们可以通过用矩阵代数表达上述方程来求解 t0 和 t1：
\n\nA x = B
\n\n其中 A 是一个 3x2 矩阵，第一列为向量坐标 (P2 - P1)，第二列为向量坐标 (Q2 - Q1)；x 是未知数 t0 和 t1 的 2x1 列向量，B 是坐标为向量 (Q1 - P1) 的 3x1 列向量。
\n\n经典地，该系统可以通过计算矩阵 A 的伪逆来求解，用 A^+ 表示：
\n\nA^+ = (A^TA)^-1 A^T
\n\n请参阅：\n https://en.m.wikipedia.org/wiki/Generalized_inverse
\n\n幸运的是，Python 中的任何矩阵包都应该能够非常轻松且高效地进行上述计算。
\n\n如果将 A 与其伪逆 A^+ 相乘等于单位矩阵 I，即 (AA^+) == I，则存在唯一答案（交集），您可以通过计算以下乘积得到它：
\n\nx = A^+ B
\n\n当然，如果您无法首先计算伪逆，例如，因为 (A^TA) 是奇异的（即行列式为零），则不存在交集。
\n\n由于我们处理的是线段，因此当且仅当 x0 和 x1 都在区间 [0 1] 中时，交点位于点 P(x0) 或 Q(x1) 处。
\n| 归档时间： |
|
| 查看次数： |
4946 次 |
| 最近记录： |