Artifact 05f672d15009c4b53de46381ddfeb3a685fba3df

• File _lib/geo/pt_in_poly.cpp
  • 2011-02-23 09:21:16 - part of checkin [4fd800b3a8] on branch trunk - Copied from private svn repository. (user: kinaba) [annotate]
• File lib/geo/pt_in_poly.cpp
  • 2011-02-23 11:18:09 - part of checkin [23dfcca431] on branch trunk - renamed _lib to lib (user: kinaba) [annotate]

//-------------------------------------------------------------
// The circle passing three points
//
// Verified by
//   - AOJ 0012 (only triangles)
//-------------------------------------------------------------

double outer_prod( CMP a, CMP b )
{
	return (a.real()*b.imag() - b.real()*a.imag())/2;
}

bool point_in_polygon( vector<CMP>& ps, CMP p )
{
	bool in = false;
	for(int i=0; i<ps.size(); ++i) {
		CMP a = ps[i] - p;
		CMP b = ps[(i+1)%ps.size()] - p;
		if(a.imag() > b.imag()) swap(a,b);
		if(a.imag()<=0 && 0<b.imag()) {
			if( outer_prod(a,b) < 0 )
				in = !in;
		}
		//if( outer_prod(a,b)==0 && inner_prod(a,b)<=0 ) return ON;
	}
	return in;
}