0
\$\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\$
2
  • 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\$
    – user35344
    Sep 24, 2016 at 16:18
  • \$\begingroup\$ Yeah it works :) passes tests. Note =< is <= ;) \$\endgroup\$
    – dolyth
    Sep 25, 2016 at 14:18

1 Answer 1

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\$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .