ผลต่างระหว่างรุ่นของ "เกรแฮมสแกน"
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
ไม่มีความย่อการแก้ไข |
|||
บรรทัด 19:
==รหัสเทียม==
อันดับแรก ฟังก์ชั่นคำนวนการ "เลี้ยวขวา" และ "เลี้ยวซ้าย"
''จุดสามจุดก่อให้เกิดการ "เลี้ยวซ้าย" เมื่อ ccw > 0,
'''ฟังก์ชั่น''' ccw(p1, p2, p3):
▲ '''return''' (p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x)
'''ให้''' N
'''ให้''' points[N+1] =
'''สลับ''' points[1]
'''เรียง''' points
# ''ต้องการให้ points[0] เป็นจุดสุดท้ายซึ่งจะจบการทำงานในวงวน ดังนั้น''
'''
# ''ค่า M
'''
'''for''' i = 3 '''to''' N:
# ''
'''while''' '''ccw'''(points[M-1], points[M], points[i]) <= 0:
# ''หากจุดทั้งสามเรียงตัวกันเป็นเส้นตรง จะไม่สนใจจุดนั้น''
'''if''' M
'''
i += 1
'''else'''
M -= 1
# ''เพิ่มค่า M ให้ถูกต้อง และสลับจุด points[i] มายังส่วนคำตอบ''
M += 1
'''
รหัสเทียมนี้ปรับปรุงจากตำรา ''Algorithms, 4th edition'' โดย Sedgewick and Wayne
| |||