Daily Archives: August 28, 2009

Getting the intersection points of two [path] geometries in WPF

While working on an app that utilises geometries in WPF, I needed a way to get the intersection points of the lines of two arbitrary geometries. A google search didn’t yield any useful hints except a post suggesting to use mathematics. That would be ideal for very simple geometries like lines, but with complex geometries, it becomes tiresome real quick. The framework doesn’t seem to have any built in functions that calculate that, so it’s time for some hack and slash.

After a few days of thinking, I came up with a simple, yet effective (but not the most efficient solution). For those who just want the intersection between two geometries, there is the CombinedGeometry geometry class which takes input in the form of two geometries. Setting the GeometryCombineMode to Intersect gives a geometry which is the intersection of the two. At the otherside of the WPF realm, we have Geometry.GetWidenedPathGeometry(). This method basically converts/strokes path lines to an approximate geometry. Combining these two concepts, we can produce an intersection from two widened path geometries (the two paths which we want the intersection of).

[csharp]
public static Point[] GetIntersectionPoints(Geometry g1, Geometry g2)
{
Geometry og1 = g1.GetWidenedPathGeometry(new Pen(Brushes.Black, 1.0));
Geometry og2 = g2.GetWidenedPathGeometry(new Pen(Brushes.Black, 1.0));

CombinedGeometry cg = new CombinedGeometry(GeometryCombineMode.Intersect, og1, og2);

PathGeometry pg = cg.GetFlattenedPathGeometry();
Point[] result = new Point[pg.Figures.Count];
for (int i = 0; i < pg.Figures.Count; i++)
{
Rect fig = new PathGeometry(new PathFigure[] { pg.Figures[i] }).Bounds;
result[i] = new Point(fig.Left + fig.Width / 2.0, fig.Top + fig.Height / 2.0);
}
return result;
}
[/csharp]

The function will return an array of zero or more points of intersection. To test it

[csharp]
sg1 = StreamGeometry.Parse("M0,0 L100,100");
sg2 = StreamGeometry.Parse("M0,100 L100,0");
Point[] pts = GetIntersectionPoints(sg1, sg2);
// pts[0] is {50,50}
[/csharp]

Hope this helps someone.