जांचें कि क्या दिया गया बिंदु बहुभुज के अंदर है

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

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

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

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

Input:
Points of a polygon {(0, 0), (10, 0), (10, 10), (0, 10)}. And point P (5, 3) to check.
Output:
Point is inside.

एल्गोरिदम

checkInside(Poly, n, p)

इनपुट: बहुभुज के बिंदु, बहुभुज के बिंदुओं की संख्या, जाँच करने के लिए बिंदु p।

आउटपुट: सही है जब p बहुभुज के अंदर है, अन्यथा असत्य है।

Begin
   if n<3, then
      return false
   create a line named exLine from point p to infinity, Slope of the line is 0°.
   count :=0 and i := 0
   repeat
      create line called side, from point poly[i] to poly[(i+1) mod n]
      if the side and exLine intersects, then
         if side and exLine are collinear, then
            if point p on the side, then
               return true
            else return false
         count := count + 1
      i := (i + 1) mod n
   until i ≠ 0
   return true if count is odd
End

उदाहरण

#include<iostream>
using namespace std;

struct Point {
   int x, y;
};

struct line {
   Point p1, p2;
};

bool onLine(line l1, Point p) {        //check whether p is on the line or not
   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;           //colinear
   else if(val < 0)
      return 2;          //anti-clockwise direction
      return 1;          //clockwise direction
}

bool isIntersect(line l1, line l2) {
   //four direction for two lines and points of other line
   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;           //they are intersecting
   if(dir1==0 && onLine(l1, l2.p1))        //when p2 of line2 are on the line1
      return true;
   if(dir2==0 && onLine(l1, l2.p2))         //when p1 of line2 are on the line1
      return true;
   if(dir3==0 && onLine(l2, l1.p1))       //when p2 of line1 are on the line2
      return true;
   if(dir4==0 && onLine(l2, l1.p2)) //when p1 of line1 are on the line2
      return true;
   return false;
}

bool checkInside(Point poly[], int n, Point p) {
   if(n < 3)
      return false;                  //when polygon has less than 3 edge, it is not polygon
   line exline = {p, {9999, p.y}};   //create a point at infinity, y is same as point p
   int count = 0;
   int i = 0;
   do {
      line side = {poly[i], poly[(i+1)%n]};     //forming a line from two consecutive points of poly
      if(isIntersect(side, exline)) {          //if side is intersects exline
         if(direction(side.p1, p, side.p2) == 0)
            return onLine(side, p);
         count++;
      }
      i = (i+1)%n;
   } while(i != 0);
      return count&1;             //when count is odd
}

int main() {
   // line polygon = {{{0,0},{10,0}},{{10,0},{10,10}},{{10,10},{0,10}},{{0,10},{0,0}}};
   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.