เกรแฮมสแกน

เกรแฮมสแกน (อังกฤษ:Graham Scan) เป็นขั้นตอนวิธีสำหรับคำนวณหา เปลือกนูน ของเซตจุดบนระนาบ โดยมีความซับซ้อนด้านเวลา (time complexity) เป็น O("n" log "n") ชื่อของชั้นตอนวิธีมาจากผู้เผยเพร่ขั้นตอนวิธีต้นฉบับในปี ค.ศ. 1972
ขั้นตอนวิธี.
ขั้นตอนวิธีเริ่มจากจุดที่มีพิกัด y ต่ำสุด หากพบจุดที่มีคู่อันดับ y ต่ำสุดมากกว่าหนึ่งจุด ให้เลือกจุดที่มีคู่อันดับ x ต่ำสุดในกลุ่มนั้น เรียกจุดนี้ว่าจุด "P" ขั้นตอนนี้ใช้เวลา O("n") โดยที่ "n" คือจำนวนของจุดทั้งหมด
ถัดมา เรียงลำดับจุดที่เหลือตามมุมที่จุด "P" และจุดนั้นๆกระทำกับแกน x โดยเรียงจากน้อยไปหามาก การเรียงลำดับสามารถใช้ขั้นตอนวิธีแบบใดก็ได้ เช่น การเรียงลำดับโดยใช้ฮีป (ใช้เวลา O("n" log "n")) เพื่อความรวดเร็วในการคำนวณ ไม่จำเป็นต้องหาค่าองศาของมุมระหว่างแกน x และเส้นจากจุด "P" ไปยังจุดหนึ่งๆ เพื่อนำมาเรียงลำดับ สามารถใช้ค่า โคไซน์ ของมุม ซึ่งในปัญหา convex hull จะเป็นฟังก์ชันลดทางเดียว (monotonically decresing funcion) มีค่าระหว่าง 0 ถึง 180 องศา ซึ่งสามารถคำนวณได้จากคณิตศาสตร์อย่างง่าย
จากนั้น พิจารณาแต่ละจุดตามลำดับที่เรียงไว้ โดยพิจารณาจากจุดนั้นๆร่วมกับก่อนหน้าสองจุด ว่าการเลือกจุดถัดไปนั้นเป็นการ "เลี้ยวขวา" หรือ "เลี้ยวซ้าย" หากเป็นการ "เลี้ยวขวา" หมายความว่าจุดตรงกลางไม่เป็นส่วนหนึ่งของผนัง 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"
ความซับซ้อนด้านเวลา.
การเรียงลำดับจุดทั้งหมดมีความซับซ้อนด้านเวลาเป็น O("n" log "n") ส่วนการทำงานในวงวนตรวจสอบว่าการเลือกจุดถัดไปเป็นการ "เลี้ยวขวา" หรือ "เลี้ยวซ้าย" ใช้เวลาเพียง O("n") เนื่องจากจุดใดๆจะนำมาตรวจสอบเพียงสองครั้ง หากตรวจสอบแล้วพบว่าเป็นจุด <math>(x_2,y_2)</math> ในการ "เลี้ยวซ้าย" ขั้นตอนวิธีจะดำเนินต่อไปยังจุด <math>(x_3,y_3)</math> และถ้าหากพบว่าเป็นจุด <math>(x_2,y_2)</math> ในการเลี้ยวขวา จุดนั้นก็จะไม่ถูกนำมาพิจารณาอีก ดังนั้น เกรแฮมสแกน มีความซับซ้อนทางเวลาเป็น O("n" log "n") ตามการเรียงลำดับจุด ซึ่งใช้เวลามากที่สุดในขั้นตอนวิธี
รหัสเทียม.
อันดับแรก กำหนดฟังก์ชันคำนวณการ "เลี้ยวขวา" และ "เลี้ยวซ้าย" โดย จุดสามจุดก่อให้เกิดการ "เลี้ยวซ้าย" เมื่อ ccw > 0, "เลี้ยวขวา" เมื่อ ccw < 0 และ เรียงตัวเป็นเส้นตรงเมื่อ ccw = 0 เนื่องจาก ccw คือพื้นที่สามเหลี่ยมจากการวางตัวของจุด p1, p2 และ p3 โดยคิดเครื่องหมายบวก-ลบ ด้วย
 function ccw(p1, p2, p3):
 return (p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x)
ให้คำตอบอยู่ในตาราง <code> points </code>
 ให้ N = จำนวนจุดทั้งหมด
 ให้ points[N+1] = ตารางของจุดทั้งหมด
 สลับ points[1] กับจุดที่มีตำแหน่งบนแกน y ต่าที่สุด
 เรียง points จากมุมที่จุดต่างๆกระทำกับจุด points[1] จากน้อยไปหามาก
 # "ต้องการให้ points[0] เป็นจุดสุดท้ายซึ่งจะจบการทำงานในวงวน ดังนั้น"
 ให้ points[0] = points[N]
 # "ค่า M จะแสดงถึงจำนวนจุดบนผนัง convex hull"
 ให้ M = 2
 for i = 3 to N:
 # "หาจุดบนผนัง convex hull จุดถัดไป"
 while ccw(points[M-1], points[M], points[i]) <= 0:
 # "หากจุดทั้งสามเรียงตัวกันเป็นเส้นตรง จะไม่สนใจจุดนั้น"
 if M == 2:
 สลับ points[M] กับ points[i]
 i += 1
 else
 M -= 1
 # "เพิ่มค่า M ให้ถูกต้อง และสลับจุด points[i] มายังส่วนคำตอบ"
 M += 1
 สลับ points[M] กับ points[i]
รหัสเทียมนี้ปรับปรุงจากตำรา "Algorithms, 4th edition" โดย Sedgewick and Wayne