ขั้นตอนวิธีแบบห่อของขวัญ

ขั้นตอนวิธีแบบห่อของขวัญ (อังกฤษ: Gift Wrapping Algorithm) คือวิธีในทาง เรขาคณิตเชิงคำนวณ ที่ใช้ในการคำนวณหา คอนเวกซ์ฮัลล์

ประวัติ แก้

ขั้นตอนวิธีแบบห่อของขวัญมีชื่อเรียกอีกอย่างหนึ่งว่า การเดินแถวของจาร์วิส (อังกฤษ: Jarvis' March) เพื่อเป็นเกียรติแก่ อาร์.เอ. จาร์วิส ผู้นำขั้นตอนวิธีนี้ออกเผยแพร่ในปี พ.ศ. 2516 (หลังจาก โรนัลด์ เกรแฮม นำเสนอเกรแฮมสแกนหนึ่งปี)

ขั้นตอนวิธี แก้

การใช้ขั้นตอนวิธีการห่อของขวัญในการหาคอนเวกซ์ฮัลล์

เริ่มจากให้ i = 0 และให้ p0 คือจุดสุดขีดจุดหนึ่ง ซึ่งทราบแน่นอนว่าอยู่บนคอนเวกซ์ฮัลล์ เช่น จุดบนสุด จากนั้น เลือกจุด pi+1 โดย pi+1 คือจุดที่ให้มุมกว้างที่สุดเทียบกับ Pi (อาจเป็นทิศทวนเข็มนาฬิกาหรือตามเข็มนาฬิกาก็ได้) ทำซ้ำเช่นนี้ไปเรื่อยๆ จนกว่าจะได้ ph = p0 คือวนกลับมาจนครบจุดเริ่มต้นนั่นเอง ([1])

รหัสเทียม แก้

jarvis(S)                      // รับ S ที่เป็นเซทของจุด
  pointOnHull = จุดสุดขีดจุดหนึ่ง    // ตั้งค่า p0 ด้วยจุดสุดขีดจุดหนึ่ง
  i = 0                       // เริ่ม i = 0
  repeat
     P[i] = pointOnHull       // เพิ่มค่า pi ลงไปในอาเรย์ของคำตอบ P ช่องที่ i
     endpoint = S[0]          // ตั้งค่าเริ่มต้นสำหรับการหาจุดต่อไปบนคอนเวกซ์ฮัลล์
     for j from 1 to |S|-1    // ตรวจสอบทุกจุด
        if (pointOnHull.angle(S[j]) > pointOnHull.angle(endpoint))
           endpoint = S[j]    // ถ้าหากมุมของจุดใหม่กว้างกว่าเทียบกับจุดเดิมที่เลือกไปในรอบก่อน ให้เปลี่ยนจุดที่เลือกใหม่
     i = i+1
     pointOnHull = endpoint   // ตั้งค่าจุด pi+1 ให้เป็นจุดหลักสำหรับรอบหน้า
until endpoint == P[0]        // ทำซ้ำจนกว่าจะครบรอบ

ประสิทธิภาพ แก้

เนื่องจากเวลาในการหามุมสำหรับแต่ละจุดเป็นค่าคงที่ (O(1)) และการเปรียบเทียบมุมสำหรับทุกคู่จุดจะใช้เวลา O(n) สรุปว่าเราสามารถหาจุดๆหนึ่งบนคอนเวกซ์ฮัลล์ได้ภายในเวลา O(n) และหากมีจุดบนคอนเวกซ์ฮัลล์เป็นจำนวน h จุดแล้ว สรุปได้ว่าการเดินแถวของจาร์วิสจะสามารถหาจุดทุกๆจุดบนคอนเวกซ์ฮัลล์ได้ภายในเวลา O(nh)

การนำไปใช้ แก้

โดยปกติแล้ว การเดินแถวของจาร์วิสนั้นจะสามารถทำงานได้เร็วกว่าเกรแฮมสแกน โดยกรณีที่เลวที่สุดคือกรณีที่ทุกจุดอยู่บนคอนเวกซ์ฮัลล์ เช่น รูปวงกลม

อ้างอิง แก้

Jarvis, R. A. (1973). "On the identification of the convex hull of a finite set of points in the plane". Information Processing Letters. 2: 18–21. doi:10.1016/0020-0190(73)90020-3.