ค้นหาทางแยกที่ไม่ปะติดปะต่อทั้งหมดในชุดของเซ็กเมนต์เส้นแนวตั้งใน 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 ] ]