Overlapping line segments

Question

The following diagram illustrates a problem I have encountered creating a Manhattan diagram:

Overlapping Lines

The box surrounds most of the line [(tx,midy)-(sx,midy)] that has overlapped an existing line (represented by psegment in the code below). I have removed the overlapping arrow heads (and tails) and am a little stumped on how to check for overlap.

Here is the problematic 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 );

Here is another example image to give you an idea of the Manhattan layout:

In the figure immediately above, the line between Dialog and Window has been overlapped (not quite visible at this zoom). The image illustrates how there can be multiple subclasses, and so detecting overlap must take into consideration multiple targets (tx, ty) for multiple sources (sx, sy) along the same mid-y line.

The midPointMap variable is a hash set that can contain multiple values per key:

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

This maps mid-y values against a set of line segments.

Any ideas how to not draw the line if it overlaps an existing line segment?

Update #1

Note that line segments for each "bus" are given in no particular order.

Answer 1

Here is a complete solution:

  // 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

I may be missing something (for example, I don't understand why you'd want to do this - maybe you are drawing things in different colors or something? If you are just trying to optimize a few write operations, I'm not sure that you are going to really gain anything by this).

But, assuming there is a good reason to do this, I'd think that the following algorithm would work:

1. Determine all horizontal line segments, and order by y position descending and segment length descending
2. Draw the first line segment
3. Compare the second line segment's y-position to all previous lines in the list (in this case, just the first) that have the same y position. If you don't get an exact y-position match, draw the segment, and repeat step 3 for subsequent segments
4. If you do get an exact y position match, compare the end point of the shorter segment to see if it's x position is between the x position of the two end points of the longer segment. If it is, then you have overlap. If it doesn't, check the other end point.

I'm assuming that the layout of the segments is such that you can't have two segments that partially overlap each other, like this (segments are aA and bB):

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

If you do have that possibility, then you'll have to decide how to resolve that.

PS - please definitely add a brief description of why you want to eliminate those segments. I'm curious!