Overlapping Liniensegmente

Question

Das folgende Diagramm veranschaulicht ein Problem, das ich begegnet ein Manhattan Diagramm erstellen:

Overlapping Lines

Die Box meisten der Linie umgibt [(tx, midy) - (sx, midy)] das hat eine bestehende Linie überlappt (dargestellt durch psegment im folgenden Code). Ich habe die überlappenden Pfeilspitzen (und Schwänze) entfernt und bin ein bisschen ratlos, wie man nach Überlappungen sucht. Hier

ist der problematische Code:

Line2D.Double segment = new Line2D.Double(sx, midy, tx, midy); 

    // Associate the middle-y point with the bounds of the target object. 
    // On subsequent draws of targets with a similar mid-y, make sure that 
    // there are no overlapping lines. 
    // 
    if(midPointMap.put(midy, segment) != null) { 
    //if(midy == 90) { 
    // New Line. 
    // 
    System.err.printf("NEW: (%3.2f, %3d)-(%3.2f, %3d)\n", sx, midy, tx, 
         midy); 

    for(Line2D.Double psegment : midPointMap.getValues(midy)) { 
     // Previous Line. 
     // 
     System.err.printf("OLD: (%3.2f, %3d)-(%3.2f, %3d)\n", 
         psegment.getX1(), midy, psegment.getX2(), midy); 
    } 
    //} 
    } 

    // Line for the bus. 
    // 
    result.moveTo(sx, midy); 
    result.lineTo(tx, midy); 

Hier ist ein weiteres Beispiel Bild, das Ihnen eine Vorstellung von dem Manhattan-Layout zu geben:

In der Figur unmittelbar über die Linie zwischen Dialog und Fenster wurden überlappt (bei diesem Zoom nicht ganz sichtbar). Das Bild zeigt, wie es mehrere Unterklassen geben kann, und so muss das Erkennen von Überlappungen mehrere Ziele (tx, ty) für mehrere Quellen (sx, sy) entlang derselben Mitte-y-Linie berücksichtigen.

midPointMap Die Variable ist ein Hash-Set, das mehrere Werte pro Schlüssel enthalten:

private MultiValueMap<Integer, Line2D.Double> midPointMap = 
    new MultiValueMap<Integer, Line2D.Double>(); 

Diese Karten Mitte Y-Wert gegen einen Satz von Liniensegmenten.

Irgendwelche Ideen, wie man die Linie nicht zeichnet, wenn sie ein vorhandenes Liniensegment überlappt?

Update # 1

Beachten Sie, dass Liniensegmente für jeden "Bus" sind in keiner bestimmten Reihenfolge gegeben.

Answer 1

ist eine Komplettlösung:

// If line segments would overlap, this gets set to false. 
    // 
    boolean drawSegment = true; 

    Line2D.Double segment = new Line2D.Double(sx, midy, tx, midy); 

    // Associate the middle-y point with the bounds of the target object. 
    // On subsequent draws of targets with a similar mid-y, make sure that 
    // there are no overlapping lines. 
    // 
    if(midPointMap.put(midy, segment) != null) { 
    // Check previous lines for overlap. Each previous line segment has 
    // values in the form: (sx, mid-y)-(tx, mid-y), which map to 
    // (getX1(), midy)-(getX2(), midy). 
    // 
    for(Line2D.Double psegment : midPointMap.getValues(midy)) { 
     // If the lines have the same source point, and differ in their 
     // target point, then they might overlap 
     // 
     if(sx == psegment.getX1() && tx != psegment.getX2()) { 
     double pdx = psegment.getX1() - psegment.getX2(); 
     double cdx = sx - tx; 

     // At this juncture: the mid-y points are the same, the source 
     // points of the previous segment and the current segment are the 
     // same, and the target points of the segments differ. 
     // 
     // If both lines go in the same direction (relative to the same 
     // source point), then they overlap. The difference of the tx 
     // and X2 points is how much overlap exists. 
     // 
     // There are two actionable possibilities: (1) psegment is longer 
     // than the current segment; or (2) psegment is shorter. 
     // 
     // If psegment is longer, then no segment must be drawn. If 
     // psegment is shorter, the difference between psegment and the 
     // current segment must be drawn. 
     // 
     if(tx < sx && psegment.getX2() < sx) { 
      // SEGMENT IS TO THE LEFT OF SOURCE 
      // 
      if(pdx > cdx) { 
      // If the previous segment is longer, then draw nothing. 
      // 
      drawSegment = false; 
      } 
      else { 
      // If the previous segment is shorter, then draw the 
      // difference. That is, change the source point for 
      // this segment to the target point of the previous segment. 
      // 
      sx = psegment.getX2(); 
      } 
     } 
     else if(tx > sx && psegment.getX2() > sx) { 
      // SEGMENT IS TO THE RIGHT OF SOURCE 
      // 
      if(pdx < cdx) { 
      // If the previous segment is longer, then draw nothing. 
      // 
      drawSegment = false; 
      } 
      else { 
      // If the previous segment is shorter, then draw the 
      // difference. That is, change the source point for 
      // this segment to the target point of the previous segment. 
      // 
      sx = psegment.getX2(); 
      } 
     } 
     } 
    } 
    } 

    // Draw the line for the bus. 
    // 
    if(drawSegment) { 
    result.moveTo(sx, midy); 
    result.lineTo(tx, midy); 
    } 

Wenn diese (oder vereinfacht) optimiert werden kann, würde ich wirklich gerne wissen.

Answer 2

Ich vermisse etwas (zum Beispiel, ich verstehe nicht, warum Sie das tun möchten - vielleicht zeichnen Sie Dinge in verschiedenen Farben oder etwas? Wenn Sie nur versuchen, ein paar Schreibvorgänge zu optimieren, Ich bin mir nicht sicher, dass du damit wirklich etwas erreichen wirst.

Aber, vorausgesetzt, es ist ein guter Grund, dies zu tun, glaube, ich würde, dass der folgende Algorithmus funktionieren würde:

1. alle Segmente horizontale Linie zu ermitteln, und um von y-Position absteigend und Längensegment absteigend
2. Zeichnen Sie das erste Liniensegment
3. Vergleichen Sie die y-Position des zweiten Liniensegments mit allen vorherigen Linien in der Liste (in diesem Fall nur die ersten), die dieselbe y-Position haben. Wenn Sie keine exakte Y-Positionsübereinstimmung erhalten, zeichnen Sie das Segment und wiederholen Sie Schritt 3 für nachfolgende Segmente.
4. Wenn Sie eine genaue Y-Positionsübereinstimmung erhalten, vergleichen Sie den Endpunkt des kürzeren Segments, um zu sehen, ob es x ist Position liegt zwischen der x-Position der beiden Endpunkte des längeren Segments. Wenn dies der Fall ist, haben Sie Überschneidungen. Ist dies nicht der Fall, überprüfen Sie den anderen Endpunkt.

Ich gehe davon aus, dass das Layout der Segmente so ist, dass man nicht zwei Segmente haben können, die einander teilweise überlappen, wie dies (Segmente sind aA und bB):

a === == b === A ========= B

Wenn Sie diese Möglichkeit haben, dann müssen Sie entscheiden, wie Sie das lösen können.

PS - bitte fügen Sie unbedingt eine kurze Beschreibung von warum Sie diese Segmente zu beseitigen möchten. Ich bin neugierig! Hier