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

Question

Hi!

I have a question very similar to this: http://stackoverflow.com/questions/30080/how-to-know-if-a-line-intersects-a-plane-in-c-basic-2d-geometry

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

I think the algorithm from chris-marasti-georg was very helpful but missing the most important method - 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 forbidden area (the arbitrary polygon).

Thank you! /Erik

Answer 1

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.

Answer 2

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