Given 4 points of a rectangle, disregarding the 4 points, do any sides intersect?

Question

I'm messing around with some object recognition samples for 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
}

However, I get some fishy results such as this (grey ish):

enter image description here

And (red):

enter image description here

I get some other bad results too, but I notice a trend with these. These rectangles (or technically trapezoids...?) have some lines that cross over or lay on top of each other. I want to ignore drawing these results if that's the case. Is there a way to determine this given the 4 points?

UPDATE: At request of user @Chris , I check out this answer. I attempted to replicate the pseudo code. However, I may be misunderstanding it. It doesn't give the expected results. It seems to always return true. This may be because I translated the pseudo code wrong.

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

http://stackoverflow.com/questions/3838329/how-can-i-check-if-two-segments-intersect may be of help (you could use that to test opposite edges to see if they intersect). — Chris, Jun 26 '14 at 15:50
@Chris I attempted to follow the checked answer, but it doesn't work for me. — But I'm Not A Wrapper Class, Jun 26 '14 at 19:08
:( I found that because I figured this must be a solved problem somewhere so just googled. I didn't actually follow the solution and don't have time to work through it to find the issues at the moment. I'll perhaps come back to it later if I find free time though. good luck in the meantime! — Chris, Jun 27 '14 at 08:20

But I'm Not A Wrapper Class · Accepted Answer · 2014-06-27T15:22:22.180

I found a really cool simplified method online. I simplified it a bit as so:

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
}

After some tweaking and debugging on some of the way I round the Points in the lines (basically some code prior to this), I figured something small in the code I need to adjust. After fixing that, this solution actually works!

Given 4 points of a rectangle, disregarding the 4 points, do any sides intersect?

1 Answers1