ค้นหาจุดตัดที่ไม่ซ้อนทับกันของชุดเส้นตั้งใน JavaScript

เรามีชุดของพื้นที่แนวตั้งที่กำหนดโดยพิกัด y1 และ y2 โดย y1 คือจุดเริ่มต้นและ y2 คือจุดสิ้นสุดของแต่ละพื้นที่ จุดกำเนิดของระบบพิกัดอยู่ที่มุมซ้ายบน ดังนั้น y2 จะมากกว่า y1 เสมอ

ตัวอย่าง:

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

เราต้องเขียนฟังก์ชัน JavaScript ที่รับอาร์เรย์พื้นที่ดังกล่าวเป็นอาร์กิวเมนต์แรก และตัวเลขเป็นอาร์กิวเมนต์ที่สอง เราต้องการหาจุดตัดที่ไม่ซ้อนทับกันทั้งหมดที่มีขนาดมากกว่าค่าที่กำหนด (อาร์กิวเมนต์ที่สอง) สมมติว่า 20 หน่วย

ผลลัพธ์สำหรับอาร์เรย์ข้างต้นควรเป็นดังนี้:

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

เราสามารถใช้อัลกอริทึมที่ง่ายขึ้นและใช้การคูณข้ามเพื่อค้นหาสิ่งที่ทับซ้อนกัน จากนั้นได้ส่วนร่วมโดยการวนซ้ำและกรองเฉพาะการจับคู่ที่ไม่รู้จัก

ตัวอย่างโค้ด

โค้ดสำหรับทำสิ่งนี้คือ:

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

ผลลัพธ์

ผลลัพธ์ในคอนโซลจะเป็นดังนี้:

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