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

'''เกรแฮมสแกน''' ([[ภาษาอังกฤษ|อังกฤษ]]:Graham Scan) เป็น[[ขั้นตอนวิธี]]สำหรับคำนวณหา [[convex hallhull]] ของ[[เซท]]จุดบนระนาบ โดยมี[[ความซับซ้อนด้านเวลา]] (time complexity) เป็น [[สัญกรณ์โอใหญ่|O]](''n'' log ''n'') ชื่อของชั้นตอนวิธีมาจากผู้เผยเพร่ขั้นตอนวิธีต้นฉบับในปี ค.ศ.1972

ถัดมา เรียงลำดับจุดที่เหลือตามมุมที่จุด ''P'' และจุดนั้นๆกระทำกับแกน x โดยเรียงจากน้อยไปหามาก การเรียงลำดับสามารถใช้ขั้นตอนวิธีแบบใดก็ได้ เช่น การเรียงลำดับโดยใช้[[ฮีป]] (ใช้เวลา O(''n'' log ''n'')) เพื่อความรวดเร็วในการคำนวณ ไม่จำเป็นต้องหาค่าองศาของมุมระหว่างแกน x และเส้นจากจุด ''P'' ไปยังจุดหนึ่งๆ เพื่อนำมาเรียงลำดับ สามารถใช้ค่า [[โคไซน์]] ของมุม ซึ่งในปัญหา convex hallhull จะเป็นฟังก์ชันลดทางเดียว (monotonically decresing funcion) มีค่าระหว่าง 0 ถึง 180 องศา ซึ่งสามารถคำนวณได้จาก[[คณิตศาสตร์]]อย่างง่าย

จากนั้น พิจารณาแต่ละจุดตามลำดับที่เรียงไว้ โดยพิจารณาจากจุดนั้นๆร่วมกับก่อนหน้าสองจุด ว่าการเลือกจุดถัดไปนั้นเป็นการ "เลี้ยวขวา" หรือ "เลี้ยวซ้าย" หากเป็นการ "เลี้ยวขวา" หมายความว่าจุดก่อนหน้าตรงกลางไม่เป็นส่วนหนึ่งของผนัง convex hallhull และจะไม่นำมาพิจารณาอีก การพิจารณาในขั้นตอนนี้ดำเนินต่อไปเรื่อยๆ จนกระทั่งพบการ "เลี้ยวซ้าย" ซึ่งหมายความว่า จุดตรงกลางคือส่วนหนึ่งของผนัง convex hull จึงพิจารณาจุดถัดไป (หากระหว่างการพิจารณาพบเส้นทางตรงซึ่งไม่มีการเลี้ยว อาจรวม หรือ ไม่รวม จุดนั้นในเซตคำตอบ ขึ้นกับปัญหา เนื่องจากการนำไปใช้บางสถานการณ์จำเป็นต้องรวมทุกจุดบนผนัง convex hallhull ลงไปในคำตอบ)

เช่นเดียวกับก่อนหน้าการเรียงลำดับจุดตามมุมในขั้นตอนที่สอง การพิจารณาจุดสามจุดว่าเป็นการ "เลี้ยวขวา" หรือ "เลี้ยวซ้าย" ไม่จำเป็นต้องคำนาณองศาของระหว่างเส้นสองเส้น แต่สามารถคำนาณจากคณิตศาสตร์อย่างง่าย สำหรับจุดสามจุด <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 hallhull เรียงตามลำดับทวนเข็มนาฬิกาจากจุด ''P''