Как разделить многоугольник PathGeometry пересекающимся отрезком

Question

У меня есть PathGeometry, которую я построил из набора LineSegment, и я хочу разделить его на две PathGeometry, разделенные линией, пересекающей середину геометрии. Вот что я имею в виду под этой картиной:

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

Я могу пройти через LineSegments и создать массив простых линейных объектов (простой объект со свойством Point1, Point2, чтобы он представлял одну линию). Но мне нужно каким-то образом выяснить, какие линии были на одном конце линии пересечения, а какие - на другом конце линии пересечения...

Это что-то вроде метода объединения геометрии, что-то вроде метода разделения геометрии, который я пытаюсь собрать.

Есть идеи?

Спасибо!

Answer 1

Ну, это было весело, вот что я сделал (я, честно говоря, понятия не имею, если это "правильный" способ, если есть более эффективный способ).

1. Создайте преобразование, которое перемещает геометрию так, чтобы разделительная линия находилась на оси Y.
2. Для каждой линии в геометрии - если X<0 - слева, если X>0 - справа, если линия пересекает ось Y, разделите ее на две линии.
3. Преобразуйте оба списка линий, используя обратное преобразование из шага 1, и восстановите геометрию из них.

Вот метод SplitGeometry, который берет геометрию и линию, заданную двумя точками, и возвращает две геометрии:

    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

Способ выяснить, какие линии находятся на какой стороне линии пересечения, состоит в том, чтобы вычислить знак определителя конечных точек линии относительно линии пересечения. Положительный - это одна сторона, отрицательный - другая.

Если вы хотите иметь более сложное пересечение, скажем, внутри отрезка, то вам нужно построить график двунаправленных ребер и вершин и вычислить пересечение пересекающейся линии и каждого ребра многоугольника. Затем вы вставляете вершины, где линия пересекает ребра, и восстанавливаете график, создавая многоугольник из направленных ребер, когда вы следуете друг за другом.

Если вы ищете реализацию этого, посмотрите Net Topology Suite, который, хотя и используется в основном для ГИС, также полезен для общих задач вычислительной геометрии, подобных этой.