使用 Cramer 检测两条线段是否相交

Question

我已经使用了已发布的代码here。这是代码：

from __future__ import division 

def line(p1, p2):
    A = (p1[1] - p2[1])
    B = (p2[0] - p1[0])
    C = (p1[0]*p2[1] - p2[0]*p1[1])
    return A, B, -C

def intersection(L1, L2):
    D  = L1[0] * L2[1] - L1[1] * L2[0]
    Dx = L1[2] * L2[1] - L1[1] * L2[2]
    Dy = L1[0] * L2[2] - L1[2] * L2[0]
    if D != 0:
        x = Dx / D
        y = Dy / D
        return x,y
    else:
        return False

# Usage
L1 = line([0,1], [2,3])
L2 = line([2,3], [0,4])

R = intersection(L1, L2)
if R:
    print "Intersection detected:", R
else:
    print "No single intersection point detected"

它实现了 Cramer 规则（适用于直线；如果为两条给定直线构建的线性方程的行列式为 0，则直线不相交）。但是，我遇到的问题是，它还会检测到手头两条线的连续性导致的交叉点。这是我使用 matplotlib 制作的图，它演示了这个问题：

我还有一个 Triangle class，其中包含 3 个 Line 对象，它进一步证明了这个问题，因为 class 也有自己的 intersect(...) 函数，它接受另一个三角形并检查两个三角形的哪些边相交以及在哪里：

我想使用 link 中的算法检测 线段交点 。以上线段没有有交点。我该怎么做？

我有两个 classes - Point 和 Line - 用于以更具可读性的方式处理这些几何元素。我维护了上面的脚本并围绕它（参见Line.intersect(...)）：

class Point:
  def __init__(self, x, y, z):
        self.x = x
        self.y = y
        self.z = z

  # Override __add__, __sub__ etc. to allow arithmetic operations with Point objects
  # ...

class Line:
  def __init__(self, p1, p2):
        self.p1 = p1
        self.p2 = p2
  # ...
  def intersect(self, l):
        def line(p1, p2):
            A = (p1.y - p2.y)
            B = (p2.x - p1.x)
            C = (p1.x*p2.y - p2.x*p1.y)
            return A, B, -C

        L1 = line(self.p1, self.p2)
        L2 = line(l.p1, l.p2)

        D  = L1[0]*L2[1] - L1[1]*L2[0]
        Dx = L1[2]*L2[1] - L1[1]*L2[2]
        Dy = L1[0]*L2[2] - L1[2]*L2[0]

        if D != 0:
            x = Dx / D
            y = Dy / D
            p = Point(x, y)
            return True, p

        return False, None

#Usage
l1 = Line(Point(0, 0), Point(10, 4))
l2 = Line(Point(-4, -3), Point(-4, 10))

res, p = l1.intersect(l2)
if not res:
    print('Lines don\'t intersect')
else:
    print('Lines intersect at [%f, %f]' % (p.x, p.y))

我也在寻找最佳（尽可能少的非成本操作和尽可能少的内存占用）解决方案。

一种可能的解决方案是通过使用欧几里德距离来确定这些点是否位于两个线段上，从而过滤掉结果的交点（不属于两个线段的交点）。如果不是，则相交是一条或两条线的延续的结果，应被视为无效。然而，这是一项代价高昂的操作，并且还需要考虑所有交叉点（无论该点是否属于两个线段的一部分）。

更新： 我以为我已经解决了问题，但是唉！以下有问题。在仔细查看评论后，我看到了@JerryCoffin 的评论，他指出 this post:

可能重复

def intersect(self, l, contious=False):
        # Before anything else check if lines have a mutual abcisses
        interval_1 = [min(self.p1.x, self.p2.x), max(self.p1.x, self.p2.x)]
        interval_2 = [min(l.p1.x, l.p2.x), max(l.p1.x, l.p2.x)]
        interval = [
            min(interval_1[1], interval_2[1]),
            max(interval_1[0], interval_2[0])
        ]

        if interval_1[1] < interval_2[0]:
            print('No mutual abcisses!')
            return False, None

        # Try to compute interception
        def line(p1, p2):
            A = (p1.y - p2.y)
            B = (p2.x - p1.x)
            C = (p1.x*p2.y - p2.x*p1.y)
            return A, B, -C

        L1 = line(self.p1, self.p2)
        L2 = line(l.p1, l.p2)

        D  = L1[0]*L2[1] - L1[1]*L2[0]
        Dx = L1[2]*L2[1] - L1[1]*L2[2]
        Dy = L1[0]*L2[2] - L1[2]*L2[0]

        if D != 0:
            x = Dx / D
            y = Dy / D
            p = Point(x, y)
            if contiuous: # continuous parameter allows switching between line and line segment interception
                return True, p
            else:
                if p.x < interval[1] or p.x > interval[0]:
                    print('Intersection out of bound')
                    return False, None
                else:
                    return True, p
        else:
            print('Not intersecting')
            return False, None

结果：

看起来不错，正是我想要的。但是我添加了一条线（坐标或多或少是随机的，但我很容易在图上检查）即Line(Point(-4, 12), Point(12, -4))。想象一下当我再次得到一个误报时我的惊讶：

如您所见，在我的线段开头的左上角检测到一个交点。它确实 与 垂直线 的延续 相交，但不与实际线段相交。似乎两条线段具有相同的 x 而一条线段是垂直的这一事实构成了一个问题。所以我仍然不知道如何解决这个问题。

Answer 1

好吧，需要学习如何阅读...解决方案实际上在@JerryCoffin 提出的重复建议的评论中，即 here:

def intersect(self, l, contious=False):
        # Before anything else check if lines have a mutual abcisses
        interval_1 = [min(self.p1.x, self.p2.x), max(self.p1.x, self.p2.x)]
        interval_2 = [min(l.p1.x, l.p2.x), max(l.p1.x, l.p2.x)]
        interval = [
            min(interval_1[1], interval_2[1]),
            max(interval_1[0], interval_2[0])
        ]

        if interval_1[1] < interval_2[0]:
            print('No mutual abcisses!')
            return False, None

        # Try to compute interception
        def line(p1, p2):
            A = (p1.y - p2.y)
            B = (p2.x - p1.x)
            C = (p1.x*p2.y - p2.x*p1.y)
            return A, B, -C

        L1 = line(self.p1, self.p2)
        L2 = line(l.p1, l.p2)

        D  = L1[0]*L2[1] - L1[1]*L2[0]
        Dx = L1[2]*L2[1] - L1[1]*L2[2]
        Dy = L1[0]*L2[2] - L1[2]*L2[0]

        if D != 0:
            x = Dx / D
            y = Dy / D
            p = Point(x, y)
            if contiuous: # continuous parameter allows switching between line and line segment interception
                return True, p
            else:
                if p.x < interval[1] or p.x > interval[0]:
                    print('Intersection out of bound')
                    return False, None
                else:
                    return True, p
        else:
            print('Not intersecting')
            return False, None

结果：

使用 Cramer 检测两条线段是否相交

Detect if two line segments intersect using Cramer

algorithm

line-intersection

line-segment