|
BWAPI
|
00001 // Copyright (c) 1997-2001 Freie Universitaet Berlin (Germany). 00002 // All rights reserved. 00003 // 00004 // This file is part of CGAL (www.cgal.org); you may redistribute it under 00005 // the terms of the Q Public License version 1.0. 00006 // See the file LICENSE.QPL distributed with CGAL. 00007 // 00008 // Licensees holding a valid commercial license may use this file in 00009 // accordance with the commercial license agreement provided with the software. 00010 // 00011 // This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE 00012 // WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. 00013 // 00014 // $URL: svn+ssh://scm.gforge.inria.fr/svn/cgal/branches/CGAL-3.5-branch/Min_ellipse_2/include/CGAL/Min_ellipse_2.h $ 00015 // $Id: Min_ellipse_2.h 41714 2008-01-20 20:24:20Z spion $ 00016 // 00017 // 00018 // Author(s) : Sven Schoenherr <sven@inf.ethz.ch>, Bernd Gaertner 00019 00020 #ifndef CGAL_MIN_ELLIPSE_2_H 00021 #define CGAL_MIN_ELLIPSE_2_H 00022 00023 #include <CGAL/Optimisation/basic.h> 00024 #include <CGAL/Random.h> 00025 #include <list> 00026 #include <vector> 00027 #include <algorithm> 00028 #include <iostream> 00029 00030 CGAL_BEGIN_NAMESPACE 00031 00032 // Class declaration 00033 // ================= 00034 template < class Traits_ > 00035 class Min_ellipse_2; 00036 00037 // Class interface 00038 // =============== 00039 template < class Traits_ > 00040 class Min_ellipse_2 { 00041 public: 00042 // types 00043 typedef Traits_ Traits; 00044 typedef typename Traits_::Point Point; 00045 typedef typename Traits_::Ellipse Ellipse; 00046 typedef typename std::list<Point>::const_iterator Point_iterator; 00047 typedef const Point * Support_point_iterator; 00048 00049 /************************************************************************** 00050 WORKAROUND: Some compilers are unable to match member functions defined 00051 outside the class template. Therefore, all member functions are implemented 00052 in the class interface. 00053 00054 // creation 00055 template < class InputIterator > 00056 Min_ellipse_2( InputIterator first, 00057 InputIterator last, 00058 bool randomize = false, 00059 Random& random = default_random, 00060 const Traits& traits = Traits()); 00061 00062 Min_ellipse_2( const Traits& traits = Traits()); 00063 Min_ellipse_2( const Point& p, 00064 const Traits& traits = Traits()); 00065 Min_ellipse_2( Point p, 00066 Point q, 00067 const Traits& traits = Traits()); 00068 Min_ellipse_2( const Point& p1, 00069 const Point& p2, 00070 const Point& p3, 00071 const Traits& traits = Traits()); 00072 Min_ellipse_2( const Point& p1, 00073 const Point& p2, 00074 const Point& p3, 00075 const Point& p4, 00076 const Traits& traits = Traits()); 00077 Min_ellipse_2( const Point& p1, 00078 const Point& p2, 00079 const Point& p3, 00080 const Point& p4, 00081 const Point& p5, 00082 const Traits& traits = Traits()); 00083 ~Min_ellipse_2( ); 00084 00085 // access functions 00086 int number_of_points ( ) const; 00087 int number_of_support_points( ) const; 00088 00089 Point_iterator points_begin( ) const; 00090 Point_iterator points_end ( ) const; 00091 00092 Support_point_iterator support_points_begin( ) const; 00093 Support_point_iterator support_points_end ( ) const; 00094 00095 const Point& support_point( int i) const; 00096 00097 const Ellipse& ellipse( ) const; 00098 00099 // predicates 00100 CGAL::Bounded_side bounded_side( const Point& p) const; 00101 bool has_on_bounded_side ( const Point& p) const; 00102 bool has_on_boundary ( const Point& p) const; 00103 bool has_on_unbounded_side ( const Point& p) const; 00104 00105 bool is_empty ( ) const; 00106 bool is_degenerate( ) const; 00107 00108 // modifiers 00109 void insert( const Point& p); 00110 void insert( const Point* first, 00111 const Point* last ); 00112 void insert( std::list<Point>::const_iterator first, 00113 std::list<Point>::const_iterator last ); 00114 void insert( std::istream_iterator<Point,std::ptrdiff_t> first, 00115 std::istream_iterator<Point,std::ptrdiff_t> last ); 00116 void clear( ); 00117 00118 // validity check 00119 bool is_valid( bool verbose = false, int level = 0) const; 00120 00121 // miscellaneous 00122 const Traits& traits( ) const; 00123 **************************************************************************/ 00124 00125 private: 00126 // private data members 00127 Traits tco; // traits class object 00128 std::list<Point> points; // doubly linked list of points 00129 int n_support_points; // number of support points 00130 Point* support_points; // array of support points 00131 00132 00133 // copying and assignment not allowed! 00134 Min_ellipse_2( const Min_ellipse_2<Traits_>&); 00135 Min_ellipse_2<Traits_>& operator = ( const Min_ellipse_2<Traits_>&); 00136 00137 // ============================================================================ 00138 00139 // Class implementation 00140 // ==================== 00141 00142 public: 00143 // Access functions and predicates 00144 // ------------------------------- 00145 // #points and #support points 00146 inline 00147 int 00148 number_of_points( ) const 00149 { 00150 return( points.size()); 00151 } 00152 00153 inline 00154 int 00155 number_of_support_points( ) const 00156 { 00157 return( n_support_points); 00158 } 00159 00160 // is_... predicates 00161 inline 00162 bool 00163 is_empty( ) const 00164 { 00165 return( number_of_support_points() == 0); 00166 } 00167 00168 inline 00169 bool 00170 is_degenerate( ) const 00171 { 00172 return( number_of_support_points() < 3); 00173 } 00174 00175 // access to points and support points 00176 inline 00177 Point_iterator 00178 points_begin( ) const 00179 { 00180 return( points.begin()); 00181 } 00182 00183 inline 00184 Point_iterator 00185 points_end( ) const 00186 { 00187 return( points.end()); 00188 } 00189 00190 inline 00191 Support_point_iterator 00192 support_points_begin( ) const 00193 { 00194 return( support_points); 00195 } 00196 00197 inline 00198 Support_point_iterator 00199 support_points_end( ) const 00200 { 00201 return( support_points+n_support_points); 00202 } 00203 00204 // random access for support points 00205 inline 00206 const Point& 00207 support_point( int i) const 00208 { 00209 CGAL_optimisation_precondition( (i >= 0) && 00210 (i < number_of_support_points())); 00211 return( support_points[ i]); 00212 } 00213 // ellipse 00214 inline 00215 const Ellipse& 00216 ellipse( ) const 00217 { 00218 return( tco.ellipse); 00219 } 00220 00221 00222 // in-ellipse test predicates 00223 inline 00224 CGAL::Bounded_side 00225 bounded_side( const Point& p) const 00226 { 00227 return( tco.ellipse.bounded_side( p)); 00228 } 00229 00230 inline 00231 bool 00232 has_on_bounded_side( const Point& p) const 00233 { 00234 return( tco.ellipse.has_on_bounded_side( p)); 00235 } 00236 00237 inline 00238 bool 00239 has_on_boundary( const Point& p) const 00240 { 00241 return( tco.ellipse.has_on_boundary( p)); 00242 } 00243 00244 inline 00245 bool 00246 has_on_unbounded_side( const Point& p) const 00247 { 00248 return( tco.ellipse.has_on_unbounded_side( p)); 00249 } 00250 00251 private: 00252 // Private member functions 00253 // ------------------------ 00254 // compute_ellipse 00255 inline 00256 void 00257 compute_ellipse( ) 00258 { 00259 switch ( n_support_points) { 00260 case 5: 00261 tco.ellipse.set( support_points[ 0], 00262 support_points[ 1], 00263 support_points[ 2], 00264 support_points[ 3], 00265 support_points[ 4]); 00266 break; 00267 case 4: 00268 tco.ellipse.set( support_points[ 0], 00269 support_points[ 1], 00270 support_points[ 2], 00271 support_points[ 3]); 00272 break; 00273 case 3: 00274 tco.ellipse.set( support_points[ 0], 00275 support_points[ 1], 00276 support_points[ 2]); 00277 break; 00278 case 2: 00279 tco.ellipse.set( support_points[ 0], support_points[ 1]); 00280 break; 00281 case 1: 00282 tco.ellipse.set( support_points[ 0]); 00283 break; 00284 case 0: 00285 tco.ellipse.set( ); 00286 break; 00287 default: 00288 CGAL_optimisation_assertion( ( n_support_points >= 0) && 00289 ( n_support_points <= 5) ); } 00290 } 00291 00292 void 00293 me( const Point_iterator& last, int n_sp) 00294 { 00295 // compute ellipse through support points 00296 n_support_points = n_sp; 00297 compute_ellipse(); 00298 if ( n_sp == 5) return; 00299 00300 // test first n points 00301 typename std::list<Point>::iterator point_iter = points.begin(); 00302 for ( ; last != point_iter; ) { 00303 const Point& p = *point_iter; 00304 00305 // p not in current ellipse? 00306 if ( has_on_unbounded_side( p)) { 00307 00308 // recursive call with p as additional support point 00309 support_points[ n_sp] = p; 00310 me( point_iter, n_sp+1); 00311 00312 // move current point to front 00313 points.splice( points.begin(), points, point_iter++); } 00314 00315 else 00316 ++point_iter; } 00317 } 00318 00319 public: 00320 // Constructors 00321 // ------------ 00322 // STL-like constructor (member template) 00323 template < class InputIterator > 00324 Min_ellipse_2( InputIterator first, 00325 InputIterator last, 00326 bool randomize 00327 #if !defined(_MSC_VER) || _MSC_VER > 1300 00328 = false 00329 #endif 00330 , 00331 Random& random = default_random, 00332 const Traits& traits = Traits()) 00333 : tco( traits) 00334 { 00335 // allocate support points' array 00336 support_points = new Point[ 5]; 00337 00338 // range of points not empty? 00339 if ( first != last) { 00340 00341 // store points 00342 if ( randomize) { 00343 00344 // shuffle points at random 00345 std::vector<Point> v( first, last); 00346 std::random_shuffle( v.begin(), v.end(), random); 00347 std::copy( v.begin(), v.end(), 00348 std::back_inserter( points)); } 00349 else 00350 std::copy( first, last, std::back_inserter( points)); } 00351 00352 // compute me 00353 me( points.end(), 0); 00354 } 00355 00356 // default constructor 00357 inline 00358 Min_ellipse_2( const Traits& traits = Traits()) 00359 : tco( traits), n_support_points( 0) 00360 { 00361 // allocate support points' array 00362 support_points = new Point[ 5]; 00363 00364 // initialize ellipse 00365 tco.ellipse.set(); 00366 00367 CGAL_optimisation_postcondition( is_empty()); 00368 } 00369 00370 // constructor for one point 00371 inline 00372 Min_ellipse_2( const Point& p, const Traits& traits = Traits()) 00373 : tco( traits), points( 1, p), n_support_points( 1) 00374 { 00375 // allocate support points' array 00376 support_points = new Point[ 5]; 00377 00378 // initialize ellipse 00379 support_points[ 0] = p; 00380 tco.ellipse.set( p); 00381 00382 CGAL_optimisation_postcondition( is_degenerate()); 00383 } 00384 00385 // constructor for two points 00386 // This was const Point& but then Intel 7.0/.net2003 messes it up 00387 // with the constructor taking an iterator range 00388 inline 00389 Min_ellipse_2( Point p1, Point p2, 00390 const Traits& traits = Traits()) 00391 : tco( traits) 00392 { 00393 // allocate support points' array 00394 support_points = new Point[ 5]; 00395 00396 // store points 00397 points.push_back( p1); 00398 points.push_back( p2); 00399 00400 // compute me 00401 me( points.end(), 0); 00402 00403 CGAL_optimisation_postcondition( is_degenerate()); 00404 } 00405 00406 // constructor for three points 00407 inline 00408 Min_ellipse_2( const Point& p1, const Point& p2, const Point& p3, 00409 const Traits& traits = Traits()) 00410 : tco( traits) 00411 { 00412 // allocate support points' array 00413 support_points = new Point[ 5]; 00414 00415 // store points 00416 points.push_back( p1); 00417 points.push_back( p2); 00418 points.push_back( p3); 00419 00420 // compute me 00421 me( points.end(), 0); 00422 } 00423 00424 // constructor for four points 00425 inline 00426 Min_ellipse_2( const Point& p1, const Point& p2, 00427 const Point& p3, const Point& p4, 00428 const Traits& traits = Traits()) 00429 : tco( traits) 00430 { 00431 // allocate support points' array 00432 support_points = new Point[ 5]; 00433 00434 // store points 00435 points.push_back( p1); 00436 points.push_back( p2); 00437 points.push_back( p3); 00438 points.push_back( p4); 00439 00440 // compute me 00441 me( points.end(), 0); 00442 } 00443 00444 // constructor for five points 00445 inline 00446 Min_ellipse_2( const Point& p1, const Point& p2, const Point& p3, 00447 const Point& p4, const Point& p5, 00448 const Traits& traits = Traits()) 00449 : tco( traits) 00450 { 00451 // allocate support points' array 00452 support_points = new Point[ 5]; 00453 00454 // store points 00455 points.push_back( p1); 00456 points.push_back( p2); 00457 points.push_back( p3); 00458 points.push_back( p4); 00459 points.push_back( p5); 00460 00461 // compute me 00462 me( points.end(), 0); 00463 } 00464 00465 00466 // Destructor 00467 // ---------- 00468 inline 00469 ~Min_ellipse_2( ) 00470 { 00471 // free support points' array 00472 delete[] support_points; 00473 } 00474 00475 // Modifiers 00476 // --------- 00477 void 00478 insert( const Point& p) 00479 { 00480 // p not in current ellipse? 00481 if ( has_on_unbounded_side( p)) { 00482 00483 // p new support point 00484 support_points[ 0] = p; 00485 00486 // recompute me 00487 me( points.end(), 1); 00488 00489 // store p as the first point in list 00490 points.push_front( p); } 00491 else 00492 00493 // append p to the end of the list 00494 points.push_back( p); 00495 } 00496 template < class InputIterator > 00497 void 00498 insert( InputIterator first, InputIterator last) 00499 { 00500 for ( ; first != last; ++first) 00501 insert( *first); 00502 } 00503 00504 void 00505 clear( ) 00506 { 00507 points.erase( points.begin(), points.end()); 00508 n_support_points = 0; 00509 tco.ellipse.set(); 00510 } 00511 00512 00513 // Validity check 00514 // -------------- 00515 bool 00516 is_valid( bool verbose = false, int level = 0) const 00517 { 00518 using namespace std; 00519 00520 CGAL::Verbose_ostream verr( verbose); 00521 verr << endl; 00522 verr << "CGAL::Min_ellipse_2<Traits>::" << endl; 00523 verr << "is_valid( true, " << level << "):" << endl; 00524 verr << " |P| = " << number_of_points() 00525 << ", |S| = " << number_of_support_points() << endl; 00526 00527 // containment check (a) 00528 verr << " a) containment check..." << flush; 00529 Point_iterator point_iter; 00530 for ( point_iter = points_begin(); 00531 point_iter != points_end(); 00532 ++point_iter) 00533 if ( has_on_unbounded_side( *point_iter)) 00534 return( CGAL::_optimisation_is_valid_fail( verr, 00535 "ellipse does not contain all points")); 00536 verr << "passed." << endl; 00537 00538 // support set checks (b)+(c) (not yet implemented) 00539 00540 // alternative support set check 00541 verr << " +) support set check..." << flush; 00542 Support_point_iterator support_point_iter; 00543 for ( support_point_iter = support_points_begin(); 00544 support_point_iter != support_points_end(); 00545 ++support_point_iter) 00546 if ( ! has_on_boundary( *support_point_iter)) 00547 return( CGAL::_optimisation_is_valid_fail( verr, 00548 "ellipse does not have all \ 00549 support points on the boundary")); 00550 verr << "passed." << endl; 00551 00552 verr << " object is valid!" << endl; 00553 return( true); 00554 } 00555 00556 // Miscellaneous 00557 // ------------- 00558 inline 00559 const Traits& 00560 traits( ) const 00561 { 00562 return( tco); 00563 } 00564 }; 00565 00566 // Function declarations 00567 // ===================== 00568 // I/O 00569 // --- 00570 template < class Traits_ > 00571 std::ostream& 00572 operator << ( std::ostream& os, const Min_ellipse_2<Traits_>& me); 00573 00574 template < class Traits_ > 00575 std::istream& 00576 operator >> ( std::istream& is, Min_ellipse_2<Traits_>& me); 00577 00578 CGAL_END_NAMESPACE 00579 00580 #include <CGAL/Min_ellipse_2/Min_ellipse_2_impl.h> 00581 00582 #endif // CGAL_MIN_ELLIPSE_2_H 00583 00584 // ===== EOF ==================================================================
1.7.6.1
