ตรวจสอบว่าจุดที่กำหนดอยู่ในรูปหลายเหลี่ยมหรือไม่

ในปัญหานี้ มีให้รูปหลายเหลี่ยมหนึ่งรูป และให้จุด 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.