একটি প্রদত্ত বিন্দু একটি বহুভুজের ভিতরে আছে কিনা তা পরীক্ষা করুন

এই সমস্যায়, একটি বহুভুজ দেওয়া হয়েছে, এবং একটি বিন্দু 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.