ผลต่างระหว่างรุ่นของ "เกรแฮมสแกน"
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
ล →ดูเพิ่ม: แก้คำผิดเล็กน้อย |
|||
บรรทัด 3:
==ขั้นตอนวิธี==
[[ไฟล์:Graham Scan.svg|frame|right|จากภาพ PAB และ ABC เป็นการ "เลี้ยวซ้าย" แต่ BCD เป็นการ "เลี้ยวขวา" ขั้นตอนวิธีจึงไม่รวมจุด C เข้าไปในเซตคำตอบ และไปเลือกจุด D ซึ่งเป็นจุดเลี้ยวซ้ายถัดไปแทน]]
ขั้นตอนวิธีเริ่มจาก[[จุด_(เรขาคณิต)|จุด]]ที่มี
ถัดมา เรียงลำดับจุดที่เหลือตามมุมที่จุด ''P'' และจุดนั้นๆกระทำกับแกน x โดยเรียงจากน้อยไปหามาก การเรียงลำดับสามารถใช้ขั้นตอนวิธีแบบใดก็ได้ เช่น การเรียงลำดับโดยใช้[[ฮีป]] (ใช้เวลา O(''n'' log ''n'')) เพื่อความรวดเร็วในการคำนวณ ไม่จำเป็นต้องหาค่าองศาของมุมระหว่างแกน x และเส้นจากจุด ''P'' ไปยังจุดหนึ่งๆ เพื่อนำมาเรียงลำดับ สามารถใช้ค่า [[โคไซน์]] ของมุม ซึ่งในปัญหา convex hull จะเป็นฟังก์ชันลดทางเดียว (monotonically decresing funcion) มีค่าระหว่าง 0 ถึง 180 องศา ซึ่งสามารถคำนวณได้จาก[[คณิตศาสตร์]]อย่างง่าย
บรรทัด 9:
จากนั้น พิจารณาแต่ละจุดตามลำดับที่เรียงไว้ โดยพิจารณาจากจุดนั้นๆร่วมกับก่อนหน้าสองจุด ว่าการเลือกจุดถัดไปนั้นเป็นการ "เลี้ยวขวา" หรือ "เลี้ยวซ้าย" หากเป็นการ "เลี้ยวขวา" หมายความว่าจุดตรงกลางไม่เป็นส่วนหนึ่งของผนัง convex hull และจะไม่นำมาพิจารณาอีก พิจารณาในขั้นตอนนี้ไปเรื่อยๆ จนกระทั่งพบการ "เลี้ยวซ้าย" ซึ่งหมายความว่า จุดตรงกลางคือส่วนหนึ่งของผนัง convex hull จึงพิจารณาจุดถัดไป (หากระหว่างการพิจารณาพบเส้นทางตรงซึ่งไม่มีการเลี้ยว อาจรวม หรือ ไม่รวม จุดนั้นในเซตคำตอบ ขึ้นกับปัญหา เนื่องจากการนำไปใช้บางสถานการณ์จำเป็นต้องรวมทุกจุดบนผนัง convex hull ลงไปในคำตอบ)
เช่นเดียวกับการเรียงลำดับจุดตามมุมในขั้นตอนที่สอง การพิจารณาจุดสามจุดว่าเป็นการ "เลี้ยวขวา" หรือ "เลี้ยวซ้าย" ไม่จำเป็นต้อง
สุดท้าย กระบวนการจะวนกลับมายังจุดเริ่มต้น ทำให้เสร็จสิ้นขั้นตอนวิธี ได้ผลลัพธ์เป็นจุดที่อยู่บนผนัง convex hull เรียงตามลำดับทวนเข็มนาฬิกาจากจุด ''P''
|