2010-07-08 181 views
1

我已經從一系列LineSegments中構建了PathGeometry,並且我想將它分割成兩個PathGeometry,並由相交的線段幾何。下面是我通過這幅畫的意思是:如何通過相交線段分割PathGeometry多邊形

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

我可以順利通過LineSegments和(因此它代表一行簡單對象W/A點1,點2屬性)創建簡單的線對象的數組。但我需要以某種方式找出哪條線位於相交線的一端,哪條線位於相交線的另一端......

這有點像幾何組合方法的反義詞,像我試圖放在一起的幾何劃分方法。

任何想法?

謝謝!

回答

0

那麼,那很有趣,這就是我所做的(我真的不知道這是否是一種更有效的方式的「正確」方式)。

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

令人印象深刻!這是非常好的。我在做這件事之前所做的事情是在多邊形周圍畫一個邊界框,然後將該邊界框按行分開,分成兩個多邊形(一個是boundingbox.topleft,line.topPoint,line.bottomPoint,boundingbox.bottomleft),然後找到所有原始多邊形的點位於那些分離的邊界框多邊形中...它的工作,但你的impl可能會更強大(至少看起來更乾淨)。 – softwarequestioneer 2010-07-08 17:54:37

1

找出哪條線位於交線的哪一側將計算線端點相對於相交線的行列式的符號的方法。正面是一面,負面是另一面。如果你想有更復雜的交點,比如在線段內部,那麼你需要建立一個雙向邊和頂點的圖,並計算相交線和每個多邊形邊的交點。然後插入線與頂點相交的頂點並回溯圖形,從一個邊到另一個邊從有向邊構建一個多邊形。

如果您正在尋找這個實現,請查看Net Topology Suite,該主題雖然主要用於GIS,但對於像這樣的一般計算幾何問題也很有用。

+0

你可以給一個更詳細一點對於如何計算一行的決定因素端點相對於相交線? – softwarequestioneer 2010-07-08 02:21:18

+0

當然,你應該能夠遵循這個:http://www.math.niu.edu/~rusin/known-math/95/line_segs – codekaizen 2010-07-08 02:23:26

+0

你可以在這裏找到一個行相交/行列式計算機的具體例子:http ://code.google.com/p/nettopologysuite/source/browse/trunk/NetTopologySuite/Algorithm/RobustLineIntersector.cs – codekaizen 2010-07-08 02:33:17