logo标签列表

两条平行线段的交点

geometry
5
我知道有许多算法可以验证两条线段是否相交。我所说的线段是由2个端点构成的长度线段。但一旦它们遇到平行条件，它们只会告诉用户一个大大的“不”，并假装没有重叠、共享端点或端点勾结。我知道我可以计算两条线段之间的距离。如果距离为0，则检查端点是否位于其他线段中。这意味着我必须使用大量的if else和&& || 条件。这并不难，但我的问题是：“有没有技巧（或数学）方法来计算这种特殊的平行情况？”我希望这张图片能澄清我的问题。http://judark.myweb.hinet.net/parallel.JPG
你究竟想找什么？根据定义，平行线永远不会相交。 - Tyler
平行线永远不会相交，除非它们的距离为0。 但是由于它们的距离为0，它们重叠了。 然而，我的问题是关于线段的。 伸展的线重叠了，但线段仍然未知。 因此，我想寻求揭示未知的解决方案。 - Judarkness
Judarkness，你可能需要稍微修改一下你的问题。如果我们正在检查平行性，那么它们是否是线段有什么关系呢？ - WhirlWind
6个回答
4

根据两条直线的公式，测试它们的斜率是否相等。如果相等，这两条直线是平行的，永远不会相交。

如果您在每条直线上有点，则可以使用斜率公式。

如果两条直线都垂直于x轴，则它们的斜率将无限大，但它们将是平行的。每条直线上的所有点将具有相同的x坐标。

要处理线段，请计算交点，然后确定该交点是否存在于两个线段中。

简单点说，我的线段是有长度的，而不是无限长的直线。除了交点之外，我拥有所有其他信息，如斜率、距离和向量。这些信息用于其他计算 :) - Judarkness
你的问题真的很令人困惑。如果两条线段是平行的，它们不会相交。这不就是你问的吗？我认为是这样的，因为你写道：“有没有一种技巧（或数学）方法来计算这种特殊的平行情况？” - WhirlWind
1
@whirlwind 他在谈论线段，而不是直线。问题是，对于两条（共线）平行线段，如何确定是否存在重叠部分？ - David Gelhar
你需要多少维度？对于2D和3D，可以使用叉积公式和排序来实现。 - Chris H.
抱歉…… - dylan
显示剩余3条评论
1
我不能说有什么“诀窍”，但确实有一种有效的方法来判断两个共线线段是否相交。
假设我们有两个共线线段：[AB]和[CD]。
将坐标转换为1D
首先，我们需要将点的坐标转换为1D环境，因为这样比较点的位置会更容易。
这个过程非常简单：我们将从坐标中去掉y和z值。这是因为在一条直线上没有两个具有相同x值的点（只要线段不属于与x轴正交的平面）。但是如果所有点都具有相同的x值，那么我们将使用y坐标。如果所有点都具有相同的y坐标，我们将考虑z坐标。如果我们到达了这一点，那么点不能都具有相同的z坐标。
判断所有点是否具有相同的x/y坐标的方法是计算向量AB。如果AB.x等于0，则意味着我们不需要在x轴上移动从点A到点B，因此点A和点B具有相同的x值，对于点C和点D也是如此。
我主要讨论的是3D，但对于2D、4D、5D等情况，原理是相同的。
代码如下：
if AB.x == 0
    if AB.y == 0
        A = A.z
        B = B.z
        C = C.z
        D = D.z
   else
        A = A.y
        B = B.y
        C = C.y
        D = D.y
else
    A = A.x
    B = B.x
    C = C.x
    D = D.x

检测碰撞在最后也是相当简单的。点A、B、C和D可以有52个不同的相对位置（包括2个具有完全相同坐标的点）。在这52个位置中，有44个表示发生了碰撞，只有8个表示相反。因此，明显的解决方案是只寻找这8个位置。
但我们可以将这个数字减少到2个。实际上，如果我们考虑到A和B的坐标以及C和D的坐标是按升序排列的，那么这四个点可能有13个不同的相对位置（*请参见注释部分）。在这13个位置中，只有2个位置表示没有任何碰撞。这两个位置是D的x值小于A（C-D A-B）或者C的x值大于B（A-B C-D）。

因此，在对点A和B以及C和D进行排序后，如果false；否则返回true，这样我们就得到了return not(D < A or B < C)或者更简化的表达方式：return A <= D and C <= B

算法的最后部分应该如下所示：

if A < B
    if C < D
        return A <= D and C <= B
    else
        return A <= C and D <= B
else
    if C < D
        return B <= D and C <= A
    else
        return B <= C and D <= A

注意事项

位置A、B、C和D可以有13个不同的位置：

┏━━━━━━━━━━━━┳━━━━━━━━━━━━┳━━━━━━━━━━━━┓
┃    C  D    ┃    C  D    ┃    C  D    ┃
┃  AB        ┃  A B       ┃  A   B     ┃
┃━━━━━━━━━━━━╋━━━━━━━━━━━━╋━━━━━━━━━━━━┫
┃    C  D    ┃    C  D    ┃    C  D    ┃
┃  A    B    ┃  A      B  ┃    A B     ┃
┣━━━━━━━━━━━━╋━━━━━━━━━━━━╋━━━━━━━━━━━━┫
┃    C  D    ┃    C  D    ┃    C  D    ┃
┃    A  B    ┃    A    B  ┃     AB     ┃
┣━━━━━━━━━━━━╋━━━━━━━━━━━━╋━━━━━━━━━━━━┫
┃    C  D    ┃    C  D    ┃    C  D    ┃
┃     A B    ┃     A   B  ┃       A B  ┃
┣━━━━━━━━━━━━╋━━━━━━━━━━━━╋━━━━━━━━━━━━┫
┃    C  D    ┃            ┃            ┃
┃        AB  ┃            ┃            ┃
┗━━━━━━━━━━━━┻━━━━━━━━━━━━┻━━━━━━━━━━━━┛
0
我假设您感兴趣的情况是两条线段平行(通过检查斜率确定)，并且您想确定这两个线段是否重叠。
与其担心线之间的距离，我认为最简单的方法是检查其中一个线段的任一端点是否在另一个线段内部：
if (segment_contains_point(segment_A, segment_B.start) || 
    segment_contains_point(segment_A, segment_B.end)) {
        // lines overlap
}
1
这正是我想要的，我有自己的segment_contains_points()函数（另一个名称）。但它太低效了。而且我必须调用它三次，因为线段B可能更大，包含整个线段A。我想知道是否有更好的解决方案？ - Judarkness
0
假设你有两条线，由公式 a.x + b.y + c = 0 和 d.x + e.y + f = 0 描述。当 a = 0 and d = 0 或者 b/a = e/d 时，这两条线是平行的。也可以通过判断 b.d = a.e 来避免除法计算。
0
我找到了这个（稍作修改以适应我的需要） 它将返回交点x，y，否则如果没有找到交点，则返回-1，-1。
    Public Function intercetion(ByVal ax As Integer, ByVal ay As Integer, ByVal bx As Integer, ByVal by As Integer, ByVal cx As Integer, ByVal cy As Integer, ByVal dx As Integer, ByVal dy As Integer) As Point
    '//  Determines the intersection point of the line segment defined by points A and B
    '//  with the line segment defined by points C and D.
    '//
    '//  Returns YES if the intersection point was found, and stores that point in X,Y.
    '//  Returns NO if there is no determinable intersection point, in which case X,Y will
    '//  be unmodified.

    Dim distAB, theCos, theSin, newX, ABpos As Double

    '//  Fail if either line segment is zero-length.
    If ax = bx And ay = by Or cx = dx And cy = dy Then Return New Point(-1, -1)

    '//  Fail if the segments share an end-point.
    If ax = cx And ay = cy Or bx = cx And by = cy Or ax = dx And ay = dy Or bx = dx And by = dy Then Return New Point(-1, -1)

    '//  (1) Translate the system so that point A is on the origin.
    bx -= ax
    by -= ay
    cx -= ax
    cy -= ay
    dx -= ax
    dy -= ay

    '//  Discover the length of segment A-B.
    distAB = Math.Sqrt(bx * bx + by * by)

    '//  (2) Rotate the system so that point B is on the positive X axis.
    theCos = bx / distAB
    theSin = by / distAB
    newX = cx * theCos + cy * theSin
    cy = cy * theCos - cx * theSin
    cx = newX
    newX = dx * theCos + dy * theSin
    dy = dy * theCos - dx * theSin
    dx = newX

    '//  Fail if segment C-D doesn't cross line A-B.
    If cy < 0 And dy < 0 Or cy >= 0 And dy >= 0 Then Return New Point(-1, -1)

    '//  (3) Discover the position of the intersection point along line A-B.
    ABpos = dx + (cx - dx) * dy / (dy - cy)

    '//  Fail if segment C-D crosses line A-B outside of segment A-B.
    If ABpos < 0 Or ABpos > distAB Then Return New Point(-1, -1)

    '//  (4) Apply the discovered position to line A-B in the original coordinate system.
    '*X=Ax+ABpos*theCos
    '*Y=Ay+ABpos*theSin

    '//  Success.
    Return New Point(ax + ABpos * theCos, ay + ABpos * theSin)
End Function

原始

这并没有解决确定共线线段重叠的问题 - 实际上，在此代码的注释中，它明确表示对于共线（和平行）线段将失败：// 如果线段C-D不穿过线A-B，则失败。 - Wil Shipley
0
我刚遇到了同样的问题：我想到的最简单的方法就是检查这些线段是否重叠： 假设这些线段共线（平行且与x轴相交）。 从较长的线段（A，B）中取一个点A作为起点。现在找到其他三个点中距离点A最小的点（平方距离更好，曼哈顿长度也可能有效），并沿着B的方向测量距离。如果距离A最近的点是B，则这些线段不相交。如果它属于另一个线段，则它们相交。 也许你需要检查特殊情况，比如零长度线段或相同的线段，但这应该很容易。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接