Tìm tất cả các giao điểm rời rạc trong một tập hợp các đoạn đường thẳng đứng trong JavaScript

Chúng tôi có một tập hợp các vùng thẳng đứng được xác định bởi các tọa độ y1 và y2, trong đó y1 là điểm bắt đầu và y2 là điểm kết thúc của mỗi vùng.

Gốc của hệ tọa độ của chúng ta là góc trên cùng bên trái, vì vậy y2 luôn lớn hơn y1.

Đây là một ví dụ -

const regions = [
   [10, 100],
   [50, 120],
   [60, 180],
   [140, 220]
];

Chúng tôi được yêu cầu viết một hàm JavaScript lấy một mảng vùng như vậy làm đối số đầu tiên và một số làm đối số thứ hai.

Chúng tôi muốn tìm ra tất cả các giao điểm rời rạc lớn hơn một kích thước nhất định, (được chỉ định bởi đối số thứ hai của hàm).

Ví dụ, giả sử là 20 đơn vị.

Sau đó, đầu ra cho mảng trên sẽ giống như -

const output = [
   [60, 100],
   [140, 180]
];

Chúng tôi có thể sử dụng một thuật toán đơn giản hóa và sử dụng trên toàn bộ sản phẩm để tìm kiếm các mặt hàng chồng chéo.

Sau đó, lấy các phần chung bằng cách lặp lại và chỉ lọc các kết quả phù hợp không xác định.

Ví dụ

Mã cho điều này sẽ là -

const regions = [
   [10, 100],
   [50, 120],
   [60, 180],
   [140, 220]
];
const getIntersections = (arr,num) => {
   let disjoint, res;
   return arr.reduce((acc,val,ind,array) => {
      if (val.used){
         return acc;
      };
      res = array.map((el, index) => array[(ind + index) % array.length]) .reduce((s,e) => {
         disjoint = [Math.max(s[0],e[0]), Math.min(s[1],e[1])];
         return disjoint[0] < disjoint[1] ? (e.used = true, disjoint) : s;
      });
      res[1] - res[0] > num && acc.push(res);
      return acc;
   },[]);
}
console.log(getIntersections(regions, 20));

Đầu ra

Và đầu ra trong bảng điều khiển sẽ là -

[ [ 60, 100 ], [ 140, 180 ] ]