কনভেক্স হাল নির্মাণ#

এই আর্টিকেলে আমরা বিন্দুর সেট থেকে কনভেক্স হাল নির্মাণের সমস্যা আলোচনা করব।

$N$ টি বিন্দু সমতলে দেওয়া আছে, আর লক্ষ্য হলো একটা কনভেক্স হাল (convex hull) তৈরি করা। মানে সবচেয়ে ছোট কনভেক্স পলিগন যেটা সবগুলো দেওয়া বিন্দু ধারণ করে।

আমরা দেখব গ্রাহাম স্ক্যান অ্যালগরিদম যা ১৯৭২ সালে Graham প্রকাশ করেছেন, এবং মনোটোন চেইন অ্যালগরিদম যা ১৯৭৯ সালে Andrew প্রকাশ করেছেন। উভয়ই $\mathcal{O}(N \log N)$, এবং অ্যাসিম্পটোটিকভাবে অপটিমাল (কারণ এটি প্রুফিত যে এর চেয়ে অ্যাসিম্পটোটিকভাবে ভালো কোনো অ্যালগরিদম নেই), কিছু সমস্যা ব্যতীত যেখানে প্যারালেল বা অনলাইন প্রসেসিং জড়িত।

গ্রাহাম স্ক্যান অ্যালগরিদম#

অ্যালগরিদমটি প্রথমে সবচেয়ে নিচের বিন্দু $P_0$ খুঁজে বের করে। যদি একই Y স্থানাঙ্কে একাধিক বিন্দু থাকে, তাহলে ছোট X স্থানাঙ্কবিশিষ্ট বিন্দুটি কনসিডার করা হয়। এই ধাপটি $\mathcal{O}(N)$ সময়ে কমপ্লিট হয়।

এরপর, অন্য সব বিন্দু পোলার কোণ অনুসারে ঘড়ির কাঁটার দিকে সাজানো হয়। যদি দুই বা ততোধিক বিন্দুর পোলার কোণ একই হয়, তাহলে $P_0$ থেকে দূরত্ব অনুসারে ক্রমবর্ধমান ক্রমে টাই ব্রেক করা হয়।

তারপর আমরা প্রতিটি বিন্দুর মধ্য দিয়ে একে একে ইটারেট করি, এবং নিশ্চিত করি বর্তমান বিন্দু এবং এর আগের দুটি বিন্দু ঘড়ির কাঁটার দিকে বাঁক নেয়, অন্যথায় আগের বিন্দু বাদ দেওয়া হয়, কারণ এটি একটি অ-কনভেক্স আকৃতি তৈরি করবে। ঘড়ির কাঁটার দিকে বা বিপরীত দিকে কিনা পরীক্ষা করা অরিয়েন্টেশন পরীক্ষার মাধ্যমে করা যায়।

আমরা বিন্দু সংরক্ষণের জন্য একটি স্ট্যাক ব্যবহার করি, এবং মূল বিন্দু $P_0$-তে পৌঁছালে অ্যালগরিদম শেষ হয় এবং আমরা কনভেক্স হালের সব বিন্দু ঘড়ির কাঁটার ক্রমে ধারণকারী স্ট্যাক রিটার্ন করি।

গ্রাহাম স্ক্যান করার সময় সমরেখ বিন্দু অন্তর্ভুক্ত করতে চাইলে, সাজানোর পরে আরেকটি ধাপ প্রয়োজন। $P_0$ থেকে সবচেয়ে বেশি পোলার দূরত্ববিশিষ্ট বিন্দুগুলো (যেগুলো সাজানো ভেক্টরের শেষে থাকবে) এবং সমরেখ বিন্দুগুলো নিতে হবে। এই রেখার বিন্দুগুলো উল্টো করতে হবে যাতে আমরা সব সমরেখ বিন্দু আউটপুট করতে পারি, অন্যথায় অ্যালগরিদম এই রেখার নিকটতম বিন্দু নিয়ে থেমে যাবে। এই ধাপটি অ্যালগরিদমের অ-সমরেখ সংস্করণে অন্তর্ভুক্ত করা উচিত নয়, নাহলে তুমি সবচেয়ে ছোট কনভেক্স হাল পাবে না।

ইমপ্লিমেন্টেশন#

struct pt {
    double x, y;
    bool operator == (pt const& t) const {
        return x == t.x && y == t.y;
    }
};

int orientation(pt a, pt b, pt c) {
    double v = a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y);
    if (v < 0) return -1; // clockwise
    if (v > 0) return +1; // counter-clockwise
    return 0;
}

bool cw(pt a, pt b, pt c, bool include_collinear) {
    int o = orientation(a, b, c);
    return o < 0 || (include_collinear && o == 0);
}
bool collinear(pt a, pt b, pt c) { return orientation(a, b, c) == 0; }

void convex_hull(vector<pt>& a, bool include_collinear = false) {
    pt p0 = *min_element(a.begin(), a.end(), [](pt a, pt b) {
        return make_pair(a.y, a.x) < make_pair(b.y, b.x);
    });
    sort(a.begin(), a.end(), [&p0](const pt& a, const pt& b) {
        int o = orientation(p0, a, b);
        if (o == 0)
            return (p0.x-a.x)*(p0.x-a.x) + (p0.y-a.y)*(p0.y-a.y)
                < (p0.x-b.x)*(p0.x-b.x) + (p0.y-b.y)*(p0.y-b.y);
        return o < 0;
    });
    if (include_collinear) {
        int i = (int)a.size()-1;
        while (i >= 0 && collinear(p0, a[i], a.back())) i--;
        reverse(a.begin()+i+1, a.end());
    }

    vector<pt> st;
    for (int i = 0; i < (int)a.size(); i++) {
        while (st.size() > 1 && !cw(st[st.size()-2], st.back(), a[i], include_collinear))
            st.pop_back();
        st.push_back(a[i]);
    }

    if (include_collinear == false && st.size() == 2 && st[0] == st[1])
        st.pop_back();

    a = st;
}

মনোটোন চেইন অ্যালগরিদম#

অ্যালগরিদমটি প্রথমে সবচেয়ে বামের ও সবচেয়ে ডানের বিন্দু A ও B খুঁজে বের করে। একাধিক এরকম বিন্দু থাকলে, বামদের মধ্যে সবচেয়ে নিচেরটি (সর্বনিম্ন Y-স্থানাঙ্ক) A হিসেবে এবং ডানদের মধ্যে সবচেয়ে উপরেরটি (সর্বোচ্চ Y-স্থানাঙ্ক) B হিসেবে নেওয়া হয়। স্পষ্টতই, A ও B উভয়কেই কনভেক্স হালে থাকতে হবে কারণ তারা সবচেয়ে দূরে এবং দেওয়া বিন্দুগুলোর কোনো জোড়ার রেখা দ্বারা ধারণ করা যায় না।

এখন, AB দিয়ে একটি রেখা আঁকুন। এটি অন্য সব বিন্দুকে দুটি সেটে ভাগ করে, S1 ও S2, যেখানে S1-এ A ও B সংযোগকারী রেখার উপরের সব বিন্দু এবং S2-তে A ও B যোগকারী রেখার নিচের সব বিন্দু আছে। A ও B সংযোগকারী রেখার উপর থাকা বিন্দু যেকোনো সেটে থাকতে পারে। A ও B বিন্দু উভয় সেটেই থাকে। এখন অ্যালগরিদম উপরের সেট S1 ও নিচের সেট S2 তৈরি করে এবং তারপর উত্তর পেতে এগুলো একত্রিত করে।

উপরের সেট পেতে, আমরা সব বিন্দু x-স্থানাঙ্ক অনুসারে সাজাই। প্রতিটি বিন্দুর জন্য পরীক্ষা করি — বর্তমান বিন্দু শেষ বিন্দু (যেটাকে আমরা B হিসেবে ডিফাইন করেছি) কিনা, অথবা A ও বর্তমান বিন্দুর রেখা এবং বর্তমান বিন্দু ও B-র রেখার মধ্যবর্তী অরিয়েন্টেশন ঘড়ির কাঁটার দিকে কিনা। সেই ক্ষেত্রগুলোতে বর্তমান বিন্দু উপরের সেট S1-এ থাকে। ঘড়ির কাঁটার দিকে বা বিপরীত দিকে পরীক্ষা করা অরিয়েন্টেশন পরীক্ষার মাধ্যমে করা যায়।

দেওয়া বিন্দু উপরের সেটে থাকলে, আমরা উপরের কনভেক্স হালের দ্বিতীয় শেষ ও শেষ বিন্দু সংযোগকারী রেখা এবং শেষ বিন্দু ও বর্তমান বিন্দু সংযোগকারী রেখার দ্বারা গঠিত কোণ পরীক্ষা করি। যদি কোণটি ঘড়ির কাঁটার দিকে না হয়, তাহলে উপরের কনভেক্স হালে সবশেষে যোগ করা বিন্দুটি সরিয়ে দিই কারণ বর্তমান বিন্দু কনভেক্স হালে যোগ হলে আগের বিন্দুটি ধারণ করতে পারবে।

নিচের সেট S2-র জন্যও একই যুক্তি প্রযোজ্য। যদি — বর্তমান বিন্দু B হয়, অথবা A ও বর্তমান বিন্দু এবং বর্তমান বিন্দু ও B দ্বারা গঠিত রেখার অরিয়েন্টেশন ঘড়ির কাঁটার বিপরীত হয় — তাহলে এটি S2-তে থাকে।

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

চূড়ান্ত কনভেক্স হাল উপরের আর নিচের কনভেক্স হালের ইউনিয়ন থেকে পাওয়া যায়, ঘড়ির কাঁটার দিকে একটা হাল তৈরি করে। ইমপ্লিমেন্টেশনটা এরকম:

কলিনিয়ার (collinear) বিন্দু দরকার হলে, CW/CCW রুটিনে সেগুলো চেক করতে হবে। তবে, এটা একটা ডিজেনারেট কেস অনুমতি দেয় যেখানে সব ইনপুট বিন্দু একটা রেখায় কলিনিয়ার, আর অ্যালগরিদম ডুপ্লিকেট বিন্দু আউটপুট করবে। এটা ফিক্স করতে, আমরা চেক করি উপরের হালে সব বিন্দু আছে কিনা। থাকলে বিন্দুগুলো রিভার্স করে রিটার্ন করি, কারণ গ্রাহাম ইমপ্লিমেন্টেশন এই কেসে তাই রিটার্ন করবে।

ইমপ্লিমেন্টেশন#

struct pt {
    double x, y;
};

int orientation(pt a, pt b, pt c) {
    double v = a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y);
    if (v < 0) return -1; // clockwise
    if (v > 0) return +1; // counter-clockwise
    return 0;
}

bool cw(pt a, pt b, pt c, bool include_collinear) {
    int o = orientation(a, b, c);
    return o < 0 || (include_collinear && o == 0);
}
bool ccw(pt a, pt b, pt c, bool include_collinear) {
    int o = orientation(a, b, c);
    return o > 0 || (include_collinear && o == 0);
}

void convex_hull(vector<pt>& a, bool include_collinear = false) {
    if (a.size() == 1)
        return;

    sort(a.begin(), a.end(), [](pt a, pt b) {
        return make_pair(a.x, a.y) < make_pair(b.x, b.y);
    });
    pt p1 = a[0], p2 = a.back();
    vector<pt> up, down;
    up.push_back(p1);
    down.push_back(p1);
    for (int i = 1; i < (int)a.size(); i++) {
        if (i == a.size() - 1 || cw(p1, a[i], p2, include_collinear)) {
            while (up.size() >= 2 && !cw(up[up.size()-2], up[up.size()-1], a[i], include_collinear))
                up.pop_back();
            up.push_back(a[i]);
        }
        if (i == a.size() - 1 || ccw(p1, a[i], p2, include_collinear)) {
            while (down.size() >= 2 && !ccw(down[down.size()-2], down[down.size()-1], a[i], include_collinear))
                down.pop_back();
            down.push_back(a[i]);
        }
    }

    if (include_collinear && up.size() == a.size()) {
        reverse(a.begin(), a.end());
        return;
    }
    a.clear();
    for (int i = 0; i < (int)up.size(); i++)
        a.push_back(up[i]);
    for (int i = down.size() - 2; i > 0; i--)
        a.push_back(down[i]);
}

অনুশীলন সমস্যা#