How to tell if a line intersects a polygon in C#?

Question

I have a question very similar to this:

How to know if a line intersects a plane in C#?

I am searching for a method (in C#) that tells if a line is intersecting an arbitrary polygon.

I think the algorithm by Chris Marasti-Georg was very helpful, but missing the most important method, i.e. line to line intersection.

Does anyone know of a line intersection method to complete Chris Marasti-Georg's code or have anything similar?

Is there a built-in code for this in C#?

This method is for use with the Bing Maps algorithm enhanced with a forbidden area feature. The resulting path must not pass through the forbidden area (the arbitrary polygon).

Answer 1

There is no builtin code for edge detection built into the .NET framework.

Here's code (ported to C#) that does what you need (the actual algorithm is found at comp.graphics.algorithms on Google groups) :

public static PointF FindLineIntersection(PointF start1, PointF end1, PointF start2, PointF 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 PointF.Empty;

    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 PointF.Empty;

    // Find intersection point
    PointF result = new PointF();
    result.X = start1.X + (r * (end1.X - start1.X));
    result.Y = start1.Y + (r * (end1.Y - start1.Y));

    return result;
 }

Answer 2

Slightly off topic, but if the line is infinite I think there's a much simpler solution:

The line does not go through the polygon if all the point lie on the same side of the line.

With help from these two:

• Using linq or otherwise, how do check if all list items have the same value and return it, or return an “otherValue” if they don’t?
• Determine which side of a line a point lies

I got this little gem:

  public class PointsAndLines
  {
    public static bool IsOutside(Point lineP1, Point lineP2, IEnumerable<Point> region)
    {
      if (region == null || !region.Any()) return true;
      var side = GetSide(lineP1, lineP2, region.First());
      return
        side == 0
        ? false
        : region.All(x => GetSide(lineP1, lineP2, x) == side);
    }

    public static int GetSide(Point lineP1, Point lineP2, Point queryP)
    {
      return Math.Sign((lineP2.X - lineP1.X) * (queryP.Y - lineP1.Y) - (lineP2.Y - lineP1.Y) * (queryP.X - lineP1.X));
    }
  }

Answer 3

To detect collisions between polygons in our silverlight map project, we're using clipper library:

Free for commercial use, small size, great performance and very easy to use.

Clipper webpage

Answer 4

This article looks like it will help

http://www.codeproject.com/KB/recipes/2dpolyclip.aspx

This code is a two-dimensional polygon-clipping algorithm that determines precisely where a line intersects with a polygon border. This code works for both concave and convex polygons of completely arbitrary shape and is able to handle any line orientation.