Trong bài toán này, một đa giác được đưa ra và một điểm P cũng được đưa ra. Chúng ta cần kiểm tra xem điểm nằm bên trong đa giác hay bên ngoài đa giác.
Để giải nó, chúng ta sẽ vẽ một đường thẳng từ điểm P. Nó kéo dài đến vô cùng. Đường nằm ngang hoặc song song với trục x.
Từ đường thẳng đó, chúng ta sẽ đếm xem đường thẳng cắt các cạnh của một đa giác bao nhiêu lần. Khi điểm nằm bên trong đa giác thì nó sẽ cắt các cạnh bên một số lẻ, nếu đặt P vào bất kỳ cạnh nào của đa giác thì nó sẽ cắt một số chẵn lần. Nếu không có điều kiện nào là đúng, thì nó nằm ngoài đa giác.
Đầu vào và Đầu ra
Input:
Points of a polygon {(0, 0), (10, 0), (10, 10), (0, 10)}. And point P (5, 3) to check.
Output:
Point is inside. Thuật toán
checkInside(Poly, n, p)
Đầu vào: Các điểm của đa giác, số điểm của đa giác, điểm p cần kiểm tra.
Đầu ra: Đúng khi p nằm bên trong đa giác, ngược lại là sai.
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
Ví dụ
#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.";
} Đầu ra
Point is inside.