How can I find out if multiple lines overlap?-CodePudding

Each line segment has 2 xy coordinates given,

Input are below,

[3,4],[5,4]

[8,4],[20,4]

[10,4],[15,4]

In the above picture, if the lines are overlapping, it can be considered as a line segment. May I know the logic or mathematics behind solving it which outputs the 2 non-overlapping line segments which are [3,4],[5,4] and [8,4],[20,4]?

The input I gave is just 3 line segments that we have to filter out to non-overlapping line segments, so this gets complicated fast with more line segments if we don't have the proper mathematics. I am doing this because I faced this bug in my programming :).

I will appreciate any help that I can obtain :)

My solution is I have tried to find whether 2 lines are overlapping from by using some of the logic which is A.start <= B.end && B.start <= A.end as stated in here. The current code which I am stuck on this problem is published in codepen live demo here.

CodePudding user response：

Your drawing indicates that you're using two-dimensional data points, with x and y coordinates. Finding overlapping lines in 2D requires more sophisticated logic than just checking start and end points.

However, as your sandbox example is 1D, I'll address that.

In this solution, you iterate over each of the line segments, sorted by increasing start coordinate. As you encounter each subsequent segment, you choose to either combine the two or add a new segment, depending on whether they overlap or not.

function resolveOverlaps(lines) {
  if (lines.length <= 1) return lines;

  // Sort the lines ascending by start value
  lines.sort((a, b) => a[0] - b[0]);

  let outLines = [lines[0]];
  let last = outLines[0];
  // Iterate over the lines, skipping the first one
  lines.slice(1).forEach((line) => {
    // There's an overlap, so extend the current segment's end
    if (line[0] <= last[1]) {
      last[1] = Math.max(last[1], line[1]);
    } else {
      // No overlap, start a new segment
      outLines.push(line);
      last = outLines[outLines.length - 1];
    }
  });
  return outLines;
}

CodePudding user response：

I reviewed the code and found there was nothing wrong with the logic. The problem was with the dimensions and input.

Here's the revised code.

function resolveOverlaps(lines) {
  if (lines.length <= 1) return lines;

  // Sort the lines ascending by start value
  lines.sort((a, b) => a[0][0] - b[0][0]);

  let outLines = [lines[0]];
  let last = outLines[0];
  // Iterate over the lines, skipping the first one
  lines.slice(1).forEach((line) => {
    // There's an overlap, so extend the current segment's end
    if (line[0][0] <= last[1][0]) {
      last[1][0] = Math.max(last[1][0], line[1][0]);
    } else {
      // No overlap, start a new segment
      outLines.push(line);
      last = outLines[outLines.length - 1];
    }
  });
  return outLines;
}