ผลต่างระหว่างรุ่นของ "เกรแฮมสแกน"

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