Overlapping line segments

Answer 1

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!

Answer 2

Instead of having multiple line segments how about one line segment per midy.

Then

Graphics2D g2 = (Graphics2D)g;

Double left = tx < sx ? tx : sx; 
Double right = tx > sx ? tx : sx;

Line2D.Double seg = midPointMap.getValue( midy );

psegment.setLine( left < seg.getX1() ? left : seg.getX1(), midy, 
                 right < seg.getX2() ? right : seg.getX2(), midy );

//  etc.

g2.drawShape( seg );

This way you have one horizontal line segment from the minimum x to the maximum x at y.

Answer 3

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

If this can be optimized (or simplified), I would really like to know.