|
BWAPI
|
00001 // Copyright (c) 2005-2008 Fernando Luis Cacciola Carballal. All rights reserved. 00002 // 00003 // This file is part of CGAL (www.cgal.org); you may redistribute it under 00004 // the terms of the Q Public License version 1.0. 00005 // See the file LICENSE.QPL distributed with CGAL. 00006 // 00007 // Licensees holding a valid commercial license may use this file in 00008 // accordance with the commercial license agreement provided with the software. 00009 // 00010 // This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE 00011 // WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. 00012 // 00013 // $URL: svn+ssh://scm.gforge.inria.fr/svn/cgal/branches/CGAL-3.5-branch/Straight_skeleton_2/include/CGAL/Straight_skeleton_builder_traits_2.h $ 00014 // $Id: Straight_skeleton_builder_traits_2.h 46477 2008-10-25 13:48:37Z afabri $ 00015 // 00016 // Author(s) : Fernando Cacciola <fernando_cacciola@ciudad.com.ar> 00017 // 00018 #ifndef CGAL_STRAIGHT_SKELETON_BUILDER_TRAITS_2_H 00019 #define CGAL_STRAIGHT_SKELETON_BUILDER_TRAITS_2_H 1 00020 00021 #include <CGAL/Filtered_construction.h> 00022 #include <CGAL/Straight_skeleton_2/Straight_skeleton_aux.h> 00023 #include <CGAL/Straight_skeleton_2/Straight_skeleton_builder_traits_2_aux.h> 00024 #include <CGAL/predicates/Straight_skeleton_pred_ftC2.h> 00025 #include <CGAL/constructions/Straight_skeleton_cons_ftC2.h> 00026 00027 CGAL_BEGIN_NAMESPACE 00028 00029 namespace CGAL_SS_i { 00030 00031 00032 template<class K> 00033 struct Construct_ss_trisegment_2 : Functor_base_2<K> 00034 { 00035 typedef Functor_base_2<K> Base ; 00036 00037 typedef typename Base::Segment_2 Segment_2 ; 00038 typedef typename Base::Trisegment_2 Trisegment_2 ; 00039 typedef typename Base::Trisegment_2_ptr Trisegment_2_ptr ; 00040 00041 typedef Trisegment_2_ptr result_type ; 00042 00043 00044 result_type operator() () const { return cgal_make_optional( Trisegment_2::null() ) ; } 00045 00046 result_type operator() ( Segment_2 const& aS0, Segment_2 const& aS1, Segment_2 const& aS2 ) const 00047 { 00048 return construct_trisegment(aS0,aS1,aS2); 00049 } 00050 }; 00051 00052 template<class K> 00053 struct Do_ss_event_exist_2 : Functor_base_2<K> 00054 { 00055 typedef Functor_base_2<K> Base ; 00056 00057 typedef typename Base::FT FT ; 00058 typedef typename Base::Trisegment_2_ptr Trisegment_2_ptr ; 00059 00060 typedef Uncertain<bool> result_type ; 00061 00062 Uncertain<bool> operator() ( Trisegment_2_ptr const& aTrisegment, boost::optional<FT> aMaxTime ) const 00063 { 00064 Uncertain<bool> rResult = exist_offset_lines_isec2(aTrisegment,aMaxTime) ; 00065 00066 CGAL_STSKEL_ASSERT_PREDICATE_RESULT(rResult,K,"Exist_event",aTrisegment); 00067 00068 return rResult ; 00069 } 00070 }; 00071 00072 template<class K> 00073 struct Is_edge_facing_ss_node_2 : Functor_base_2<K> 00074 { 00075 typedef Functor_base_2<K> Base ; 00076 00077 typedef typename Base::Point_2 Point_2 ; 00078 typedef typename Base::Segment_2 Segment_2 ; 00079 typedef typename Base::Trisegment_2_ptr Trisegment_2_ptr ; 00080 00081 typedef Uncertain<bool> result_type ; 00082 00083 Uncertain<bool> operator() ( Point_2 const& aContourNode, Segment_2 const& aEdge ) const 00084 { 00085 return is_edge_facing_pointC2(cgal_make_optional(aContourNode),aEdge) ; 00086 } 00087 00088 Uncertain<bool> operator() ( Trisegment_2_ptr const& aSkeletonNode, Segment_2 const& aEdge ) const 00089 { 00090 return is_edge_facing_offset_lines_isecC2(aSkeletonNode,aEdge) ; 00091 } 00092 }; 00093 00094 template<class K> 00095 struct Compare_ss_event_times_2 : Functor_base_2<K> 00096 { 00097 typedef Functor_base_2<K> Base ; 00098 00099 typedef typename Base::Trisegment_2_ptr Trisegment_2_ptr ; 00100 00101 typedef Uncertain<Comparison_result> result_type ; 00102 00103 Uncertain<Comparison_result> operator() ( Trisegment_2_ptr const& aL, Trisegment_2_ptr const& aR ) const 00104 { 00105 Uncertain<Comparison_result> rResult = compare_offset_lines_isec_timesC2(aL,aR) ; 00106 00107 CGAL_STSKEL_ASSERT_PREDICATE_RESULT(rResult,K,"Compare_event_times","L: " << aL << "\nR:" << aR ); 00108 00109 return rResult ; 00110 } 00111 }; 00112 00113 template<class K> 00114 struct Oriented_side_of_event_point_wrt_bisector_2 : Functor_base_2<K> 00115 { 00116 typedef Functor_base_2<K> Base ; 00117 00118 typedef typename Base::Segment_2 Segment_2 ; 00119 typedef typename Base::Trisegment_2_ptr Trisegment_2_ptr ; 00120 typedef typename Base::Point_2 Point_2 ; 00121 00122 typedef Uncertain<Oriented_side> result_type ; 00123 00124 Uncertain<Oriented_side> operator() ( Trisegment_2_ptr const& aEvent 00125 , Segment_2 const& aE0 00126 , Segment_2 const& aE1 00127 , Trisegment_2_ptr const& aE01Event 00128 , bool aE0isPrimary 00129 ) const 00130 { 00131 Uncertain<Oriented_side> rResult = oriented_side_of_event_point_wrt_bisectorC2(aEvent,aE0,aE1,aE01Event,aE0isPrimary) ; 00132 00133 CGAL_STSKEL_ASSERT_PREDICATE_RESULT(rResult,K,"Oriented_side_of_event_point_wrt_bisector_2","Event=" << aEvent << " E0=" << aE0 << " E1=" << aE1 ); 00134 00135 return rResult ; 00136 } 00137 }; 00138 00139 00140 template<class K> 00141 struct Are_ss_events_simultaneous_2 : Functor_base_2<K> 00142 { 00143 typedef Functor_base_2<K> Base ; 00144 00145 typedef typename Base::Trisegment_2_ptr Trisegment_2_ptr ; 00146 00147 typedef Uncertain<bool> result_type ; 00148 00149 Uncertain<bool> operator() ( Trisegment_2_ptr const& aA, Trisegment_2_ptr const& aB ) const 00150 { 00151 Uncertain<bool> rResult = are_events_simultaneousC2(aA,aB); 00152 00153 CGAL_STSKEL_ASSERT_PREDICATE_RESULT(rResult,K,"Are_events_simultaneous","A=" << aA << "\nB=" << aB); 00154 00155 return rResult ; 00156 } 00157 }; 00158 00159 template<class K> 00160 struct Are_ss_edges_collinear_2 : Functor_base_2<K> 00161 { 00162 typedef Functor_base_2<K> Base ; 00163 00164 typedef typename Base::Segment_2 Segment_2 ; 00165 00166 typedef Uncertain<bool> result_type ; 00167 00168 Uncertain<bool> operator() ( Segment_2 const& aA, Segment_2 const& aB ) const 00169 { 00170 Uncertain<bool> rResult = are_edges_collinearC2(aA,aB); 00171 00172 CGAL_STSKEL_ASSERT_PREDICATE_RESULT(rResult,K,"Are_ss_edges_collinear","A=" << aA << "\nB=" << aB); 00173 00174 return rResult ; 00175 } 00176 }; 00177 00178 template<class K> 00179 struct Are_ss_edges_parallel_2 : Functor_base_2<K> 00180 { 00181 typedef Functor_base_2<K> Base ; 00182 00183 typedef typename Base::Segment_2 Segment_2 ; 00184 00185 typedef Uncertain<bool> result_type ; 00186 00187 Uncertain<bool> operator() ( Segment_2 const& aA, Segment_2 const& aB ) const 00188 { 00189 Uncertain<bool> rResult = are_edges_parallelC2(aA,aB); 00190 00191 CGAL_STSKEL_ASSERT_PREDICATE_RESULT(rResult,K,"Are_ss_edges_parallel","A=" << aA << "\nB=" << aB); 00192 00193 return rResult ; 00194 } 00195 }; 00196 00197 00198 template<class K> 00199 struct Construct_ss_event_time_and_point_2 : Functor_base_2<K> 00200 { 00201 typedef Functor_base_2<K> Base ; 00202 00203 typedef typename Base::FT FT ; 00204 typedef typename Base::Point_2 Point_2 ; 00205 typedef typename Base::Segment_2 Segment_2 ; 00206 typedef typename Base::Trisegment_2_ptr Trisegment_2_ptr ; 00207 00208 typedef boost::tuple<FT,Point_2> rtype ; 00209 00210 typedef boost::optional<rtype> result_type ; 00211 00212 00213 result_type operator() ( Trisegment_2_ptr const& aTrisegment ) const 00214 { 00215 bool lOK = false ; 00216 00217 FT t(0) ; 00218 Point_2 i = ORIGIN ; 00219 00220 optional< Rational<FT> > ot = compute_offset_lines_isec_timeC2(aTrisegment); 00221 00222 if ( !!ot && certainly( CGAL_NTS certified_is_not_zero(ot->d()) ) ) 00223 { 00224 t = ot->n() / ot->d(); 00225 00226 optional<Point_2> oi = construct_offset_lines_isecC2(aTrisegment); 00227 if ( oi ) 00228 { 00229 i = *oi ; 00230 CGAL_stskel_intrinsic_test_assertion(!is_point_calculation_clearly_wrong(t,i,aTrisegment)); 00231 lOK = true ; 00232 } 00233 } 00234 00235 CGAL_STSKEL_ASSERT_CONSTRUCTION_RESULT(lOK,K,"Construct_ss_event_time_and_point_2",aTrisegment); 00236 00237 return cgal_make_optional(lOK,boost::make_tuple(t,i)) ; 00238 } 00239 00240 bool is_point_calculation_clearly_wrong( FT const& t, Point_2 const& p, Trisegment_2_ptr const& aTrisegment ) const 00241 { 00242 bool rR = false ; 00243 00244 if ( is_possibly_inexact_time_clearly_not_zero(t) ) 00245 { 00246 Segment_2 const& e0 = aTrisegment->e0() ; 00247 Segment_2 const& e1 = aTrisegment->e1() ; 00248 Segment_2 const& e2 = aTrisegment->e2() ; 00249 00250 Point_2 const& e0s = e0.source(); 00251 Point_2 const& e0t = e0.target(); 00252 00253 Point_2 const& e1s = e1.source(); 00254 Point_2 const& e1t = e1.target(); 00255 00256 Point_2 const& e2s = e2.source(); 00257 Point_2 const& e2t = e2.target(); 00258 00259 FT const very_short(0.1); 00260 FT const very_short_squared = CGAL_NTS square(very_short); 00261 00262 FT l0 = squared_distance(e0s,e0t) ; 00263 FT l1 = squared_distance(e1s,e1t) ; 00264 FT l2 = squared_distance(e2s,e2t) ; 00265 00266 bool e0_is_not_very_short = l0 > very_short_squared ; 00267 bool e1_is_not_very_short = l1 > very_short_squared ; 00268 bool e2_is_not_very_short = l2 > very_short_squared ; 00269 00270 FT d0 = squared_distance_from_point_to_lineC2(p.x(),p.y(),e0s.x(),e0s.y(),e0t.x(),e0t.y()).to_nt(); 00271 FT d1 = squared_distance_from_point_to_lineC2(p.x(),p.y(),e1s.x(),e1s.y(),e1t.x(),e1t.y()).to_nt(); 00272 FT d2 = squared_distance_from_point_to_lineC2(p.x(),p.y(),e2s.x(),e2s.y(),e2t.x(),e2t.y()).to_nt(); 00273 00274 FT tt = CGAL_NTS square(t); 00275 00276 bool e0_is_clearly_wrong = e0_is_not_very_short && is_possibly_inexact_distance_clearly_not_equal_to(d0,tt) ; 00277 bool e1_is_clearly_wrong = e1_is_not_very_short && is_possibly_inexact_distance_clearly_not_equal_to(d1,tt) ; 00278 bool e2_is_clearly_wrong = e2_is_not_very_short && is_possibly_inexact_distance_clearly_not_equal_to(d2,tt) ; 00279 00280 rR = e0_is_clearly_wrong || e1_is_clearly_wrong || e2_is_clearly_wrong ; 00281 00282 CGAL_stskel_intrinsic_test_trace_if(rR 00283 , "\nSkeleton node point calculation is clearly wrong:" 00284 << "\ntime=" << t << " p=" << p2str(p) << " e0=" << s2str(e0) << " e1=" << s2str(e1) << " e2=" << s2str(e2) 00285 << "\nl0=" << inexact_sqrt(l0) << " l1=" << inexact_sqrt(l1) << " l2=" << inexact_sqrt(l2) 00286 << "\nd0=" << d0 << " d1=" << d1 << " d2=" << d2 << " tt=" << tt 00287 ) ; 00288 } 00289 00290 return rR ; 00291 } 00292 }; 00293 00294 } // namespace CGAL_SS_i 00295 00296 template<class K> 00297 struct Straight_skeleton_builder_traits_2_functors 00298 { 00299 typedef CGAL_SS_i::Do_ss_event_exist_2 <K> Do_ss_event_exist_2 ; 00300 typedef CGAL_SS_i::Compare_ss_event_times_2 <K> Compare_ss_event_times_2 ; 00301 typedef CGAL_SS_i::Is_edge_facing_ss_node_2 <K> Is_edge_facing_ss_node_2 ; 00302 typedef CGAL_SS_i::Oriented_side_of_event_point_wrt_bisector_2<K> Oriented_side_of_event_point_wrt_bisector_2 ; 00303 typedef CGAL_SS_i::Are_ss_events_simultaneous_2 <K> Are_ss_events_simultaneous_2 ; 00304 typedef CGAL_SS_i::Are_ss_edges_parallel_2 <K> Are_ss_edges_parallel_2 ; 00305 typedef CGAL_SS_i::Are_ss_edges_collinear_2 <K> Are_ss_edges_collinear_2 ; 00306 typedef CGAL_SS_i::Construct_ss_event_time_and_point_2 <K> Construct_ss_event_time_and_point_2 ; 00307 typedef CGAL_SS_i::Construct_ss_trisegment_2 <K> Construct_ss_trisegment_2 ; 00308 } ; 00309 00310 template<class K> 00311 struct Straight_skeleton_builder_traits_2_base 00312 { 00313 typedef K Kernel ; 00314 00315 typedef typename K::FT FT ; 00316 typedef typename K::Point_2 Point_2 ; 00317 typedef typename K::Vector_2 Vector_2 ; 00318 typedef typename K::Direction_2 Direction_2 ; 00319 typedef typename K::Segment_2 Segment_2 ; 00320 00321 typedef CGAL_SS_i::Trisegment_2<K> Trisegment_2 ; 00322 00323 typedef typename Trisegment_2::Self_ptr Trisegment_2_ptr ; 00324 00325 template<class F> F get( F const* = 0 ) const { return F(); } 00326 00327 } ; 00328 00329 00330 template<class Is_filtered_kernel, class K> class Straight_skeleton_builder_traits_2_impl ; 00331 00332 template<class K> 00333 class Straight_skeleton_builder_traits_2_impl<Tag_false,K> : public Straight_skeleton_builder_traits_2_base<K> 00334 { 00335 typedef Straight_skeleton_builder_traits_2_functors<K> Unfiltering ; 00336 00337 public: 00338 00339 typedef Unfiltered_predicate_adaptor<typename Unfiltering::Do_ss_event_exist_2> 00340 Do_ss_event_exist_2 ; 00341 00342 typedef Unfiltered_predicate_adaptor<typename Unfiltering::Compare_ss_event_times_2> 00343 Compare_ss_event_times_2 ; 00344 00345 typedef Unfiltered_predicate_adaptor<typename Unfiltering::Is_edge_facing_ss_node_2> 00346 Is_edge_facing_ss_node_2 ; 00347 00348 typedef Unfiltered_predicate_adaptor<typename Unfiltering::Oriented_side_of_event_point_wrt_bisector_2> 00349 Oriented_side_of_event_point_wrt_bisector_2 ; 00350 00351 typedef Unfiltered_predicate_adaptor<typename Unfiltering::Are_ss_events_simultaneous_2> 00352 Are_ss_events_simultaneous_2 ; 00353 00354 typedef Unfiltered_predicate_adaptor<typename Unfiltering::Are_ss_edges_parallel_2> 00355 Are_ss_edges_parallel_2 ; 00356 00357 typedef Unfiltered_predicate_adaptor<typename Unfiltering::Are_ss_edges_collinear_2> 00358 Are_ss_edges_collinear_2 ; 00359 00360 typedef typename Unfiltering::Construct_ss_event_time_and_point_2 Construct_ss_event_time_and_point_2 ; 00361 typedef typename Unfiltering::Construct_ss_trisegment_2 Construct_ss_trisegment_2 ; 00362 } ; 00363 00364 template<class K> 00365 class Straight_skeleton_builder_traits_2_impl<Tag_true,K> : public Straight_skeleton_builder_traits_2_base<K> 00366 { 00367 typedef typename K::Exact_kernel EK ; 00368 typedef typename K::Approximate_kernel FK ; 00369 00370 typedef Straight_skeleton_builder_traits_2_functors<EK> Exact ; 00371 typedef Straight_skeleton_builder_traits_2_functors<FK> Filtering ; 00372 typedef Straight_skeleton_builder_traits_2_functors<K> Unfiltering ; 00373 00374 typedef Cartesian_converter<K,EK> BaseC2E; 00375 typedef Cartesian_converter<K,FK> BaseC2F; 00376 typedef Cartesian_converter<EK,K> BaseE2C; 00377 typedef Cartesian_converter<FK,K> BaseF2C; 00378 typedef Cartesian_converter<K,K> BaseC2C; 00379 00380 typedef CGAL_SS_i::SS_converter<BaseC2E> C2E ; 00381 typedef CGAL_SS_i::SS_converter<BaseC2F> C2F ; 00382 typedef CGAL_SS_i::SS_converter<BaseE2C> E2C ; 00383 typedef CGAL_SS_i::SS_converter<BaseF2C> F2C ; 00384 typedef CGAL_SS_i::SS_converter<BaseC2C> C2C ; 00385 00386 public: 00387 00388 typedef Filtered_predicate<typename Exact ::Do_ss_event_exist_2 00389 ,typename Filtering::Do_ss_event_exist_2 00390 , C2E 00391 , C2F 00392 > 00393 Do_ss_event_exist_2 ; 00394 00395 typedef Filtered_predicate< typename Exact ::Compare_ss_event_times_2 00396 , typename Filtering::Compare_ss_event_times_2 00397 , C2E 00398 , C2F 00399 > 00400 Compare_ss_event_times_2 ; 00401 00402 typedef Filtered_predicate< typename Exact ::Is_edge_facing_ss_node_2 00403 , typename Filtering::Is_edge_facing_ss_node_2 00404 , C2E 00405 , C2F 00406 > 00407 Is_edge_facing_ss_node_2 ; 00408 00409 typedef Filtered_predicate< typename Exact ::Oriented_side_of_event_point_wrt_bisector_2 00410 , typename Filtering::Oriented_side_of_event_point_wrt_bisector_2 00411 , C2E 00412 , C2F 00413 > 00414 Oriented_side_of_event_point_wrt_bisector_2 ; 00415 00416 typedef Filtered_predicate< typename Exact ::Are_ss_events_simultaneous_2 00417 , typename Filtering::Are_ss_events_simultaneous_2 00418 , C2E 00419 , C2F 00420 > 00421 Are_ss_events_simultaneous_2 ; 00422 00423 typedef Filtered_predicate< typename Exact ::Are_ss_edges_parallel_2 00424 , typename Filtering::Are_ss_edges_parallel_2 00425 , C2E 00426 , C2F 00427 > 00428 Are_ss_edges_parallel_2 ; 00429 00430 typedef Filtered_predicate< typename Exact ::Are_ss_edges_collinear_2 00431 , typename Filtering::Are_ss_edges_collinear_2 00432 , C2E 00433 , C2F 00434 > 00435 Are_ss_edges_collinear_2 ; 00436 00437 typedef CGAL_SS_i::Exceptionless_filtered_construction< typename Unfiltering::Construct_ss_event_time_and_point_2 00438 , typename Exact ::Construct_ss_event_time_and_point_2 00439 , typename Unfiltering::Construct_ss_event_time_and_point_2 00440 , C2E 00441 , C2C 00442 , E2C 00443 , C2C 00444 > 00445 Construct_ss_event_time_and_point_2 ; 00446 00447 typedef CGAL_SS_i::Exceptionless_filtered_construction< typename Unfiltering::Construct_ss_trisegment_2 00448 , typename Exact ::Construct_ss_trisegment_2 00449 , typename Unfiltering::Construct_ss_trisegment_2 00450 , C2E 00451 , C2C 00452 , E2C 00453 , C2C 00454 > 00455 Construct_ss_trisegment_2 ; 00456 } ; 00457 00458 template<class K> 00459 class Straight_skeleton_builder_traits_2 00460 : public Straight_skeleton_builder_traits_2_impl<typename CGAL_SS_i::Is_filtering_kernel<K>::type, K> 00461 { 00462 } ; 00463 00464 CGAL_STRAIGHT_SKELETON_CREATE_FUNCTOR_ADAPTER(Do_ss_event_exist_2); 00465 CGAL_STRAIGHT_SKELETON_CREATE_FUNCTOR_ADAPTER(Compare_ss_event_times_2); 00466 CGAL_STRAIGHT_SKELETON_CREATE_FUNCTOR_ADAPTER(Is_edge_facing_ss_node_2); 00467 CGAL_STRAIGHT_SKELETON_CREATE_FUNCTOR_ADAPTER(Oriented_side_of_event_point_wrt_bisector_2); 00468 CGAL_STRAIGHT_SKELETON_CREATE_FUNCTOR_ADAPTER(Are_ss_events_simultaneous_2); 00469 CGAL_STRAIGHT_SKELETON_CREATE_FUNCTOR_ADAPTER(Are_ss_edges_parallel_2); 00470 CGAL_STRAIGHT_SKELETON_CREATE_FUNCTOR_ADAPTER(Are_ss_edges_collinear_2); 00471 CGAL_STRAIGHT_SKELETON_CREATE_FUNCTOR_ADAPTER(Construct_ss_event_time_and_point_2); 00472 CGAL_STRAIGHT_SKELETON_CREATE_FUNCTOR_ADAPTER(Construct_ss_trisegment_2); 00473 00474 CGAL_END_NAMESPACE 00475 00476 #endif // CGAL_STRAIGHT_SKELETON_BUILDER_TRAITS_2_H // 00477 // EOF //
1.7.6.1
