// ------------------------------------------------------------------------ // This program is complementary material for the book: // // Frank Nielsen // // Visual Computing: Geometry, Graphics, and Vision // // ISBN: 1-58450-427-7 // // Charles River Media, Inc. // // // All programs are available at http://www.charlesriver.com/visualcomputing/ // // You may use this program for ACADEMIC and PERSONAL purposes ONLY. // // // The use of this program in a commercial product requires EXPLICITLY // written permission from the author. The author is NOT responsible or // liable for damage or loss that may be caused by the use of this program. // // Copyright (c) 2005. Frank Nielsen. All rights reserved. // ------------------------------------------------------------------------ // ------------------------------------------------------------------------ // File: traits-geometrykernel.cpp // // Description: Compute the convex hull of a 2D point set using Andrew's algorithm. // The geometric kernel (arithmetic+predicate) is given to a traits class. // ------------------------------------------------------------------------ // This code has been adapted from an original code of Lutz Kettner #include "stdafx.h" #include #include #include #include #include #include #define W 800 #define H 800 // Notice: This code is not robust. See Chapter "Robustness" using namespace std; template class Point2D { public: NumberType x; NumberType y; bool operator < ( const Point2D & rhs) {return (x (const Point2D & rhs) {return (x>rhs.x);} bool operator == (const Point2D & rhs) {return (x==rhs.x);} }; template struct ConvexHullTraits { typedef Point2D Point; struct Leftturn { bool operator()( const Point& p, const Point& q, const Point& r) { if ((q.x-p.x) * (r.y-p.y) >(r.x-p.x) * (q.y-p.y)) return true; else return false; } }; Leftturn leftturn() const { return Leftturn(); } }; template OutputIterator ConvexHull( BidirectionalIterator first, BidirectionalIterator beyond, OutputIterator result, const ConvexHullTraits& traits) { typedef typename ConvexHullTraits::Point Point; vector hull; hull.push_back( *first); hull.push_back( *first); // First compute the lower convex hull BidirectionalIterator i = first; for ( ++i; i != beyond; ++i) { while ( traits.leftturn()( hull.end()[-2], *i, hull.back())) hull.pop_back(); hull.push_back( *i); } // Now compute the upper convex hull i = beyond; for ( --i; i != first; ) { --i; while ( traits.leftturn()( hull.end()[-2], *i, hull.back())) hull.pop_back(); hull.push_back( *i); } // Finally, get the full convex hull (intersection of lower and upper hulls) hull.pop_back(); hull.front() = hull.back(); hull.pop_back(); return copy( hull.begin(), hull.end(), result); } #define N 150 Point2D point; priority_queue > q; vector > set, result; ConvexHullTraits MyConvexHullPolicy; inline double drand() { return 0.1+0.8*(rand()/(double)RAND_MAX); } void disp( void ) { int i; glClearColor(1,1,1,1); glClear(GL_COLOR_BUFFER_BIT); glColor3f(0,0,1); glPointSize(2); glBegin(GL_POINTS); for(i=0;i