Artifact bec880bc3280bac95260f0971c9a970b73fb46f8

• File lib/geo/ccw.cpp
  • 2014-10-04 14:48:03 - part of checkin [ba015e9217] on branch trunk - 634 (user: kinaba) [annotate]

//-------------------------------------------------------------
// ccw
//
// Verified by
//   - SRM 492 Div1 LV1
//-------------------------------------------------------------

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

int ccw(const CMP& a, CMP b, CMP c) {
	b -= a; c -= a;
	if( outer_prod(b,c) > 0 ) return +1; // counter clockwise
	if( outer_prod(b,c) < 0 ) return -1; // clockwise
	if( inner_prod(b,c) < 0 ) return +2; // c--[a--b] on line
	if( norm(b) < norm(c) )   return -2; // [a--b]--c on line
	return 0; // [a--c--b] on line
}


// intersection of two line segments.
bool cross(CMP p1, CMP p2, CMP P1, CMP P2) {
	return ccw(p1,p2,P1)*ccw(p1,p2,P2)<=0 && ccw(P1,P2,p1)*ccw(P1,P2,p2)<=0;
}