ডেটা স্ট্রাকচারে কনভেক্স হাল উদাহরণ

এখানে কনভেক্স হালের একটি উদাহরণ দেখব। ধরা যাক আমাদের একটি পয়েন্ট সেট রয়েছে। আমাদের কম পয়েন্ট নিয়ে একটি পলিগন বানাতে হবে, যা দেওয়া সব পয়েন্ট কভার করবে। এই সেকশনে আমরা জারভিস মার্চ অ্যালগরিদম দেখব কনভেক্স হাল পেতে।

জারভিস মার্চ অ্যালগরিদম একটি দिये गये ডেটা পয়েন্ট সেট থেকে কনভেক্স হালের কনার পয়েন্টগুলো ডিটেক্ট করতে ব্যবহৃত হয়।

ডেটা সেটের সবচেয়ে বাম পয়েন্ট থেকে শুরু করে, অ্যান্টি-ক্লকওয়াইজ রোটেশন দিয়ে পয়েন্টগুলো কনভেক্স হালে রাখি। একটি কারেন্ট পয়েন্ট থেকে, আমরা পরবর্তী পয়েন্ট বেছে নিতে পারি সেই পয়েন্টগুলোর ওরিয়েন্টেশন চেক করে কারেন্ট পয়েন্ট থেকে। যখন কোণটি সবচেয়ে বড়, তখন সেই পয়েন্টটি বেছে নেওয়া হয়। সব পয়েন্ট কমপ্লিট হলে, যখন নেক্স্ট পয়েন্ট স্টার্ট পয়েন্ট হয়, অ্যালগরিদম বন্ধ করুন।

ইনপুট - পয়েন্ট সেট: {(-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)}

আউটপুট - কনভেক্স হালের বাউন্ডারি পয়েন্টগুলো -

(-9, -5) (6, -10) (8, -7) (8, 6) (-7, 8) (-10, 4) (-10, 3)

অ্যালগরিদম

findConvexHull(points, n)
Input: The points, number of points.
Output: Corner points of convex hull.
Begin
    start := points[0]
    for each point i, do
        if points[i].x < start.x, then // get the left most point
            start := points[i]
    done
    current := start
    add start point to the result set.
    define colPts set to store collinear points
    while true, do //start an infinite loop
        next := points[i]
        for all points i except 0th point, do
            if points[i] = current, then
                skip the next part, go for next iteration
            val := cross product of current, next, points[i]
            if val > 0, then
                next := points[i]
                clear the colPts array
            else if cal = 0, then
                if next is closer to current than points[i], then
                    add next in the colPts
                    next := points[i]
                else
                    add points[i] in the colPts
        done
        add all items in the colPts into the result
        if next = start, then
            break the loop
        insert next into the result
        current := next
    done
    return result
End

উদাহরণ

#include 
#include 
#include 
using namespace std;
struct point { //define points for 2d plane
    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 used to sort in set
        return true;
    }
};
int crossProduct(point a, point b, point c) { //finds the place of c from ab vector
    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; //if result < 0, c in the left, > 0, c in the right, = 0, a,b,c are 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; //when b and c are in same distance from a
    else if(item1 < item2)
        return -1; //when b is closer to a
    return 1; //when c is closer to a
}
set findConvexHull(point points[], int n) {
    point start = points[0];
    for(int i = 1; i result; //set is used to avoid entry of duplicate points
    result.insert(start);
    vector *collinearPoints = new vector();
    while(true) {
        point nextTarget = points[0];
        for(int i = 1; i 0) { //when ith point is on the left side
                nextTarget = points[i];
                collinearPoints = new vector(); //reset collinear points
            } else if(val == 0) { //if three points are collinear
                if(distance(current, nextTarget, points[i]) < 0) { //add closer one to collinear list
                    collinearPoints->push_back(nextTarget);
                    nextTarget = points[i];
                } else {
                    collinearPoints->push_back(points[i]); //when ith point is closer or same as nextTarget
                }
            }
        }
        vector::iterator it;
        for(it = collinearPoints->begin(); it != collinearPoints->end(); it++) {
            result.insert(*it); //add allpoints in collinear points to result set
        }
        if(nextTarget == start) //when next point is start it means, the area covered
            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)