เมนูนำทาง
เกรแฮมสแกน รหัสเทียมอันดับแรก กำหนดฟังก์ชันคำนวณการ "เลี้ยวขวา" และ "เลี้ยวซ้าย" โดย จุดสามจุดก่อให้เกิดการ "เลี้ยวซ้าย" เมื่อ 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]
เมนูนำทาง
เกรแฮมสแกน รหัสเทียมใกล้เคียง
แหล่งที่มา
WikiPedia: เกรแฮมสแกน http://www.sciencedirect.com/science?_ob=IssueURL&... http://www.personal.kent.edu/~rmuhamma/Compgeometr... http://people.csail.mit.edu/thies/6.046-web/graham... http://www.cs.princeton.edu/courses/archive/fall08... http://www.partow.net/projects/fastgeo/index.html http://tixxit.net/2010/03/graham-scan