?? pointtopology.cpp
字號(hào):
// 判斷點(diǎn)是否在多邊形內(nèi)
#include <iostream>
#include <cmath>
#ifdef DEBUG
#include <fstream>
#endif
using namespace std;
const double INFINITY = 1e10;
const double ESP = 1e-5;
const int MAX_N = 1000;
struct Point {
double x, y;
};
struct LineSegment {
Point pt1, pt2;
};
int n, m, count;
Point polygon[MAX_N];
Point P;
inline double max(double x, double y)
{
return (x > y ? x : y);
}
inline double min(double x, double y)
{
return (x < y ? x : y);
}
// 計(jì)算叉乘 |P1P0| × |P2P0|
double Multiply(Point p1, Point p2, Point p0)
{
return ( (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y) );
}
// 判斷線段是否包含點(diǎn)point
bool IsOnline(Point point, LineSegment line)
{
return( ( fabs(Multiply(line.pt1, line.pt2, point)) < ESP ) &&
( ( point.x - line.pt1.x ) * ( point.x - line.pt2.x ) <= 0 ) &&
( ( point.y - line.pt1.y ) * ( point.y - line.pt2.y ) <= 0 ) );
}
// 判斷線段相交
bool Intersect(LineSegment L1, LineSegment L2)
{
return( (max(L1.pt1.x, L1.pt2.x) >= min(L2.pt1.x, L2.pt2.x)) &&
(max(L2.pt1.x, L2.pt2.x) >= min(L1.pt1.x, L1.pt2.x)) &&
(max(L1.pt1.y, L1.pt2.y) >= min(L2.pt1.y, L2.pt2.y)) &&
(max(L2.pt1.y, L2.pt2.y) >= min(L1.pt1.y, L1.pt2.y)) &&
(Multiply(L2.pt1, L1.pt2, L1.pt1) * Multiply(L1.pt2, L2.pt2, L1.pt1) >= 0) &&
(Multiply(L1.pt1, L2.pt2, L2.pt1) * Multiply(L2.pt2, L1.pt2, L2.pt1) >= 0)
);
}
// 判斷點(diǎn)在多邊形內(nèi)
bool InPolygon(Point polygon[], int n, Point point)
{
if (n == 1) {
return ( (fabs(polygon[0].x - point.x) < ESP) && (fabs(polygon[0].y - point.y) < ESP) );
}
else if (n == 2) {
LineSegment side;
side.pt1 = polygon[0];
side.pt2 = polygon[1];
return IsOnline(point, side);
}
int count = 0;
LineSegment line;
line.pt1 = point;
line.pt2.y = point.y;
line.pt2.x = - INFINITY;
for( int i = 0; i < n; i++ ) {
// 得到多邊形的一條邊
LineSegment side;
side.pt1 = polygon[i];
side.pt2 = polygon[(i + 1) % n];
if( IsOnline(point, side) ) { //點(diǎn)在邊上
return true;
}
// 如果side平行x軸則不作考慮
if( fabs(side.pt1.y - side.pt2.y) < ESP ) {
continue;
}
if( IsOnline(side.pt1, line) ) { //射線過頂點(diǎn)
if( side.pt1.y > side.pt2.y ) count++;
} else if( IsOnline(side.pt2, line) ) { ////射線過頂點(diǎn)
if( side.pt2.y > side.pt1.y ) count++;
} else if( Intersect(line, side) ) { //求交點(diǎn)
count++;
}
}
return ( count % 2 == 1 );
}
int main()
{
int i;
count = 0;
cin >> n;
while (n > 0) {
count++;
if (count > 1) cout << endl;
cout << "Problem " << count << ":" << endl;
cin >> m;
for ( i = 0; i < n; i++) {
cin >> polygon[i].x >> polygon[i].y;
}
for ( i = 0; i < m; i++) {
cin >> P.x >> P.y;
if (InPolygon(polygon, n, P)) {
cout << "Within" << endl;
} else {
cout << "Outside" << endl;
}
}
n = 0;
cin >> n;
}
return 0;
}
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -