উত্তল পলিগনের মিনকোস্কি সাম#

সংজ্ঞা#

সমতলে দুটি বিন্দু সমষ্টি $A$ ও $B$ বিবেচনা করুন। মিনকোস্কি সাম $A + B$ সংজ্ঞায়িত হয় $\{a + b| a \in A, b \in B\}$ হিসেবে। এখানে আমরা সেই ক্ষেত্র বিবেচনা করব যেখানে $A$ ও $B$ উত্তল পলিগন $P$ ও $Q$ এবং তাদের অভ্যন্তর নিয়ে গঠিত। এই নিবন্ধ জুড়ে আমরা পলিগনকে তাদের শীর্ষবিন্দুগুলোর ক্রমিক অনুক্রম দিয়ে চিহ্নিত করব, যাতে $|P|$ বা $P_i$-এর মতো স্বরলিপি অর্থবহ হয়। দেখা যায় যে উত্তল পলিগন $P$ ও $Q$-এর যোগফল সর্বাধিক $|P| + |Q|$ শীর্ষবিন্দু বিশিষ্ট একটি উত্তল পলিগন।

অ্যালগরিদম#

এখানে আমরা পলিগনগুলোকে চক্রীয়ভাবে সংখ্যায়িত বিবেচনা করি, অর্থাৎ $P_{|P|} = P_0,\ Q_{|Q|} = Q_0$ ইত্যাদি।

যেহেতু যোগফলের আকার প্রারম্ভিক পলিগনগুলোর আকারের সাপেক্ষে লিনিয়ার, আমাদের একটি লিনিয়ার-টাইম অ্যালগরিদম খুঁজে বের করা উচিত। ধরুন উভয় পলিগন ঘড়ির কাঁটার বিপরীত দিকে সাজানো। এজগুলোর অনুক্রম $\{\overrightarrow{P_iP_{i+1}}\}$ ও $\{\overrightarrow{Q_jQ_{j+1}}\}$ পোলার কোণ অনুযায়ী সাজানো বিবেচনা করুন। আমরা দাবি করি যে $P + Q$-এর এজগুলোর অনুক্রম এই দুটি অনুক্রম পোলার কোণের ক্রম বজায় রেখে মার্জ করে এবং ক্রমিক সমদিক ভেক্টরগুলোকে তাদের যোগফল দিয়ে প্রতিস্থাপন করে পাওয়া যায়। এই ধারণার সরাসরি ব্যবহার লিনিয়ার-টাইম অ্যালগরিদম দেয়, তবে, বাহুগুলোর অনুক্রম থেকে $P + Q$-এর শীর্ষবিন্দু পুনরুদ্ধার করতে বারবার ভেক্টর যোগ প্রয়োজন, যা ফ্লোটিং-পয়েন্ট স্থানাঙ্কে কাজ করলে অবাঞ্ছিত প্রেসিশন সমস্যা আনতে পারে, তাই আমরা এই ধারণার একটি সামান্য পরিবর্তিত সংস্করণ বর্ণনা করব।

প্রথমে আমাদের শীর্ষবিন্দুগুলো এমনভাবে পুনর্বিন্যাস করতে হবে যাতে প্রতিটি পলিগনের প্রথম শীর্ষবিন্দুর y-স্থানাঙ্ক সবচেয়ে কম হয় (একাধিক এমন শীর্ষবিন্দু থাকলে সবচেয়ে ছোট x-স্থানাঙ্ক বিশিষ্টটি নিন)। এর পর উভয় পলিগনের বাহুগুলো পোলার কোণ অনুযায়ী সাজানো হয়ে যাবে, তাই ম্যানুয়ালি সাজানোর প্রয়োজন নেই। এখন আমরা দুটি পয়েন্টার $i$ ($P$-এর একটি শীর্ষবিন্দুতে) ও $j$ ($Q$-এর একটি শীর্ষবিন্দুতে) তৈরি করি, উভয়ই প্রথমে ০-তে সেট। আমরা $i < |P|$ বা $j < |Q|$ থাকাকালীন নিম্নলিখিত ধাপগুলো পুনরাবৃত্তি করি।

১. $P + Q$-তে $P_i + Q_j$ যোগ করুন।

২. $\overrightarrow{P_iP_{i + 1}}$ ও $\overrightarrow{Q_jQ_{j+1}}$-এর পোলার কোণ তুলনা করুন।

৩. যে পয়েন্টারটি ক্ষুদ্রতম কোণের সাথে সম্পর্কিত সেটি বাড়ান (কোণ সমান হলে উভয়ই বাড়ান)।

ভিজুয়ালাইজেশন#

এখানে একটি সুন্দর ভিজুয়ালাইজেশন, যা আপনাকে কী ঘটছে তা বুঝতে সাহায্য করতে পারে।

দুটি পলিগনের মধ্যে দূরত্ব#

মিনকোস্কি সামের সবচেয়ে সাধারণ অ্যাপ্লিকেশনগুলোর একটি হলো দুটি উত্তল পলিগনের মধ্যে দূরত্ব গণনা (বা সহজভাবে তারা ছেদ করে কি না তা পরীক্ষা করা)। দুটি উত্তল পলিগন $P$ ও $Q$-এর মধ্যে দূরত্ব সংজ্ঞায়িত হয় $\min\limits_{a \in P, b \in Q} ||a - b||$ হিসেবে। লক্ষ্য করা যায় যে দূরত্ব সর্বদা দুটি শীর্ষবিন্দু বা একটি শীর্ষবিন্দু ও একটি বাহুর মধ্যে অর্জিত হয়, তাই আমরা সহজেই $O(|P||Q|)$-এ দূরত্ব বের করতে পারি। তবে, মিনকোস্কি সামের চতুর ব্যবহারে আমরা কমপ্লেক্সিটি $O(|P| + |Q|)$-এ কমাতে পারি।

যদি আমরা $Q$ কে $(0, 0)$ বিন্দুর সাপেক্ষে প্রতিফলিত করে পলিগন $-Q$ পাই, তাহলে সমস্যাটি $P + (-Q)$-এর একটি বিন্দু ও $(0, 0)$-এর মধ্যে ক্ষুদ্রতম দূরত্ব বের করায় পরিণত হয়। আমরা নিম্নলিখিত ধারণা ব্যবহার করে সেই দূরত্ব লিনিয়ার সময়ে বের করতে পারি। যদি $(0, 0)$ পলিগনের ভেতরে বা সীমানায় থাকে, দূরত্ব $0$, অন্যথায় দূরত্ব $(0, 0)$ ও পলিগনের কোনো শীর্ষবিন্দু বা বাহুর মধ্যে অর্জিত হয়। যেহেতু মিনকোস্কি সাম লিনিয়ার সময়ে গণনা করা যায়, আমরা দুটি উত্তল পলিগনের মধ্যে দূরত্ব বের করার একটি লিনিয়ার-টাইম অ্যালগরিদম পাই।

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

নিচে পূর্ণসংখ্যা বিন্দু বিশিষ্ট পলিগনের জন্য মিনকোস্কি সামের ইমপ্লিমেন্টেশন দেওয়া হলো। লক্ষ্য করুন এই ক্ষেত্রে সব গণনা পূর্ণসংখ্যায় করা যায় কারণ পোলার কোণ গণনা ও সরাসরি তুলনা করার বদলে আমরা দুটি ভেক্টরের ক্রস প্রোডাক্টের চিহ্ন দেখতে পারি।

struct pt{
    long long x, y;
    pt operator + (const pt & p) const {
        return pt{x + p.x, y + p.y};
    }
    pt operator - (const pt & p) const {
        return pt{x - p.x, y - p.y};
    }
    long long cross(const pt & p) const {
        return x * p.y - y * p.x;
    }
};

void reorder_polygon(vector<pt> & P){
    size_t pos = 0;
    for(size_t i = 1; i < P.size(); i++){
        if(P[i].y < P[pos].y || (P[i].y == P[pos].y && P[i].x < P[pos].x))
            pos = i;
    }
    rotate(P.begin(), P.begin() + pos, P.end());
}

vector<pt> minkowski(vector<pt> P, vector<pt> Q){
    // the first vertex must be the lowest
    reorder_polygon(P);
    reorder_polygon(Q);
    // we must ensure cyclic indexing
    P.push_back(P[0]);
    P.push_back(P[1]);
    Q.push_back(Q[0]);
    Q.push_back(Q[1]);
    // main part
    vector<pt> result;
    size_t i = 0, j = 0;
    while(i < P.size() - 2 || j < Q.size() - 2){
        result.push_back(P[i] + Q[j]);
        auto cross = (P[i + 1] - P[i]).cross(Q[j + 1] - Q[j]);
        if(cross >= 0 && i < P.size() - 2)
            ++i;
        if(cross <= 0 && j < Q.size() - 2)
            ++j;
    }
    return result;
}