算法找到段与两个共线区段 [英] Algorithm for finding the segment overlapping two collinear segments

查看：127
本文介绍了算法找到段与两个共线区段的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

更新

  • 在C＃我原来实施
  • 在C＃我的最终落实的基础上，我得到了答案。

由于下列条件的，我怎么能编程方式找到两条线之间的重叠段？

此外，对于不同的斜率：

和垂直线：

和水平行：

注：对于所有的象限

我已经通过编码所有可能的条件下开始，但它变得难看。

 公共线路GetOverlap（线一号线，线2号线）
{
    双line1X1 = line1.X1;
    双line1Y1 = line1.Y1;
    双line1X2 = line1.X2;
    双line1Y2 = line1.Y2;
    双line2X1 = line2.X1;
    双line2Y1 = line2.Y1;
    双line2X2 = line2.X2;
    双line2Y2 = line2.Y2;

    如果（line1X1＆GT; line1X2）
    {
        双交换= line1X1;
        line1X1 = line1X2;
        line1X2 =掉;

        互换= line1Y1;
        line1Y1 = line1Y2;
        line1Y2 =掉;
    }
    否则，如果（line1X1.AlmostEqualTo（line1X2））
    {
        如果（line1Y1＆GT; line1Y2）
        {
            双交换= line1Y1;
            line1Y1 = line1Y2;
            line1Y2 =掉;

            互换= line1X1;
            line1X1 = line1X2;
            line1X2 =掉;
        }
    }

    如果（line2X1＆GT; line2X2）
    {
        双交换= line2X1;
        line2X1 = line2X2;
        line2X2 =掉;

        互换= line2Y1;
        line2Y1 = line2Y2;
        line2Y2 =掉;
    }
    否则，如果（line2X1.AlmostEqualTo（line2X2））
    {
        如果（line2Y1＆GT; line2Y2）
        {
            双交换= line2Y1;
            line2Y1 = line2Y2;
            line2Y2 =掉;

            互换= line2X1;
            line2X1 = line2X2;
            line2X2 =掉;
        }
    }

    双line1MinX = Math.Min（line1X1，line1X2）;
    双line2MinX = Math.Min（line2X1，line2X2）;
    双line1MinY = Math.Min（line1Y1，line1Y2）;
    双line2MinY = Math.Min（line2Y1，line2Y2）;
    双line1MaxX = Math.Max​​（line1X1，line1X2）;
    双line2MaxX = Math.Max​​（line2X1，line2X2）;
    双line1MaxY = Math.Max​​（line1Y1，line1Y2）;
    双line2MaxY = Math.Max​​（line2Y1，line2Y2）;

    双重叠;
    如果（line1MinX＆LT; line2MinX）
        重叠= Math.Max​​（line1X1，line1X2） -  line2MinX;
    其他
        重叠= Math.Max​​（line2X1，line2X2） -  line1MinX;

    如果（重叠＆所述; = 0）
        返回null;

    双X1;
    双Y1;
    双X2;
    双Y2;

    如果（line1MinX.AlmostEqualTo（line2MinX））
    {
        X1 = line1X1;
        X2 = X1;
        Y1 = line1MinY＆LT; line2MinY
                 ？ line2Y1
                 ：line1Y1;
        Y2 = line1MaxY＆LT; line2MaxY
                 ？ line1Y2
                 ：line2Y2;
    }
    其他
    {
        如果（line1MinX＆LT; line2MinX）
        {
            X1 = line2X1;
            Y1 = line2Y1;
        }
        其他
        {
            X1 = line1X1;
            Y1 = line1Y1;
        }

        如果（line1MaxX＆GT; line2MaxX）
        {
            X2 = line2X2;
            Y2 = line2Y2;
        }
        其他
        {
            X2 = line1X2;
            Y2 = line1Y2;
        }
    }

    返回新线（X1，Y1，X2，Y2）;
}

我敢肯定存在一个这样的算法，但我无法找到一个在网络上。

更新与解决方案的基础上我得到了答案：

对于所有的情况下，我能想到的这个解决方案帐户（垂直，水平线条，正斜率，负斜率，互不交叉）

 公共线路GetOverlap（线一号线，线2号线）
{
    双坡=（line1.Y2  -  line1.Y1）/（line1.X2  -  line1.X1）;
    布尔isHorizo​​ntal = AlmostZero（斜率）;
    布尔isDescending =斜率LT; 0安培;＆安培; ！isHorizo​​ntal;
    双invertY = isDescending || isHorizo​​ntal？ -1：1;

    点分1 =新的点（Math.Min（line1.X1，line1.X2），Math.Min（line1.Y1 * invertY，line1.Y2 * invertY））;
    点MAX1 =新的点（Math.Max​​（line1.X1，line1.X2），Math.Max​​（line1.Y1 * invertY，line1.Y2 * invertY））;

    点MIN2 =新的点（Math.Min（line2.X1，line2.X2），Math.Min（line2.Y1 * invertY，line2.Y2 * invertY））;
    点MAX2 =新的点（Math.Max​​（line2.X1，line2.X2），Math.Max​​（line2.Y1 * invertY，line2.Y2 * invertY））;

    点minIntersection;
    如果（isDescending）
        minIntersection =新的点（Math.Max​​（min1.X，min2.X），Math.Min（min1.Y * invertY，min2.Y * invertY））;
    其他
        minIntersection =新的点（Math.Max​​（min1.X，min2.X），Math.Max​​（min1.Y * invertY，min2.Y * invertY））;

    点maxIntersection;
    如果（isDescending）
        maxIntersection =新的点（Math.Min（max1.X，max2.X），Math.Max​​（max1.Y * invertY，max2.Y * invertY））;
    其他
        maxIntersection =新的点（Math.Min（max1.X，max2.X），Math.Min（max1.Y * invertY，max2.Y * invertY））;

    布尔相交= minIntersection.X＆LT; = maxIntersection.X和放大器;＆安培;
                     （isDescending＆安培;！＆安培; minIntersection.Y＆LT; = maxIntersection.Y ||
                       isDescending＆功放;＆安培; minIntersection.Y＆GT; = maxIntersection.Y）;

    如果（！相交）
        返回null;

    返回新线（minIntersection，maxIntersection）;
}

公共BOOL AlmostEqualTo（双值1，双值2）
{
    返回Math.Abs​​（值1  - 值2）其中，= 0.00001;
}

公共BOOL AlmostZero（double值）
{
    返回Math.Abs​​（值）＆LT; = 0.00001;
}

解决方案

这个问题是大致相当于测试二轴​​对准的矩形是否相交：你可以威胁每一段为斜轴对齐的矩形，那么你需要找到这两个矩形的交集。下面是我使用的矩形相交的办法。

让我们假设线段的斜率是升序，垂直或水平;如果段被降，否定每y坐标，使得它们升序。

定义MinPoint和MaxPoint每个线段：

 点分1 =新的点（Math.Min（line1.X1，line1.X2），Math.Min（line1.Y1，line1.Y2）;
点MAX1 =新的点（Math.Max​​（line1.X1，line1.X2），Math.Max​​（line1.Y1，line1.Y2）;

点MIN2 =新的点（Math.Min（line2.X1，line2.X2），Math.Min（line2.Y1，line2.Y2）;
点MAX2 =新的点（Math.Max​​（line2.X1，line2.X2），Math.Max​​（line2.Y1，line2.Y2）;

现在通过以下两点给出的交集：两个最低的最大，最小的两个最大值的

 点minIntersection =新的点（Math.Max​​（min1.X，min2.X），Math.Max​​（min1.Y，min2.Y））;
点maxIntersection =新的点（Math.Min（max1.X，max2.X），Math.Min（max1.Y，max2.Y））;

，就是这样。为了测试两个部分是否相交于一切，你检查

 布尔相交=（minIntersection.X＆LT; maxIntersection.X）及和放大器; （minIntersection.Y＆LT; maxIntersection.Y）;

如果他们相交，交叉口由两个点给定的 minIntersection 和 maxIntersection 。如果他们不相交，该段的长度（minIntersection，maxIntersection）是原来的两部分之间​​的距离。

（如果否定每y坐标在第一个步骤中，否定的y坐标的结果现在）

（你可以很容易地扩展这种方法以覆盖共线区段的3个或更多维）

UPDATES

  • My original implementation in C#
  • My final implementation in C#, based on the answers I got.

Given the following conditions, how can I programatically find the overlapping segment between two lines?

Also, for a different slope:

And for vertical lines:

And for horizontal lines:

Note: For all the quadrants !

I've started by coding all possible conditions but it gets ugly.

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);
}

I'm sure an algorithm exists for this but I was unable to find one on the web.

UPDATE with solution based on answers I got:

This solution account for all the cases I could think of (verticals, horizontals, positive slope, negative slope, not intersecting)

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;
}

解决方案

This problem is roughly equivalent to the test whether two axis-aligned rectangles intersect: you can threat every segment as the diagonal of an axis-aligned rectangle, then you need to find the intersection of these two rectangles. The following is the approach I use for rectangle intersection.

Let's assume that the slope of the segments is ascending, vertical, or horizontal; if the segments are descending, negate every y-coordinate so that they are ascending.

Define the MinPoint and MaxPoint for each line segment:

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);

Now the intersection is given by the following two points: the maximum of the two minimums, and the minimum of the two maximums

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));

and that's it. To test whether the two segments intersect at all, you check

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

If they do intersect, the intersection is given by the two points minIntersection and maxIntersection. If they do not intersect, the length of the segment (minIntersection, maxIntersection) is the distance between the two original segments.

(If you negated every y-coordinate in the first step, negate the y-coordinate of the result now)

(You can easily extend this approach to cover colinear segments in 3 or more dimensions)

这篇关于算法找到段与两个共线区段的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！

查看全文
相关文章
C#/.NET最新文章
热门教程
热门工具
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆