java - 重叠线段

Question

下图说明了我在创建曼哈顿图时遇到的问题:

Overlapping Lines

该框包围了与现有行重叠的大部分行 [(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 );

这是另一个示例图像，可让您了解曼哈顿布局:

在上图中，Dialog 和 Window 之间的线已经重叠(在此缩放下不太明显)。该图说明了如何可以有多个子类，因此检测重叠必须考虑沿同一 y 中线的多个源(sx、sy)的多个目标(tx、ty)。

midPointMap 变量是一个哈希集，每个键可以包含多个值:

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

这会将 mid-y 值映射到一组线段。

如果线与现有线段重叠，有什么想法可以不画线吗？

更新 #1

请注意，每条“总线”的线段未按特定顺序给出。

Answer 1

我可能遗漏了一些东西(例如，我不明白你为什么要这样做 - 也许你正在用不同的颜色绘制东西或其他东西？如果你只是想优化一些写操作，我我不确定你是否会真正从中获得任何东西)。

但是，假设有充分的理由这样做，我认为以下算法可行:

1. 确定所有水平线段，并按y位置降序，线段长度降序排列
2. 绘制第一条线段
3. 将第二条线段的 y 位置与列表中具有相同 y 位置的所有先前行(在本例中为第一行)进行比较。如果您没有获得精确的 y 位置匹配，请绘制线段，并对后续线段重复步骤 3
4. 如果确实获得了精确的 y 位置匹配，请比较较短线段的终点，看看它的 x 位置是否在较长线段的两个端点的 x 位置之间。如果是，那么你有重叠。如果没有，请检查另一个端点。

我假设段的布局是这样的，你不能有两个部分重叠的段，就像这样(段是 aA 和 bB):

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

如果您确实有这种可能性，那么您必须决定如何解决它。

PS - 请一定要添加一个简短的说明，说明您为什么要删除这些分割。我很好奇!