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

Question

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

Перекрывающиеся линии

Рамка окружает большую часть строки [(tx, 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 );

Вот еще один пример изображения, чтобы дать вам представление о планировке Манхэттена:

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

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

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

Отображает средние значения y для набора отрезков.

Есть идеи, как не рисовать линию, если она перекрывает существующий отрезок?

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

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

Answer 1

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

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

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

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

а ===== б === ========= В

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

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

Answer 2

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

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

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