อัลกอริทึม Graham Scan (Convex Hull)

บทนำ

Convex Hull คือพื้นที่ปิดขนาดเล็กที่สุดที่สามารถครอบคลุมจุดข้อมูลที่กำหนดทั้งหมดได้

อัลกอริทึม Graham's Scan จะหาจุดมุมของ Convex Hull ในอัลกอริทึมนี้ ขั้นแรกเลือกจุดที่ต่ำที่สุด จุดนั้นคือจุดเริ่มต้นของ Convex Hull จุดยอดที่เหลือ n-1 จุด ถูกเรียงลำดับตามทิศทางทวนเข็มนาฬิกาจากจุดเริ่มต้น ถ้ามีจุดสองจุดขึ้นไปที่สร้างมุมเท่ากัน ให้ลบทิ้งทั้งหมดยกเว้นจุดที่ไกลที่สุดจากจุดเริ่มต้น

จากจุดที่เหลือ ให้ push เข้า Stack แล้ว pop ออกทีละอัน เมื่อทิศทาง (Orientation) ของจุดบนสุดของ Stack, จุดที่สองจากบนสุด และจุดที่เลือกใหม่ points[i] ไม่ใช่ทิศทางทวนเข็มนาฬิกา หลังจากตรวจสอบแล้ว ให้ insert points[i] เข้า Stack

อินพุตและเอาต์พุต

Input: ชุดจุด: {(-7,8), (-4,6), (2,6), (6,4), (8,6), (7,-2), (4,-6), (8,-7),(0,0), (3,-2),(6,-10),(0,-6),(-9,-5),(-8,-2),(-8,0),(-10,3),(-2,2),(-10,4)}
Output: จุดขอบของ Convex Hull คือ: (-9, -5) (-10, 3) (-10, 4) (-7, 8) (8, 6) (8, -7) (6, -10)

อัลกอริทึม

findConvexHull(points, n)
Input: ชุดจุด, จำนวนจุด
Output: จุดขอบของ Convex Hull

Begin
    minY := points[0].y
    min := 0
    for i := 1 to n-1 do
        y := points[i].y
        if y < minY or minY = y and points[i].x < points[min].x, then
            minY := points[i].y
            min := i
    done
    swap points[0] and points[min]
    p0 := points[0]
    เรียง points จาก points[1] ถึง end
    arrSize := 1
    for i := 1 to n, do
        when i < n-1 and (p0, points[i], points[i+1]) are collinear, do
            i := i + 1
        done
        points[arrSize] := points[i]
        arrSize := arrSize + 1
    done
    if arrSize < 3, then
        return cHullPoints
    push points[0] into stack
    push points[1] into stack
    push points[2] into stack
    for i := 3 to arrSize, do
        while top of stack, item below the top and points[i] is not in
            anticlockwise rotation, do
            delete top element from stack
        done
        push points[i] into stack
    done
    while stack is not empty, do
        item stack top element into cHullPoints
        pop from stack
    done
End

ตัวอย่างโค้ด (C++)

#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>
using namespace std;

struct point {
    // กำหนดจุดสำหรับระนาบ 2D
    int x, y;
};

point p0;  // ใช้สำหรับเปรียบเทียบอีกสองจุด

point secondTop(stack& stk) {
    point tempPoint = stk.top(); stk.pop();
    point res = stk.top();  // ได้อิลิเมนต์ลำดับสองจากบนสุด
    stk.push(tempPoint);  // push อันบนสุดเดิมกลับไป
    return res;
}

int squaredDist(point p1, point p2) {
    return ((p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y));
}

int direction(point a, point b, point c) {
    int val = (b.y-a.y)*(c.x-b.x) - (b.x-a.x)*(c.y-b.y);
    if (val == 0)
        return 0;  // collinear
    else if (val < 0)
        return 2;  // anti-clockwise direction
    return 1;  // clockwise direction
}

int comp(const void *point1, const void* point2) {
    point *p1 = (point*)point1;
    point *p2 = (point*)point2;
    int dir = direction(p0, *p1, *p2);
    if (dir == 0)
        return (squaredDist(p0, *p2) >= squaredDist(p0, *p1)) ? -1 : 1;
    return (dir == 2) ? -1 : 1;
}

vector findConvexHull(point points[], int n) {
    vector convexHullPoints;
    int minY = points[0].y, min = 0;
    for (int i = 1; i < n; i++) {
        int y = points[i].y;
        // หาจุดล่างสุดหรือซ้ายสุด
        if ((y < minY) || (minY == y && points[i].x < points[min].x)) {
            minY = points[i].y;
            min = i;
        }
    }
    swap(points[0], points[min]);  // swap จุด min ไปที่ตำแหน่ง 0
    p0 = points[0];
    qsort(&points[1], n-1, sizeof(point), comp);  // เรียงจุดจากตำแหน่ง 1 ถึง end
    
    int arrSize = 1;  // ใช้ locate items ใน modified array
    for (int i = 1; i < n; i++) {
        // เมื่อมุมของ ith และ (i+1)th เหมือนกัน ให้ลบจุด
        while (i < n-1 && direction(p0, points[i], points[i+1]) == 0)
            i++;
        points[arrSize] = points[i];
        arrSize++;
    }
    if (arrSize < 3)
        return convexHullPoints;  // ต้องมีจุดอย่างน้อย 3 จุด, return empty list
    
    // สร้าง stack และเพิ่มจุดแรกสามจุดใน stack
    stack stk;
    stk.push(points[0]); stk.push(points[1]); stk.push(points[2]);
    
    for (int i = 3; i < arrSize; i++) {
        // สำหรับจุดยอดที่เหลือ
        while (direction(secondTop(stk), stk.top(), points[i]) != 2)
            stk.pop();  // เมื่อ top, second top และ ith point ไม่ทำ left turn ให้ลบจุด
        stk.push(points[i]);
    }
    
    while (!stk.empty()) {
        convexHullPoints.push_back(stk.top());  // เพิ่มจุดจาก stack
        stk.pop();
    }
    return convexHullPoints;
}

int main() {
    point points[] = {{-7,8},{-4,6},{2,6},{6,4},{8,6},{7,-2},{4,-6},{8,-7},{0,0},
        {3,-2},{6,-10},{0,-6},{-9,-5},{-8,-2},{-8,0},{-10,3},{-2,2},{-10,4}};
    int n = 18;
    vector result;
    result = findConvexHull(points, n);
    cout << "Boundary points of convex hull are: " << endl;
    vector::iterator it;
    for (it = result.begin(); it != result.end(); it++)
        cout << "(" << it->x << ", " << it->y << ") ";
}

ผลลัพธ์

Boundary points of convex hull are: (-9, -5) (-10, 3) (-10, 4) (-7, 8) (8, 6) (8, -7) (6, -10)