โปรแกรม C++ ใช้ Jarvis March หา Convex Hull

อัลกอริทึม Jarvis March ใช้สำหรับหาจุดมุมของ Convex Hull จากชุดข้อมูลจุด เริ่มจากจุดที่อยู่ซ้ายสุดของชุดข้อมูล เราจะเก็บจุดใน Convex Hull โดยหมุนทวนเข็มนาฬิกา จากจุดปัจจุบัน สามารถเลือกจุดถัดไปได้โดยตรวจสอบการวางแนวของจุดเหล่านั้นจากจุดปัจจุบัน เมื่อมุมมากที่สุด จุดนั้นจะถูกเลือก หลังจากครบทุกจุด เมื่อจุดถัดไปคือจุดเริ่มต้น ให้หยุดอัลกอริทึม

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) (6, -10) (8, -7) (8, 6) (-7, 8) (-10, 4) (-10, 3)

อัลกอริทึม

findConvexHull(points, n)

Input: จุดต่างๆ และจำนวนจุด

Output: จุดมุมของ Convex Hull

Begin
    start := points[0]
    สำหรับแต่ละจุด i ทำ
        ถ้า points[i].x < start.x แล้ว
            // หาจุดซ้ายสุด
            start := points[i]
        จบ if
    จบ for
    current := start
    เพิ่มจุดเริ่มต้นในชุดผลลัพธ์
    กำหนดชุด colPts สำหรับเก็บจุด collinear
    while true ทำ
        // เริ่มลูปไม่รู้จบ
        next := points[i]
        สำหรับทุกจุด i ยกเว้นจุดที่ 0 ทำ
            ถ้า points[i] = current แล้ว
                ข้ามส่วนต่อไป ไปรอบถัดไป
            จบ if
            val := cross product ของ current, next, points[i]
            ถ้า val > 0 แล้ว
                next := points[i]
                ล้างอาร์เรย์ colPts
            ไม่เช่นนั้น ถ้า val = 0 แล้ว
                ถ้า next ใกล้ current กว่า points[i] แล้ว
                    เพิ่ม next ใน colPts
                    next := points[i]
                ไม่เช่นนั้น
                    เพิ่ม points[i] ใน colPts
                จบ if
            จบ if
        จบ for
        เพิ่มทุกอย่างใน colPts ลงในผลลัพธ์
        ถ้า next = start แล้ว
            ออกจากลูป
        จบ if
        เพิ่ม next ลงในผลลัพธ์
        current := next
    จบ while
    return result
End

ตัวอย่างโค้ด

#include <iostream>
#include <set>
#include <vector>
using namespace std;

struct point {
    int x, y;
    bool operator==(point p2) {
        if(x == p2.x && y == p2.y)
            return 1;
        return 0;
    }
    bool operator<(const point &p2)const {
        // ฟังก์ชันเปรียบเทียบ dummy ใช้สำหรับจัดเรียงใน set
        return true;
    }
};

int crossProduct(point a, point b, point c) {
    // หาตำแหน่งของ c จากเวกเตอร์ ab
    int y1 = a.y - b.y;
    int y2 = a.y - c.y;
    int x1 = a.x - b.x;
    int x2 = a.x - c.x;
    return y2*x1 - y1*x2; // ถ้าผลลัพธ์ < 0, c อยู่ซ้าย, > 0 อยู่ขวา, = 0 จุด a,b,c อยู่บนเส้นตรงเดียวกัน
}

int distance(point a, point b, point c) {
    int y1 = a.y - b.y;
    int y2 = a.y - c.y;
    int x1 = a.x - b.x;
    int x2 = a.x - c.x;
    int item1 = (y1*y1 + x1*x1);
    int item2 = (y2*y2 + x2*x2);
    if(item1 == item2)
        return 0; // เมื่อ b และ c อยู่ห่างจาก a เท่ากัน
    else if(item1 < item2)
        return -1; // เมื่อ b ใกล้ a กว่า
    return 1; // เมื่อ c ใกล้ a กว่า
}

set<point> findConvexHull(point points[], int n) {
    point start = points[0];
    for(int i = 1; i<n; i++) {
        // หาจุดซ้ายสุดสำหรับเริ่มต้น
        if(points[i].x < start.x)
            start = points[i];
    }
    point current = start;
    set<point> result;
    // ใช้ set เพื่อป้องกันจุดซ้ำ
    result.insert(start);
    vector<point> *collinearPoints = new vector<point>;
    
    while(true) {
        point nextTarget = points[0];
        for(int i = 1; i<n; i++) {
            if(points[i] == current) // เมื่อจุดที่เลือกคือจุดปัจจุบัน ข้ามส่วนที่เหลือ
                continue;
            
            int val = crossProduct(current, nextTarget, points[i]);
            if(val > 0) {
                // เมื่อจุดที่ i อยู่ด้านซ้าย
                nextTarget = points[i];
                collinearPoints = new vector<point>; // รีเซตจุด collinear
            }else if(val == 0) {
                // ถ้าจุด 3 จุดอยู่บนเส้นตรงเดียวกัน
                if(distance(current, nextTarget, points[i]) < 0) {
                    // เพิ่มจุดที่ใกล้กว่าในรายการ collinear
                    collinearPoints->push_back(nextTarget);
                    nextTarget = points[i];
                }else{
                    collinearPoints->push_back(points[i]); // เมื่อจุด i ใกล้กว่าหรือเท่ากับ nextTarget
                }
            }
        }
        
        vector<point>::iterator it;
        for(it = collinearPoints->begin(); it != collinearPoints->end(); it++) {
            result.insert(*it); // เพิ่มจุดทั้งหมดใน collinear points ลงใน result set
        }
        
        if(nextTarget == start) // เมื่อจุดถัดไปคือจุดเริ่มต้น หมายถึงครอบคลุมพื้นที่แล้ว
            break;
        
        result.insert(nextTarget);
        current = nextTarget;
    }
    return result;
}

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;
    set<point> result;
    result = findConvexHull(points, n);
    cout << "Boundary points of convex hull are: "<<endl;
    set<point>::iterator it;
    for(it = result.begin(); it!=result.end(); it++)
        cout << "(" << it->x << ", " <<it->y <<") ";
}

ผลลัพธ์

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