資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學檢查給定點是否在多邊形內
在這個問題中，給定一個多邊形和一個點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.
更新於： 2020年6月17日
3K+ 次瀏覽
廣告