c# – 用于查找重叠两个共线段的段的算法

更新

>我在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,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,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,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,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;
}

解决方法

这个问题大致相当于测试两个轴对齐的矩形是否相交：你可以威胁每个段作为轴对齐矩形的对角线,然后你需要找到这两个矩形的交点.以下是我用于矩形交叉的方法.

让我们假设段的斜率是上升的,垂直的或水平的;如果段正在下降,则否定每个y坐标以使它们上升.

为每个线段定义MinPoint和MaxPoint：

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

现在交叉点由以下两点给出：两个最小值的最大值,以及两个最大值的最小值

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

就是这样.要检查两个段是否相交,请检查

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

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

(如果在第一步中否定了每个y坐标,则现在否定结果的y坐标)

(您可以轻松扩展此方法以覆盖3个或更多维度的共线段)

c# – 用于查找重叠两个共线段的段的算法

解决方法

猜你在找的C#相关文章