寻找共线线段重叠的算法

Question

更新

• 我的C＃中的原始实现
• 我基于所得答案的C＃最终实现。

---

在以下条件下，如何编程找到两条线之间的重叠段？

另外，对于不同的斜率：

对于垂直线：

对于水平线：

注意：适用于所有象限！

我已经开始编写所有可能的条件但是代码变得很丑陋。

public Line GetOverlap (Line line1, Line line2)
{
    double line1X1 = line1.X1;
    double line1Y1 = line1.Y1;
    double line1X2 = line1.X2;
    double line1Y2 = line1.Y2;
    double line2X1 = line2.X1;
    double line2Y1 = line2.Y1;
    double line2X2 = line2.X2;
    double line2Y2 = line2.Y2;

    if (line1X1 > line1X2)
    {
        double swap = line1X1;
        line1X1 = line1X2;
        line1X2 = swap;

        swap = line1Y1;
        line1Y1 = line1Y2;
        line1Y2 = swap;
    }
    else if (line1X1.AlmostEqualTo (line1X2))
    {
        if (line1Y1 > line1Y2)
        {
            double swap = line1Y1;
            line1Y1 = line1Y2;
            line1Y2 = swap;

            swap = line1X1;
            line1X1 = line1X2;
            line1X2 = swap;
        }
    }

    if (line2X1 > line2X2)
    {
        double swap = line2X1;
        line2X1 = line2X2;
        line2X2 = swap;

        swap = line2Y1;
        line2Y1 = line2Y2;
        line2Y2 = swap;
    }
    else if (line2X1.AlmostEqualTo (line2X2))
    {
        if (line2Y1 > line2Y2)
        {
            double swap = line2Y1;
            line2Y1 = line2Y2;
            line2Y2 = swap;

            swap = line2X1;
            line2X1 = line2X2;
            line2X2 = swap;
        }
    }

    double line1MinX = Math.Min (line1X1, line1X2);
    double line2MinX = Math.Min (line2X1, line2X2);
    double line1MinY = Math.Min (line1Y1, line1Y2);
    double line2MinY = Math.Min (line2Y1, line2Y2);
    double line1MaxX = Math.Max (line1X1, line1X2);
    double line2MaxX = Math.Max (line2X1, line2X2);
    double line1MaxY = Math.Max (line1Y1, line1Y2);
    double line2MaxY = Math.Max (line2Y1, line2Y2);

    double overlap;
    if (line1MinX < line2MinX)
        overlap = Math.Max (line1X1, line1X2) - line2MinX;
    else
        overlap = Math.Max (line2X1, line2X2) - line1MinX;

    if (overlap <= 0)
        return null;

    double x1;
    double y1;
    double x2;
    double y2;

    if (line1MinX.AlmostEqualTo (line2MinX))
    {
        x1 = line1X1;
        x2 = x1;
        y1 = line1MinY < line2MinY
                 ? line2Y1
                 : line1Y1;
        y2 = line1MaxY < line2MaxY
                 ? line1Y2
                 : line2Y2;
    }
    else
    {
        if (line1MinX < line2MinX)
        {
            x1 = line2X1;
            y1 = line2Y1;
        }
        else
        {
            x1 = line1X1;
            y1 = line1Y1;
        }

        if (line1MaxX > line2MaxX)
        {
            x2 = line2X2;
            y2 = line2Y2;
        }
        else
        {
            x2 = line1X2;
            y2 = line1Y2;
        }
    }

    return new Line (x1, y1, x2, y2);
}

我相信这个问题存在一个算法，但是我在网上没有找到。

---

根据我得到的答案更新的解决方案：

这个解决方案考虑了我所能想到的所有情况（垂直、水平、正斜率、负斜率、不相交）。

public Line GetOverlap (Line line1, Line line2)
{
    double slope = (line1.Y2 - line1.Y1)/(line1.X2 - line1.X1);
    bool isHorizontal = AlmostZero (slope);
    bool isDescending = slope < 0 && !isHorizontal;
    double invertY = isDescending || isHorizontal ? -1 : 1;

    Point min1 = new Point (Math.Min (line1.X1, line1.X2), Math.Min (line1.Y1*invertY, line1.Y2*invertY));
    Point max1 = new Point (Math.Max (line1.X1, line1.X2), Math.Max (line1.Y1*invertY, line1.Y2*invertY));

    Point min2 = new Point (Math.Min (line2.X1, line2.X2), Math.Min (line2.Y1*invertY, line2.Y2*invertY));
    Point max2 = new Point (Math.Max (line2.X1, line2.X2), Math.Max (line2.Y1*invertY, line2.Y2*invertY));

    Point minIntersection;
    if (isDescending)
        minIntersection = new Point (Math.Max (min1.X, min2.X), Math.Min (min1.Y*invertY, min2.Y*invertY));
    else
        minIntersection = new Point (Math.Max (min1.X, min2.X), Math.Max (min1.Y*invertY, min2.Y*invertY));

    Point maxIntersection;
    if (isDescending)
        maxIntersection = new Point (Math.Min (max1.X, max2.X), Math.Max (max1.Y*invertY, max2.Y*invertY));
    else
        maxIntersection = new Point (Math.Min (max1.X, max2.X), Math.Min (max1.Y*invertY, max2.Y*invertY));

    bool intersect = minIntersection.X <= maxIntersection.X && 
                     (!isDescending && minIntersection.Y <= maxIntersection.Y ||
                       isDescending && minIntersection.Y >= maxIntersection.Y);

    if (!intersect)
        return null;

    return new Line (minIntersection, maxIntersection);
}

public bool AlmostEqualTo (double value1, double value2)
{
    return Math.Abs (value1 - value2) <= 0.00001;
}

public bool AlmostZero (double value)
{
    return Math.Abs (value) <= 0.00001;
}

- Stécy

---

“gets ugly”是什么意思？目前这个问题非常宽泛；最好发布一些代码并寻求更具体的帮助。为什么您需要“单独条件”（我假设是针对每个图表）？将点排序并返回中间两个应该相对简单... - Dan Puzey

你目前尝试了什么？这是基本的向量数学。可能存在的问题是舍入误差和浮点精度。 - Ondrej Tucny

@DanPuzey 我更新了我的问题。 - Stécy

求解一个简单问题却得到如此复杂的答案。计算两个线段的长度，按字典序排序点集。如果整体长度（min-max）> 两条线段长度之和，则无重叠部分；否则中间的两个点是重叠部分。如果您事先知道它们共线，那么就可以了解决，否则需要进行叉积检查。 - agentp

Answer 1

这个问题大致相当于测试两个轴对齐矩形是否相交：您可以将每个线段视为轴对齐矩形的对角线，然后需要找到这两个矩形的交点。以下是我用于矩形交集的方法。

假设线段的斜率是上升的、垂直的或水平的；如果线段是下降的，请否定每个y坐标，使它们上升。

为每条线段定义MinPoint和MaxPoint：

Point min1 = new Point(Math.Min(line1.X1, line1.X2),Math.Min(line1.Y1,line1.Y2);
Point max1 = new Point(Math.Max(line1.X1, line1.X2),Math.Max(line1.Y1,line1.Y2);

Point min2 = new Point(Math.Min(line2.X1, line2.X2),Math.Min(line2.Y1,line2.Y2);
Point max2 = new Point(Math.Max(line2.X1, line2.X2),Math.Max(line2.Y1,line2.Y2);

现在的交集由以下两个点给出：两个最小值中的最大值和两个最大值中的最小值。

Point minIntersection = new Point(Math.Max(min1.X, min2.X), Math.Max(min1.Y, min2.Y));
Point maxIntersection = new Point(Math.Min(max1.X, max2.X), Math.Min(max1.Y, max2.Y));

就是这样。要测试这两个线段是否有交点，您需要检查：

bool intersect = (minIntersection.X< maxIntersection.X) && (minIntersection.Y< maxIntersection.Y);

如果它们相交，交点由两个点minIntersection和maxIntersection给出。如果它们不相交，则线段(minIntersection，maxIntersection)的长度是两个原始线段之间的距离。

（如果您在第一步中否定了第一个y坐标，请现在否定结果的y坐标）

（您可以轻松地扩展此方法以涵盖3或更多维的共线线段）

- HugoRune

---

水平线的Y坐标反转可以实现，但是对于下降线段则不行。 - Stécy

当你对一个下降段反转所有的Y坐标时，你会得到一个上升段，而结果坐标只是原始坐标的镜像。 - HugoRune

即使需要更多的代码，也不需要进行词典排序就能完成相同的任务，这是一种更好的方法。 - Nuclearman

这种方法不适用于升序平行但非共线对角线，其中线1的矩形与线2的矩形在两条线之间的空间中相交。计算出的线段是两个线段中间的虚拟线。只有当min1，max1，max2的叉积为0时才使用此方法。 - Martijn Pieters

该问题指定共线线段。据我回忆，这个解决方案不适用于非共线线段，它最初是为轴对齐的矩形设计的： “幻影线” 应该是两个相交矩形之间矩形交集的对角线。 - HugoRune

Answer 2

您需要对这两个部分进行字典序排序，然后取第一个部分的最后一个元素和最后一个部分的第一个元素（以字典序排序的部分）。这样可以得到所需的部分。

如果您想要验证，可以使用叉积来确定它们是否形成一条线。当二维叉积为零时，三个点形成一条线。

例如：

B = ((0,0),(3,3))
A = ((2,2),(5,5))

进行字典排序后：

[((0,0),(3,3)),((2,2),(5,5))]
C = ((3,3),(4,4))

您可以通过确保C的第一个元素在字典序上大于第二个线段的第一个元素，来检查它们是否重叠。例如，在本例中是这样的。

然后，使用第一个列表的第一个元素和最后一个线段的最后一个元素来进行它们重叠的证明。然后分别检查这两个元素内部，以查看它们是否通过三个点的叉积为零位于一条直线上：

cross((0,0),(1,1),(5,5)) = 0
cross((0,0),(4,4),(5,5)) = 0

因此，这两个输入段确实形成一条直线。

我对C#不太熟悉，无法保证正确性，但在Python中，该算法如下：

def cross(o, a, b):
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

def line_segment_overlap(segment_a,segment_b):
    segments = [segment_a.sort(),segment_b.sort()] # 2D Lexicographic sort the line segments
    segments.sort()
    A = segments[0]
    B = segments[1]
    if cross(A[0],A[1],B[1]) == 0 and cross(A[0],B[0],B[1]) == 0: # Segments form a line
        if A[1] > B[0]: # Segments overlap
            return (A[1],B[1]) # New line segment
    return None

- Nuclearman

---

@Stécy：这是一种字典排序，应该可以（尽管精度可能会有问题）。如果B = ((0,0),(0,2))，A = ((0,1),(0,4))。字典排序应该得到[((0,0),(0,2)),((0,1),(0,4))]。如果x值相同，则按x然后y排序。这是一种字典排序。话虽如此，如果您使用的线段超过两条，则几乎肯定需要更复杂的算法来确保它给出所有正确的输出，但这不是您的问题所要求的。 - Nuclearman

好的，排序的结果应该是（0,0）-（0,1）-（0,2）-（0,4）吗？如果我先按X排序再按Y排序，那么这就是我得到的结果。 - Stécy

哦，这对于非重叠的片段是行不通的：(0,0)-(1,1)和(3,3)-(5,5)会得到(1,1)-(3,3)，这不是一个重叠的片段。 - Stécy

是的，但正如我在答案中指出的那样，验证它们是否重叠相当简单。 - Nuclearman

不，您需要对线段本身进行词典排序，而不是对端点进行排序，但最终会涉及到点本身，我之所以提到X和Y，是因为您所说的问题。这可能需要递归来比较第一个线段的第一个点与第一个线段的第一个点。如果这两个点相同，则比较第二个点。我想，如果您使用支持词典排序的语言而不是尝试自己实现它，那将更容易些。我不确定C#是否支持。 - Nuclearman

Answer 3

将你的坐标系转换，使得线段成为新的x轴。

按照从左到右的顺序对点进行排序。

如果线段实际上重叠了，那么解决方案始终是第二个和第三个点。

注意：如果不能保证线段重叠，则测试很简单——如果前两个点属于同一线段，则它们不重叠。

- mbeckish

---

如果坐标转换听起来太可怕而不敢尝试，您也可以用参数方程式写出您的线性方程式，在每个点上解出t，并按t排序，而不是从“左到右”排序。 - mbeckish

需要“转换”坐标吗？我能否按它们的X值对点进行排序？那么垂直线呢？ - Stécy

@Stécy - 请看我的回答评论。您可以使用线的参数形式，并按t排序。如果您不想这样做，那么是的，您可以只按x排序，并处理垂直线的边缘情况。但是您真的不应该害怕坐标变换-一旦您习惯了它们，它们就非常容易和强大。 - mbeckish

Answer 4

使用将线段AB映射到(0, 0):(0, 1)的变换。任何与AB共线的线段两端点的纵坐标都为0，设为(c, 0):(d, 0)。重叠部分由(Max(0, c), 0):(Min(1, d), 0)给出，除非Max(0, c) > Min(1, d)。

令ABx = X1 - X0，ABy = Y1 - Y0，AB^2 = ABx^2 + ABy^2。

x = ((X-XA) ABx + (Y-YA) ABy) / AB^2
y = ((X-XA) ABy - (Y-YA) ABx) / AB^2

如果您想在2D中重叠，请应用反转换（其中y = 0）。

X = XA + x ABx
Y = YA + x ABy

- user1196549

Answer 5

我不是100%确定，希望社区能告诉我。我之所以不把这个发布为评论，只是因为我认为一些微小的格式化不会有害。

在我看来，一条直线的方程：

y = mx + c

其中：

• y 是给定的 y 坐标（在一个 x-y 对中）；
• m 是该线的斜率;
• x 是给定的坐标（x-y 对的另一部分）；
• c 是截距关键。

对于任何两个点的集合，您都应该能够通过以下方式计算出线的方程：

1. 找到 m 的值（通常为 dy/dx）

2. 找到 y=0 时 c 的值。

一旦您计算出来了，如果愿意，您可以生成字符串形式的方程。

一旦您完成了所有点对的处理，您应该能够通过检查您生成的方程式来确定重叠的线段。然后，您可以使用线上点的坐标来推断出两个矩形，并查看哪一个适合另一个。这应该有助于您确定哪条线在哪个线段内。

- npinti