দুটি রেখাখণ্ডের ছেদবিন্দু নির্ণয়#

আপনাকে দুটি রেখাখণ্ড AB ও CD দেওয়া আছে, তাদের প্রান্তবিন্দুর জোড়া হিসেবে বর্ণিত। প্রতিটি রেখাখণ্ড একটি একক বিন্দু হতে পারে যদি এর প্রান্তবিন্দু একই হয়। আপনাকে এই রেখাখণ্ডগুলোর ছেদ খুঁজে বের করতে হবে, যেটি ফাঁকা হতে পারে (যদি রেখাখণ্ডগুলো ছেদ না করে), একটি একক বিন্দু বা একটি রেখাখণ্ড (যদি প্রদত্ত রেখাখণ্ডগুলো ওভারল্যাপ করে)।

সমাধান#

আমরা রেখার ছেদবিন্দু-র মতোই রেখাখণ্ডের ছেদবিন্দু খুঁজতে পারি: রেখাখণ্ডের প্রান্তবিন্দু থেকে রেখার সমীকরণ পুনর্গঠন করি এবং পরীক্ষা করি তারা সমান্তরাল কি না।

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

সমান্তরাল রেখার ক্ষেত্র একটু জটিল (এক বা একাধিক রেখাখণ্ড একক বিন্দু হওয়ার ক্ষেত্রটিও এখানে পড়ে)। এই ক্ষেত্রে আমাদের পরীক্ষা করতে হবে উভয় রেখাখণ্ড একই রেখার অন্তর্গত কি না। না হলে, উত্তর হলো “কোনো ছেদ নেই”। হলে, উত্তর হলো একই রেখার অন্তর্গত রেখাখণ্ডগুলোর ছেদ, যেটি পাওয়া যায় উভয় রেখাখণ্ডের প্রান্তবিন্দুগুলো কোনো নির্দিষ্ট স্থানাঙ্কের ক্রমবর্ধমান ক্রমে সাজিয়ে বাম প্রান্তবিন্দুগুলোর মধ্যে ডানদিকেরটি ও ডান প্রান্তবিন্দুগুলোর মধ্যে বামদিকেরটি নিয়ে।

উভয় রেখাখণ্ড একক বিন্দু হলে, সেই বিন্দুগুলো অভিন্ন হতে হবে, এবং এই পরীক্ষা আলাদাভাবে করা সঙ্গত।

অ্যালগরিদমের শুরুতে একটি বাউন্ডিং বক্স পরীক্ষা যোগ করি — রেখাখণ্ডগুলো একই রেখার অন্তর্গত হওয়ার ক্ষেত্রে এটি প্রয়োজনীয়, এবং (একটি হালকা পরীক্ষা হওয়ায়) র‍্যান্ডম টেস্টে গড়ে অ্যালগরিদমকে দ্রুত কাজ করতে দেয়।

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

এখানে রেখা ও রেখাখণ্ড প্রক্রিয়াকরণের সব সহায়ক ফাংশনসহ ইমপ্লিমেন্টেশন দেওয়া হলো।

প্রধান ফাংশন intersect সত্য ফেরত দেয় যদি রেখাখণ্ডগুলোর অশূন্য ছেদ থাকে, এবং ছেদ রেখাখণ্ডের প্রান্তবিন্দু left ও right আর্গুমেন্টে সংরক্ষণ করে। উত্তর একটি একক বিন্দু হলে, left ও right-এ লেখা মান একই হবে।

const double EPS = 1E-9;

struct pt {
    double x, y;

    bool operator<(const pt& p) const
    {
        return x < p.x - EPS || (abs(x - p.x) < EPS && y < p.y - EPS);
    }
};

struct line {
    double a, b, c;

    line() {}
    line(pt p, pt q)
    {
        a = p.y - q.y;
        b = q.x - p.x;
        c = -a * p.x - b * p.y;
        norm();
    }

    void norm()
    {
        double z = sqrt(a * a + b * b);
        if (abs(z) > EPS)
            a /= z, b /= z, c /= z;
    }

    double dist(pt p) const { return a * p.x + b * p.y + c; }
};

double det(double a, double b, double c, double d)
{
    return a * d - b * c;
}

inline bool betw(double l, double r, double x)
{
    return min(l, r) <= x + EPS && x <= max(l, r) + EPS;
}

inline bool intersect_1d(double a, double b, double c, double d)
{
    if (a > b)
        swap(a, b);
    if (c > d)
        swap(c, d);
    return max(a, c) <= min(b, d) + EPS;
}

bool intersect(pt a, pt b, pt c, pt d, pt& left, pt& right)
{
    if (!intersect_1d(a.x, b.x, c.x, d.x) || !intersect_1d(a.y, b.y, c.y, d.y))
        return false;
    line m(a, b);
    line n(c, d);
    double zn = det(m.a, m.b, n.a, n.b);
    if (abs(zn) < EPS) {
        if (abs(m.dist(c)) > EPS || abs(n.dist(a)) > EPS)
            return false;
        if (b < a)
            swap(a, b);
        if (d < c)
            swap(c, d);
        left = max(a, c);
        right = min(b, d);
        return true;
    } else {
        left.x = right.x = -det(m.c, m.b, n.c, n.b) / zn;
        left.y = right.y = -det(m.a, m.c, n.a, n.c) / zn;
        return betw(a.x, b.x, left.x) && betw(a.y, b.y, left.y) &&
               betw(c.x, d.x, left.x) && betw(c.y, d.y, left.y);
    }
}