pointtopology.cpp

输入任意两点的坐标可以计算任意两点间的距离

// 判断点是否在多边形内  

 




#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); 
} 

// 计算叉乘 |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) ); 
} 

// 判断线段是否包含点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) 
		); 
} 


// 判断点在多边形内 
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) ) { //点在边上
			return true; 
		} 
		
		// 如果side平行x轴则不作考虑 
		if( fabs(side.pt1.y - side.pt2.y) < ESP ) { 
			continue; 
		} 
		
		if( IsOnline(side.pt1, line) ) { //射线过顶点
			if( side.pt1.y > side.pt2.y ) count++; 
        } else if( IsOnline(side.pt2, line) ) { ////射线过顶点
            if( side.pt2.y > side.pt1.y ) count++; 
        } else if( Intersect(line, side) ) { //求交点
            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; 
}