Polyline-Shifting-Algorithmus

Question

Ich habe eine Liste mit Polylinien (PointCollection) wie in der Grafik gezeigt. Einige Segmente überlappen sich wie die blaue und orange Linie, wie in "Original" gezeigt. Ich weiß schon, welche Segmente das sind. Ich muss die überlappenden Segmente auseinander schieben. Das Schwierige ist, neue Überlappungen mit anderen Zeilen zu vermeiden, wie sie in "falsch" angezeigt werden.

Ich habe das Problem, dass ich nur die Koordinaten der Knoten und keine Informationen über die Segmente haben. Gibt es eine Möglichkeit zu bestimmen, ob ich einen Knoten auf ein Segment einer anderen Linie verschiebe? Hat jemand eine gute Idee wie ich dieses Problem lösen könnte?

Answer 1

Wie in den Kommentaren darauf hingewiesen haben Sie eine Auswahl an

• das Problem analytisch durch geometrische Berechnungen zu lösen oder von
• einige + Methoden GDI mit

Hier ist ein Beispiel für letzteres ist:

Zuerst muss Ihre Konsolenanwendung einen Verweis auf System.Drawing und einige using-Klauseln enthalten:

using System.Drawing; 
using System.Drawing.Drawing2D; 
using System.Drawing.Imaging; //optional, used for bitmap saving only 

Hier ist eine statische Funktion, wenn zwei GraphicsPaths Tests schneiden:

static bool intersect(GraphicsPath gp1, GraphicsPath gp2, Graphics g) 
{ 
    using (Region reg = new Region(gp1)) 
    { 
     reg.Intersect(gp2); 
     return !reg.IsEmpty(g); 
    } 
} 

Es dauert zwei GraphicsPaths und aslo ein Graphics Objekt.

Hier ist ein Testbed, um zu demonstrieren, wie man es benutzen kann. Es erzeugt 2 zufällige Polylinien und verschiebt dann die zweite um jeweils 50 Pixel nach rechts, bis sie die erste nicht mehr schneidet.

Alle Stufen werden in eine Bitmap gezeichnet, die gespeichert wird dann ..:

kann

Sie die Bahnpunkte verschoben Zugriff als:

static void Main(string[] args) 
{ 
    int w = 1234; 
    int h = 1234; 

    Random rnd = new Random(0); 
    for (int t = 0; t < 33; t++) 
    { 
     List<Point> l1 = new List<Point>(); 
     List<Point> l2 = new List<Point>(); 
     for (int i = 0; i < 4; i++) 
     { 
      l1.Add(new Point(rnd.Next(1234), rnd.Next(567))); 
      l2.Add(new Point(rnd.Next(567), rnd.Next(1234))); 
     } 

     using (Matrix m = new Matrix()) 
     using (Bitmap bmp = new Bitmap(w, h)) 
     using (Graphics g = Graphics.FromImage(bmp)) 
     using (GraphicsPath gp1 = new GraphicsPath()) 
     using (GraphicsPath gp2 = new GraphicsPath()) 
     { 
      gp1.AddLines(l1.ToArray()); 
      gp2.AddLines(l2.ToArray()); 
      m.Translate(50, 0); 
      bool intersects = intersect(gp1, gp2, g); 
      g.Clear(Color.White); 
      g.DrawPath(Pens.Blue, gp1); 
      g.DrawPath(intersects ? Pens.Red : Pens.Green, gp2); 

      while (intersects) 
      { 
       gp2.Transform(m); 
       intersects = intersect(gp1, gp2, g); 
       g.DrawPath(intersects ? Pens.Red : Pens.Green, gp2); 
       intersects = intersect(gp1, gp2, g); 
      } 


      bmp.Save(@"D:\scrape\x\__xTest_" + t.ToString("000") + ".png", 
        ImageFormat.Png); 

     } 
    } 
} 

Hier einer der Ausgabedateien ist

List<PointF> l3 = gp2.PathPoints.ToList(); 

Beachten Sie, dass Sie entweder diemachen solltengroß genug für Ihre tatsächlichen Zahlen oder skalieren Sie sie und arbeiten Sie mit floats!