c# - 给定矩形的 4 个点，忽略这 4 个点，是否有任何边相交？

Question

我正在为 EMGU 处理一些对象识别样本:

Rectangle rect = modelImage.ROI;

PointF p1 = new PointF(rect.Left, rect.Bottom);
PointF p2 = new PointF(rect.Right, rect.Bottom);
PointF p3 = new PointF(rect.Right, rect.Top);
PointF p4 = new PointF(rect.Left, rect.Top);

//check if any opposite lines intersect
//if so, then don't add to final results
//we should never have 2 opposite sides intersecting
LineSegment2DF l1 = new LineSegment2DF(p1,p2);
LineSegment2DF l2 = new LineSegment2DF(p2, p3);
LineSegment2DF l3 = new LineSegment2DF(p3, p4);
LineSegment2DF l4 = new LineSegment2DF(p4, p1)

if (!(intersects(l1, l3) || intersects(l2, l4))) 
{
    //draw line
}

但是，我得到了一些可疑的结果，例如这个(灰色):

和(红色):

我也得到了其他一些不好的结果，但我注意到了这些的趋势。这些矩形(或者技术上是梯形……？)有一些线相互交叉或重叠。如果是这样的话，我想忽略绘制这些结果。有没有办法根据 4 点来确定这一点？

更新:应用户@Chris 的要求，我查看了this answer .我试图复制伪代码。但是，我可能会误解它。它没有给出预期的结果。它似乎总是返回 true。这可能是我把伪代码翻译错了。

public static bool intersects(LineSegment2DF l1, LineSegment2DF l2)
{
    float x1 = l1.P1.X;
    float x2 = l1.P2.X;
    float x3 = l2.P1.X;
    float x4 = l2.P2.X;
    float y1 = l1.P1.Y;
    float y2 = l1.P2.Y;
    float y3 = l2.P1.Y;
    float y4 = l2.P2.Y;

    float intervalAMin = Math.Min(x1, x2);
    float intervalAMax = Math.Max(x1, x2);
    float intervalBMin = Math.Min(x3, x4);
    float intervalBMax = Math.Max(x3, x4);

    //if (Math.Max(l1.P1.X, l1.P2.X) < Math.Min(l2.P1.X, l2.P2.X)) return false;
    if(intervalAMax < intervalBMin) return false;

    float a1 = (y1-y2)/(x1-x2); // Pay attention to not dividing by zero
    float a2 = (y3-y4)/(x3-x4); // Pay attention to not dividing by zero
    if (a1 == a2) return false; // Parallel segments

    float b1 = y1-a1*x1;// = y2-a1*x2;
    float b2 = y3-a2*x3;// = y4-a2*x4;

    float xa = (b2 - b1) / (a1 - a2);// Once again, pay attention to not dividing by zero
    float ya = a1 * xa + b1;
    //float ya = a2 * xa + b2;

    if ((xa < Math.Max(Math.Min(x1, x2), Math.Min(x3, x4))) || (xa > Math.Min(Math.Max(x1, x2), Math.Max(x3, x4)))) return false; // intersection is out of bound
    return true;
}

Answer 1

我真的找到了cool simplified method online .我将其简化为:

public static bool Intersects2DF(LineSegment2DF thisLineSegment, LineSegment2DF otherLineSegment)
{
    float firstLineSlopeX, firstLineSlopeY, secondLineSlopeX, secondLineSlopeY;

    firstLineSlopeX = thisLineSegment.P2.X - thisLineSegment.P1.X;
    firstLineSlopeY = thisLineSegment.P2.Y - thisLineSegment.P1.Y;

    secondLineSlopeX = otherLineSegment.P2.X - otherLineSegment.P1.X;
    secondLineSlopeY = otherLineSegment.P2.Y - otherLineSegment.P1.Y;

    float s, t;
    s = (-firstLineSlopeY * (thisLineSegment.P1.X - otherLineSegment.P1.X) + firstLineSlopeX * (thisLineSegment.P1.Y - otherLineSegment.P1.Y)) / (-secondLineSlopeX * firstLineSlopeY + firstLineSlopeX * secondLineSlopeY);
    t = (secondLineSlopeX * (thisLineSegment.P1.Y - otherLineSegment.P1.Y) - secondLineSlopeY * (thisLineSegment.P1.X - otherLineSegment.P1.X)) / (-secondLineSlopeX * firstLineSlopeY + firstLineSlopeX * secondLineSlopeY);

    if (s >= 0 && s <= 1 && t >= 0 && t <= 1)
    {
        // Collision detected
        return true;
    }
    return false; // No collision
}

在对行中的 Point 进行一些调整和调试之后(基本上是在此之前的一些代码)，我发现代码中有一些小问题需要调整。修复该问题后，此解决方案实际上有效!