如何通过相交线段分割PathGeometry多边形

Question

我已经从一系列LineSegments中构建了PathGeometry，并且我想将它分割成两个PathGeometry，并由相交的线段几何。下面是我通过这幅画的意思是：

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

我可以顺利通过LineSegments和（因此它代表一行简单对象W/A点1，点2属性）创建简单的线对象的数组。但我需要以某种方式找出哪条线位于相交线的一端，哪条线位于相交线的另一端......

这有点像几何组合方法的反义词，像我试图放在一起的几何划分方法。

任何想法？

谢谢！

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，该主题虽然主要用于GIS，但对于像这样的一般计算几何问题也很有用。