รหัสเทียม ของ เกรแฮมสแกน

อันดับแรก กำหนดฟังก์ชันคำนวณการ "เลี้ยวขวา" และ "เลี้ยวซ้าย" โดย จุดสามจุดก่อให้เกิดการ "เลี้ยวซ้าย" เมื่อ 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)

ให้คำตอบอยู่ในตาราง points

ให้ N = จำนวนจุดทั้งหมดให้ points[N+1] = ตารางของจุดทั้งหมดสลับ points[1] กับจุดที่มีตำแหน่งบนแกน y ต่าที่สุดเรียง points จากมุมที่จุดต่างๆกระทำกับจุด points[1] จากน้อยไปหามาก# ต้องการให้ points[0] เป็นจุดสุดท้ายซึ่งจะจบการทำงานในวงวน ดังนั้นให้ points[0] = points[N]# ค่า M จะแสดงถึงจำนวนจุดบนผนัง convex hullให้ M = 2for 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[2]

ใกล้เคียง