ผลต่างระหว่างรุ่นของ "ขั้นตอนวิธีแบบห่อของขวัญ"
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
Nullzerobot (คุย | ส่วนร่วม) ล เก็บกวาด |
Nullzerobot (คุย | ส่วนร่วม) ล เก็บกวาด |
||
บรรทัด 1:
'''ขั้นตอนวิธีแบบห่อของขวัญ'''
== ประวัติ ==
บรรทัด 7:
[[ไฟล์:Jarvis march convex hull algorithm diagram.svg|thumb|280px|right|การใช้ขั้นตอนวิธีการห่อของขวัญในการหาคอนเวกซ์ฮัลล์]]
เริ่มจากให้ i = 0 และให้ p0 คือจุดสุดขีดจุดหนึ่ง ซึ่งทราบแน่นอนว่าอยู่บนคอนเวกซ์ฮัลล์ เช่น จุดบนสุด จากนั้น เลือกจุด pi+1 โดย pi+1 คือจุดที่ให้มุมกว้างที่สุดเทียบกับ Pi (อาจเป็นทิศทวนเข็มนาฬิกาหรือตามเข็มนาฬิกาก็ได้) ทำซ้ำเช่นนี้ไปเรื่อยๆ จนกว่าจะได้ ph = p0 คือวนกลับมาจนครบจุดเริ่มต้นนั่นเอง ([http://www.cs.princeton.edu/courses/archive/spr10/cos226/demo/ah/JarvisMarch.html
== รหัสเทียม ==
บรรทัด 33:
{{เริ่มอ้างอิง}}
* {{cite journal
| author = Jarvis, R. A.
| title = On the identification of the convex hull of a finite set of points in the plane
| |||