Question 11311 in Jquery Question posted in
The official Jquery Api Documentation can be found here.

How can I find out if multiple lines overlap? – Jquery

enter image description here

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.

Tags:

2

Answers


  1. 0

    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;
  if (lines[0].length !== 2 || typeof lines[0][0] !== "number") {
    throw new Error(
      "Invalid input shape. resolveOverlaps requires a list of N tuples like `[[start0, end0], ..., [startN, endN]]`"
    );
  }
  for (const line of lines) {
    if (line[0] > line[1]) {
      throw new Error(
        `Invalid segment [${line[0]}, ${line[1]}]. Ensure startend.`
      );
    }
  }

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

    Edit: Here’s an implementation for 2D segments which assumes that all points lie on the same line, and thus only needs to check the x coordinate of each point. A general 2D solution requires more sophisticated logic than this.

    function resolveOverlaps2d(lines) {
  if (lines.length <= 1) return lines;
  if (lines[0].length !== 2 || lines[0][0].length !== 2) {
    throw new Error(
      "Invalid input shape. resolveOverlaps requires a list of N tuples like `[[[x0_0, y0_0], [x0_1, y0_1]], ..., [[xN_0, yN_0], [xN_1, yN_1]]]"
    );
  }
  for (const line of lines) {
    if (line[0][0] > line[1][0]) {
      throw new Error(
        `Invalid segment [${line[0]}, ${line[1]}]. Ensure start <= end.`
      );
    }
  }

  // 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;
}
    Login or Signup to reply.
  2. 0

    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;
}
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search