Tìm tất cả các giao điểm không giao nhau của đoạn thẳng dọc trong JavaScript

Chúng ta có tập hợp các vùng dọc được định nghĩa bằng tọa độ y1 và y2, trong đó y1 là điểm bắt đầu và y2 là điểm kết thúc. Hệ tọa độ gốc ở góc trên bên trái, nên y2 luôn lớn hơn y1.

Ví dụ:

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

Cần viết hàm nhận mảng vùng làm đối số đầu tiên và một số làm đối số thứ hai. Chúng ta muốn tìm tất cả các giao điểm không giao nhau lớn hơn kích thước nhất định (được chỉ định bởi đối số thứ hai).

Giả sử ngưỡng là 20 đơn vị. Khi đó đầu ra cho mảng trên sẽ là:

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

Có thể dùng thuật toán đơn giản với tích Descartes để tìm các mục chồng chéo, sau đó lấy phần chung bằng cách lặp và lọc các kết quả trùng lặp.

Ví dụ

Mã thực hiện như sau:

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

Kết quả

Kết quả trong console sẽ là:

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