Перекрывающиеся отрезки

Question

Следующая диаграмма иллюстрирует проблему, я столкнулся созданием Manhattan диаграммы:

Overlapping Lines

Коробка окружает большую часть линии [(ТЙ, midy) - (Sx, midy)], что перекрыл существующую строку (представленную ниже кодом psegment). Я удалил перекрывающиеся головки стрелок (и хвосты), и я немного зациклен на том, как проверить наложение.

Вот проблемный код:

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

Вот другой пример изображения, чтобы дать вам представление о макете Manhattan:

На рисунке непосредственно выше, линия между Диалоговое окно и окно перекрыты (это не очень заметно при этом увеличении). Изображение иллюстрирует, как могут быть несколько подклассов, и поэтому обнаружение перекрытия должно учитывать несколько целей (tx, ty) для нескольких источников (sx, sy) вдоль одной и той же линии среднего y.

midPointMap переменная является хэш-набор, который может содержать несколько значений в ключе:

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

Эта карта среднего значения Y от набора отрезков.

Любые идеи о том, как не нарисовать линию, если она перекрывает существующий сегмент линии?

Обновление # 1

Обратите внимание, что сегменты линии для каждого «шины» приведены в произвольном порядке.

Answer 1

Вот полное решение:

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

Если это может быть оптимизировано (или упрощенный), я действительно хотел бы знать.

Answer 2

Возможно, у меня что-то не хватает (например, я не понимаю, почему вы хотите это сделать - возможно, вы рисуете вещи разными цветами или что-то в этом роде? Если вы просто пытаетесь оптимизировать несколько операций записи, Я не уверен, что вы действительно получите что-либо от этого).

Но, предполагая, что есть хороший повод, чтобы сделать это, я думаю, что следующий алгоритм работы:

1. Определить все горизонтальные отрезки, и порядок по у позиции нисходящие и длина сегмента по убыванию
2. Нарисуйте первый отрезок линии
3. Сравните позицию y второго положения сегмента со всеми предыдущими строками списка (в данном случае только с первым), которые имеют одинаковую позицию y. Если вы не получите точное совпадение y-позиции, нарисуйте сегмент и повторите шаг 3 для последующих сегментов.
4. Если вы получаете точное совпадение позиции y, сравните конечную точку более короткого сегмента, чтобы увидеть, положение находится между положением x двух конечных точек более длинного сегмента. Если это так, то у вас есть совпадение. Если это не так, проверьте другую конечную точку.

Я предполагаю, что расположение сегментов такова, что вы не можете иметь два сегмента, которые частично перекрывают друг друга, как это (сегменты АА и ВВ):

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

Если у вас есть такая возможность, вам придется решить, как это решить.

PS - пожалуйста, обязательно добавьте краткое описание , почему вы хотите устранить эти сегменты. Мне любопытно!