1
\$\begingroup\$

I've been looking for a c# algorithm to help determine if shapes and lines intersect but want to exclude boundary overlaps. Here's an example:

enter image description here

My true problem is finding if polygons intersect but exclude boundary overlaps. I broke down the problem to look at the individual lines of that polygon and check each line segment from the shape1 against each line segment from shape2.

A: Is this an efficient/correct way to do the checking?

B: How do I ignore when they are on the boundary as illustrated above?

Here's some code I found here - I've been testing for line segments but it fails on fig 2, when the end point of the 2nd line segment finishes on the end point of the 1st segment.

private bool DoesLineIntersect(Vector2 start1, Vector2 end1, Vector2 start2, Vector2 end2)
{
    float denom = ((end1.x - start1.x) * (end2.y - start2.y)) - ((end1.y - start1.y) * (end2.x - start2.x));

    //  AB & CD are parallel 
    if (denom == 0)
        return false;

    float numer = ((start1.y - start2.y) * (end2.x - start2.x)) - ((start1.x - start2.x) * (end2.y - start2.y));

    float r = numer / denom;

    float numer2 = ((start1.y - start2.y) * (end1.x - start1.x)) - ((start1.x - start2.x) * (end1.y - start1.y));

    float s = numer2 / denom;

    if ((r < 0 || r > 1) || (s < 0 || s > 1))
        return false;

    return true;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Just throwing a random idea out here: What if you change the line if ((r < 0 || r > 1) || (s < 0 || s > 1)) to if ((r =< 0 || r >= 1) || (s =< 0 || s >= 1))? \$\endgroup\$ – Tyyppi_77 Sep 24 '16 at 16:18
  • \$\begingroup\$ Yeah it works :) passes tests. Note =< is <= ;) \$\endgroup\$ – dolyth Sep 25 '16 at 14:18
1
\$\begingroup\$

You need to change your final check to also check for equality. So change the line

if ((r < 0 || r > 1) || (s < 0 || s > 1)) 

to

if ((r <= 0 || r >= 1) || (s <= 0 || s >= 1))
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.