อัลกอริทึม Jarvis March (Convex Hull)

บทนำ

อัลกอริทึม Jarvis March ใช้ตรวจจับจุดมุมของ Convex Hull จากชุดจุดข้อมูลที่กำหนด

เริ่มจากจุดที่ซ้ายสุดของชุดข้อมูล เราเก็บจุดใน Convex Hull โดยการหมุนทวนเข็มนาฬิกา (Anti-clockwise) จากจุดปัจจุบัน สามารถเลือกจุดถัดไปได้โดยตรวจสอบทิศทาง (Orientation) ของจุดเหล่านั้นจากจุดปัจจุบัน เมื่อมุมใหญ่ที่สุด จุดนั้นจะถูกเลือก หลังจากครบจุดทั้งหมด เมื่อจุดถัดไปคือจุดเริ่มต้น ให้หยุดอัลกอริทึม

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

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]
    for แต่ละจุด i, do
        if points[i].x < start.x, then
            // หาจุดที่ซ้ายสุด
            start := points[i]
    done
    current := start
    เพิ่ม start point เข้า result set
    กำหนด colPts set เพื่อเก็บจุด collinear
    while true, do
        // เริ่ม loop ไม่รู้จบ
        next := points[i]
        for ทุกจุด i ยกเว้นจุดที่ 0, do
            if points[i] = current, then
                skip ส่วนต่อไป ไปรอบถัดไป
            val := cross product ของ current, next, points[i]
            if val > 0, then
                next := points[i]
                clear colPts array
            else if val = 0, then
                if next ใกล้ current กว่า points[i], then
                    เพิ่ม next ใน colPts
                    next := points[i]
                else
                    เพิ่ม points[i] ใน colPts
        done
        เพิ่มทุกไอเทมใน colPts เข้า result
        if next = start, then
            break loop
        insert next เข้า result
        current := next
    done
    return result
End

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

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

struct point {
    // กำหนดจุดสำหรับระนาบ 2D
    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 compare function ใช้ sort ใน 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 collinear
}

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 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 result;  // set ใช้ป้องกันจุดซ้ำ
    result.insert(start);
    vector *collinearPoints = new vector();
    
    while (true) {
        point nextTarget = points[0];
        for (int i = 1; i < n; i++) {
            if (points[i] == current)  // เมื่อจุดที่เลือกคือ current point ข้ามส่วนที่เหลือ
                continue;
            int val = crossProduct(current, nextTarget, points[i]);
            if (val > 0) {
                // เมื่อจุด i อยู่ด้านซ้าย
                nextTarget = points[i];
                collinearPoints = new vector();  // reset collinear points
            } else if (val == 0) {
                // ถ้าสามจุด collinear
                if (distance(current, nextTarget, points[i]) < 0) { // เพิ่มจุดที่ใกล้กว่าใน collinear list
                    collinearPoints->push_back(nextTarget);
                    nextTarget = points[i];
                } else {
                    collinearPoints->push_back(points[i]); // เมื่อจุด i ใกล้กว่าหรือเท่ากับ nextTarget
                }
            }
        }
        vector::iterator it;
        for (it = collinearPoints->begin(); it != collinearPoints->end(); it++) {
            result.insert(*it);  // เพิ่มจุดทั้งหมดใน collinear points เข้า result set
        }
        if (nextTarget == start)  // เมื่อจุดถัดไปคือ 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 result;
    result = findConvexHull(points, n);
    cout << "Boundary points of convex hull are: " << endl;
    set::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)