ผู้ใช้:DeNoctua/ทดลองเขียน

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

กรณี 2 มิติ[แก้]

(หรือที่รู้จักกันในชื่อ เขตแดนจาร์วิส เพื่อเป็นเกียรติแก่ R.A. Jarvis ผู้เผยแพร่ขั้นตอนวิธีนี้ในปี พ.ศ. 2516) โดยขั้นตอนวิธีนี้มี ประสิทธิภาพเชิงเวลาเป็น O(nh) เมื่อ n คือจำนวนของจุด และ h คือจำนวนของจุดบนเปลือกนูน โดยในการนำไปใช้จริงนั้น ขั้นตอนวิธีนี้จะมีประสิทธิภาพเหนือกว่าขั้นตอนวิธีอื่นๆเมื่อ h มีขนาดเล็กเมื่อเทียบกับ n เท่านั้น

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

เพื่อความง่ายในการศึกษาขั้นตอนวิธี จะทำการศึกษากรณีที่ไม่มีจุดสามจุดใดๆอยู่บนเส้นตรงเดียวกัน โดยสามารถปรับเปลี่ยนเพื่อใช้ในกรณีที่จุดสามจุดอยู่บนเส้นตรงเดียวกันได้ง่าย โดยอาจสามารถเลือกให้แสดงผลเฉพาะจุดสุดขีด หรือจุดทุกจุดบนเปลือกนูน นอกจากนี้ยังต้องคำนึงถึงกรณีที่มีเพียงหนึ่งหรือสองจุด และความแม่นยำเชิงคณิตศาสตร์ทั้งที่คอมพิวเตอร์สามารถคำนวณได้และข้อมูลเข้า

ขั้นตอนวิธีแบบห่อข้อขวัญเริ่มต้นโดยให้ i = 0 และจุด p0 ซึ่งทราบอยู่แล้วว่าอยู่บนเปลือกนูน เช่น จุดซ้ายสุด จากนั้นจึงเลือกจุด pi+1 ซึ่งเมื่อพิจารณาจุดนี้แล้ว จุดที่เหลือจะอยู่ทางขวามือของจุดนี้ทั้งหมด ซึ่งจุดนี้สามารถหาได้ภายในเวลา O(n) โดยใช้วิธีการเปรียบเทียบมุมระหว่าง pi กับทุกจุดที่เหลือ ทำจนได้ ph = p0 ฉะนั้น จึงสรุปได้ว่า เราสามารถหาเปลือกนูนได้หลังจากทำเช่นนี้ h ครั้ง

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

 jarvis(S)
  pointOnHull = leftmost point in S
  i = 0
  repeat
     P[i] = pointOnHull
     endpoint = S[0]         // ตั้งค่าเริ่มต้นสำหรับจุดบนเปลือกนูนต่อไป
     for j from 1 to |S|-1
        if (endpoint == pointOnHull) or (S[j] is on left of line from P[i] to endpoint)
           endpoint = S[j]   // พบจุดที่อยู่ทางซ้ายมากกว่า เปลี่ยนค่าใหม่
     i = i+1
     pointOnHull = endpoint
  until endpoint == P[0]      // ทำซ้ำจนกว่าจะครบรอบ

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

จะเห็นได้ว่า วงวนด้านในจะตรวจสอบสำหรับทุกๆจุดในเซต S ส่วนวงรอบภายนอกจะทำซ้ำทุกจุดบนเปลือกนูน ฉะนั้นสรุปได้ว่า เวลาที่ใช้ในการหาเปลือกนูนด้วยขั้นตอนวิธีแบบห่อของขวัญ จะใช้เวลาเป็น nh ซึ่งขึ้นกับข้อมูลขาออก จึงกล่าวได้ว่า ขั้นตอนวิธีแบบห่อของขวัญนี้เป็นแบบขึ้นกับข้อมูลออก

แหล่งข้อมูลอื่น[แก้]