How to split a PathGeometry Polygon by an intersecting line segment

Question

I've got a PathGeometry that I've built from a bunch of LineSegments, and I want to split it into two PathGeometries divided by a line intersecting down the middle of the geometry. Here's what I mean by this picture:

http://i30.tinypic.com/2noyvm.png

I can go through the LineSegments and create an array of simple line objects (simple object w/ a Point1, Point2 property so that it represents one line). But i need to somehow figure out which Lines were on one end of the intersect line, and which lines were on the other end of the intersect line...

This is sort of like the opposite of a geometry combine method, something like a geometry divide method that I'm trying to put together.

Any ideas?

Thanks!

Answer 1

Well, that was fun, here's what I did (I honestly have no idea if this is the "right" way of if there is a more efficient way).

1. Create a transform that moves the geometry so that the dividing line is on the Y axis.
2. For each line in the geometry - if X<0 it's on the left, if X>0 it's on the right, if the line crosses the the Y axis divide it into two lines.
3. Transform both lists of lines using the inverse of the transform from step 1 and rebuild a geometry from them.

Here's a SplitGeometry method that takes a geometry and a line defined by two points and returns the two geometries:

    private void SplitGeometry(Geometry geo, Point pt1, Point pt2, out PathGeometry leftGeo, out PathGeometry rightGeo)
    {
        double c = 360.0 + 90.0 - (180.0 / Math.PI * Math.Atan2(pt2.Y - pt1.Y, pt2.X - pt1.X));
        var t = new TransformGroup();
        t.Children.Add(new TranslateTransform(-pt1.X, -pt1.Y));
        t.Children.Add(new RotateTransform(c));
        var i = t.Inverse;
        leftGeo = new PathGeometry();
        rightGeo = new PathGeometry();
        foreach (var figure in geo.GetFlattenedPathGeometry().Figures)
        {
            var left = new List<Point>();
            var right = new List<Point>();
            var lastPt = t.Transform(figure.StartPoint);
            foreach (PolyLineSegment segment in figure.Segments)
            {
                foreach (var currentPtOrig in segment.Points)
                {
                    var currentPt = t.Transform(currentPtOrig);
                    ProcessLine(lastPt, currentPt, left, right);
                    lastPt = currentPt;
                }
            }
            ProcessFigure(left, i, leftGeo);
            ProcessFigure(right, i, rightGeo);
        }
    }

    private void ProcessFigure(List<Point> points, GeneralTransform transform, PathGeometry geometry)
    {
        if (points.Count == 0) return;
        var result = new PolyLineSegment();
        var prev = points[0];
        for (int i = 1; i < points.Count; ++i)
        {
            var current = points[i];
            if (current == prev) continue;
            result.Points.Add(transform.Transform(current));
            prev = current;
        }
        if (result.Points.Count == 0) return;
        geometry.Figures.Add(new PathFigure(transform.Transform(points[0]), new PathSegment[] { result }, true));
    }

    private void ProcessLine(Point pt1, Point pt2, List<Point> left, List<Point> right)
    {
        if (pt1.X >= 0 && pt2.X >= 0)
        {
            right.Add(pt1);
            right.Add(pt2);
        }
        else if (pt1.X < 0 && pt2.X < 0)
        {
            left.Add(pt1);
            left.Add(pt2);
        }
        else if (pt1.X < 0)
        {
            double c = (Math.Abs(pt1.X) * Math.Abs(pt2.Y - pt1.Y)) / Math.Abs(pt2.X - pt1.X);
            double y = pt1.Y + c * Math.Sign(pt2.Y - pt1.Y);
            var p = new Point(0, y);
            left.Add(pt1);
            left.Add(p);
            right.Add(p);
            right.Add(pt2);
        }
        else
        {
            double c = (Math.Abs(pt1.X) * Math.Abs(pt2.Y - pt1.Y)) / Math.Abs(pt2.X - pt1.X);
            double y = pt1.Y + c * Math.Sign(pt2.Y - pt1.Y);
            var p = new Point(0, y);
            right.Add(pt1);
            right.Add(p);
            left.Add(p);
            left.Add(pt2);
        }
    }

Answer 2

The way to figure out which lines are on which side of the intersection line is to compute the sign of the determinant of the line endpoints relative to the intersection line. Positive is one side, negative is the other.

If you want to have more sophisticated intersection, say, within the interior of a line-segment, then you need to build a graph of doubly-directed edges and vertexes and compute the intersection of the intersecting line and each polygon edge. You then insert vertexes where the line intersects edges and retrace the graph, building a polygon from the directed edges as you follow one to the other.

If you are looking for an implementation of this, check out Net Topology Suite, which, while used primarily for GIS, is also useful for general computational-geometry problems like this.