Artifact f28d7402b7cb45295c7d9e9e95e0544528580e75

• File lib/geo/pt_in_poly.cpp
  • 2013-06-30 08:35:05 - part of checkin [07ad2e1283] on branch trunk - Geocon library update. (user: kinaba) [annotate]

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

double outer_prod(const CMP& a, const CMP& b) { return imag(conj(a)*b); }

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