ตัวอย่าง Convex Hull ในโครงสร้างข้อมูล (Jarvis March Algorithm)

Convex Hull คืออะไร?

มีชุดจุด (Points) ต้องสร้างรูปหลายเหลี่ยม (Polygon) โดยใช้จุดน้อยที่สุด ที่จะ ครอบคลุมจุดทั้งหมด ส่วนนี้ใช้ Jarvis March Algorithm หา Convex Hull

Jarvis March Algorithm

ใช้หาจุดมุม (Corner Points) ของ Convex Hull จากชุดข้อมูล

1. เริ่มจาก จุดซ้ายสุด (Leftmost Point)
2. เก็บจุดใน Convex Hull โดยหมุน ทวนเข็มนาฬิกา (Anti-clockwise)
3. จากจุดปัจจุบัน เลือกจุดถัดไปโดยตรวจสอบ Orientation (ทิศทาง) จุดที่มุมมากที่สุดจะถูกเลือก
4. เมื่อจุดถัดไปคือจุดเริ่มต้น หยุดอัลกอริทึม

Input และ Output

Input: ชุดจุด {(-7,8), (-4,6), (2,6), (6,4), (8,6), (7,-2), (4,-6), (8,-7), (0,0), (3,-2), (6,-10), (0,-6), (-9,-5), (-8,-2), (-8,0), (-10,3), (-2,2), (-10,4)}

Output: จุดขอบของ Convex Hull –

(-9, -5) (6, -10) (8, -7) (8, 6) (-7, 8) (-10, 4) (-10, 3)

อัลกอริทึม (Pseudocode)

findConvexHull(points, n)
  start := points[0]
  for each point i: if points[i].x < start.x then start := points[i]  // จุดซ้ายสุด
  current := start
  add start to result
  define colPts set for collinear points
  while true:
    next := points[0]
    for all points i except 0:
      if points[i] == current: continue
      val := cross product of current, next, points[i]
      if val > 0: next := points[i]; clear colPts
      else if val == 0:
        if next closer to current than points[i]: add next to colPts; next := points[i]
        else: add points[i] to colPts
    add all colPts to result
    if next == start: break
    insert next to result
    current := next
  return result

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

// โครงสร้าง Point, Cross Product, Distance, findConvexHull function
// ดูโค้ดเต็มในต้นฉบับ

Output

Boundary points of convex hull are:
(-9, -5) (6, -10) (8, -7) (8, 6) (-7, 8) (-10, 4) (-10, 3)