ขั้นตอนวิธี ของ เกรแฮมสแกน

จากภาพ 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 องศา ซึ่งสามารถคำนวณได้จากคณิตศาสตร์อย่างง่าย

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

เช่นเดียวกับการเรียงลำดับจุดตามมุมในขั้นตอนที่สอง การพิจารณาจุดสามจุดว่าเป็นการ "เลี้ยวขวา" หรือ "เลี้ยวซ้าย" ไม่จำเป็นต้องคำนวณองศาของระหว่างเส้นสองเส้น แต่สามารถคำนวณจากคณิตศาสตร์อย่างง่าย สำหรับจุดสามจุด ( x 1 , y 1 ) {\displaystyle (x_{1},y_{1})} , ( x 2 , y 2 ) {\displaystyle (x_{2},y_{2})} และ ( x 3 , y 3 ) {\displaystyle (x_{3},y_{3})} นั้น สามารถคำนวณหาทิศทางของผลลัพธ์จากการครอสส์เวกเตอร์ ( ( x 1 , y 1 ) , ( x 2 , y 2 ) ) {\displaystyle ((x_{1},y_{1}),(x_{2},y_{2}))} และ ( ( x 1 , y 1 ) , ( x 3 , y 3 ) ) {\displaystyle ((x_{1},y_{1}),(x_{3},y_{3}))} ซึ่งคำนวณได้จากเครื่องหมายของนิพจน์ ( x 2 − x 1 ) ( y 3 − y 1 ) − ( y 2 − y 1 ) ( x 3 − x 1 ) {\displaystyle (x_{2}-x_{1})(y_{3}-y_{1})-(y_{2}-y_{1})(x_{3}-x_{1})} หากผลลัพธ์เป็น 0 แสดงว่าจุดสามจุดเรียงกันเป็นเส้นตรง หากผลลัพธ์เป็นบวก แสดงจุดทั้งสามทำให้เกิดการ "เลี้ยวซ้าย" และหากผลลัพธ์เป็นลบ แสดงว่าเกิดการ "เลี้ยวขวา"

สุดท้าย กระบวนการจะวนกลับมายังจุดเริ่มต้น ทำให้เสร็จสิ้นขั้นตอนวิธี ได้ผลลัพธ์เป็นจุดที่อยู่บนผนัง convex hull เรียงตามลำดับทวนเข็มนาฬิกาจากจุด P

ใกล้เคียง