जांचें कि कोई दिया गया बिंदु बहुभुज के अंदर है या नहीं

परिचय

इस समस्या में, एक बहुभुज दिया गया है, और एक बिंदु P भी दिया गया है। हमें जांचना होगा कि बिंदु बहुभुज के अंदर है या बाहर।

इसे हल करने के लिए हम बिंदु P से एक सीधी रेखा खींचेंगे। यह अनंत तक फैली हुई है। रेखा क्षैतिज है, या यह x-अक्ष के समानांतर है।

उस रेखा से, हम गिनेंगे कि रेखा बहुभुज के पक्षों को कितनी बार प्रतिच्छेद करती है। जब बिंदु बहुभुज के अंदर होता है, तो यह पक्षों को विषम संख्या में बार प्रतिच्छेद करेगी, यदि P बहुभुज के किसी पक्ष पर रखा गया है, तो यह सम संख्या में बार काटेगा। यदि कोई भी शर्त सत्य नहीं है, तो यह बहुभुज के बाहर है।

इनपुट और आउटपुट

इनपुट: एक बहुभुज के बिंदु {(0, 0), (10, 0), (10, 10), (0, 10)}। और जांचने के लिए बिंदु P (5, 3)।
आउटपुट: बिंदु अंदर है।

एल्गोरिदम

checkInside(Poly, n, p)
इनपुट: बहुभुज के बिंदु, बहुभुज के बिंदुओं की संख्या, जांचने के लिए बिंदु p
आउटपुट: सत्य जब p बहुभुज के अंदर हो, अन्यथा असत्य

Begin
    यदि n < 3, तो
        असत्य लौटाएं
    exLine नामक एक रेखा बनाएं बिंदु p से अनंत तक, रेखा का ढलान 0° है।
    count := 0 और i := 0
    दोहराएं
        side नामक रेखा बनाएं, बिंदु poly[i] से poly[(i+1) mod n] तक
        यदि side और exLine प्रतिच्छेद करते हैं, तो
            यदि side और exLine संरेखी हैं, तो
                यदि बिंदु p side पर है, तो
                    सत्य लौटाएं
                अन्यथा असत्य लौटाएं
            count := count + 1
        i := (i + 1) mod n
    जब तक i ≠ 0
    सत्य लौटाएं यदि count विषम है
End

उदाहरण (C++ कोड)

#include <iostream>
using namespace std;

struct Point {
    int x, y;
};

struct line {
    Point p1, p2;
};

bool onLine(line l1, Point p) {
    // जांचें कि p रेखा पर है या नहीं
    if (p.x <= max(l1.p1.x, l1.p2.x) && p.x >= min(l1.p1.x, l1.p2.x) &&
        (p.y <= max(l1.p1.y, l1.p2.y) && p.y >= min(l1.p1.y, l1.p2.y)))
        return true;
    return false;
}

int direction(Point a, Point b, Point c) {
    int val = (b.y-a.y)*(c.x-b.x)-(b.x-a.x)*(c.y-b.y);
    if (val == 0)
        return 0; // संरेखी
    else if (val < 0)
        return 2; // वामावर्त दिशा
    return 1; // दक्षिणावर्त दिशा
}

bool isIntersect(line l1, line l2) {
    // दो रेखाओं और दूसरी रेखा के बिंदुओं के लिए चार दिशा
    int dir1 = direction(l1.p1, l1.p2, l2.p1);
    int dir2 = direction(l1.p1, l1.p2, l2.p2);
    int dir3 = direction(l2.p1, l2.p2, l1.p1);
    int dir4 = direction(l2.p1, l2.p2, l1.p2);
    if (dir1 != dir2 && dir3 != dir4)
        return true; // वे प्रतिच्छेद कर रहे हैं
    if (dir1==0 && onLine(l1, l2.p1)) // जब रेखा2 के p2 रेखा1 पर हैं
        return true;
    if (dir2==0 && onLine(l1, l2.p2)) // जब रेखा2 के p1 रेखा1 पर हैं
        return true;
    if (dir3==0 && onLine(l2, l1.p1)) // जब रेखा1 के p2 रेखा2 पर हैं
        return true;
    if (dir4==0 && onLine(l2, l1.p2)) // जब रेखा1 के p1 रेखा2 पर हैं
        return true;
    return false;
}

bool checkInside(Point poly[], int n, Point p) {
    if (n < 3)
        return false; // जब बहुभुज में 3 से कम किनारे हों, तो यह बहुभुज नहीं है
    line exline = {p, {9999, p.y}}; // अनंत पर एक बिंदु बनाएं, y बिंदु p के समान है
    int count = 0;
    int i = 0;
    do {
        line side = {poly[i], poly[(i+1)%n]}; // बहुभुज के दो क्रमागत बिंदुओं से रेखा बनाना
        if (isIntersect(side, exline)) {
            // यदि side exline को प्रतिच्छेद करता है
            if (direction(side.p1, p, side.p2) == 0)
                return onLine(side, p);
            count++;
        }
        i = (i+1)%n;
    } while (i != 0);
    return count & 1; // जब count विषम हो
}

int main() {
    Point polygon[] = {{0, 0}, {10, 0}, {10, 10}, {0, 10}};
    Point p = {5, 3};
    int n = 4;
    if (checkInside(polygon, n, p))
        cout << "Point is inside.";
    else
        cout << "Point is outside.";
}

आउटपुट

Point is inside.