เกรแฮมสแกน

เกรแฮมสแกน (อังกฤษ:Graham Scan) เป็นขั้นตอนวิธีสำหรับคำนวณหา เปลือกนูน ของเซตจุดบนระนาบ โดยมีความซับซ้อนด้านเวลา (time complexity) เป็น O(n log n) ชื่อของชั้นตอนวิธีมาจากผู้เผยเพร่ขั้นตอนวิธีต้นฉบับในปี ค.ศ. 1972Graham, R.L. (1972). An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set. Information Processing Letters 1, 132-133

ขั้นตอนวิธี
ขั้นตอนวิธีเริ่มจากจุดที่มีพิกัด 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 ลงไปในคำตอบ)

เช่นเดียวกับการเรียงลำดับจุดตามมุมในขั้นตอนที่สอง การพิจารณาจุดสามจุดว่าเป็นการ "เลี้ยวขวา" หรือ "เลี้ยวซ้าย" ไม่จำเป็นต้องคำนวณองศาของระหว่างเส้นสองเส้น แต่สามารถคำนวณจากคณิตศาสตร์อย่างง่าย สำหรับจุดสามจุด ,  และ  นั้น สามารถคำนวณหาทิศทางของผลลัพธ์จากการครอสส์เวกเตอร์  และ  ซึ่งคำนวณได้จากเครื่องหมายของนิพจน์  หากผลลัพธ์เป็น 0 แสดงว่าจุดสามจุดเรียงกันเป็นเส้นตรง หากผลลัพธ์เป็นบวก แสดงจุดทั้งสามทำให้เกิดการ "เลี้ยวซ้าย" และหากผลลัพธ์เป็นลบ แสดงว่าเกิดการ "เลี้ยวขวา"

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

ความซับซ้อนด้านเวลา
การเรียงลำดับจุดทั้งหมดมีความซับซ้อนด้านเวลาเป็น O(n log n) ส่วนการทำงานในวงวนตรวจสอบว่าการเลือกจุดถัดไปเป็นการ "เลี้ยวขวา" หรือ "เลี้ยวซ้าย" ใช้เวลาเพียง O(n) เนื่องจากจุดใดๆจะนำมาตรวจสอบเพียงสองครั้ง หากตรวจสอบแล้วพบว่าเป็นจุด  ในการ "เลี้ยวซ้าย" ขั้นตอนวิธีจะดำเนินต่อไปยังจุด  และถ้าหากพบว่าเป็นจุด  ในการเลี้ยวขวา จุดนั้นก็จะไม่ถูกนำมาพิจารณาอีก ดังนั้น เกรแฮมสแกน มีความซับซ้อนทางเวลาเป็น 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)

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

 ให้ 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

ดูเพิ่ม
 เกรแฮมสแกนในภาษา C++ และ Object Pascal 
 เกรแฮมสแกนในภาษา Python 
 ตัวอย่างการทำงานของเกรแฮมสแกน
 เหตุใดเกรแฮมสแกนต้องเรียงลำดับปมก่อนค้นหา

อ้างอิง


 Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford (2001) [1990]. "33.3: Finding the convex hull". Introduction to Algorithms (2nd ed.). MIT Press และ McGraw-Hill. หน้า 949–955. ISBN 0-262-03293-7.

หมวดหมู่:ขั้นตอนวิธี
หมวดหมู่:ขั้นตอนวิธีแก้ปัญหาเปลือกนูน
หมวดหมู่:เรขาคณิตเชิงคำนวณ