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

Question

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

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

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

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

Есть идеи?

Спасибо!

Answer 1

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

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

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

Answer 2

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

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