ตรวจสอบรูปหลายเหลี่ยมคูน (Convex Polygon) ใน JavaScript

Convex Polygon

รูปหลายเหลี่ยมที่มุมภายในทุกมุมน้อยกว่า 180 องศา

ปัญหา

รับอาร์เรย์พิกัด [[x,y], ...] ตรวจสอบว่าจุดเหล่านี้สร้าง Convex Polygon ได้หรือไม่

ตัวอย่าง

const arr = [[0,0],[0,1],[1,1],[1,0]];

เป็นสี่เหลี่ยมจัตุรัส มุม 90 องศา → true

โค้ดตัวอย่าง (Cross Product)

const arr = [[0,0],[0,1],[1,1],[1,0]]; 
const isConvex = (arr = []) => { 
  const { length } = arr; 
  let pre = 0, curr = 0; 
  for (let i = 0; i < length; ++i) { 
    let dx1 = arr[(i + 1) % length][0] - arr[i][0]; 
    let dx2 = arr[(i + 2) % length][0] - arr[(i + 1) % length][0]; 
    let dy1 = arr[(i + 1) % length][1] - arr[i][1]; 
    let dy2 = arr[(i + 2) % length][1] - arr[(i + 1) % length][1]; 
    curr = dx1 * dy2 - dx2 * dy1; 
    if (curr != 0) { 
      if ((curr > 0 && pre < 0) || (curr < 0 && pre > 0)) return false; 
      else pre = curr; 
    } 
  } 
  return true; 
}; 
console.log(isConvex(arr));

ผลลัพธ์

true