// Copyright (c) 2006 Fernando Luis Cacciola Carballal. All rights reserved. // // This file is part of CGAL (www.cgal.org). // You can redistribute it and/or modify it under the terms of the GNU // General Public License as published by the Free Software Foundation, // either version 3 of the License, or (at your option) any later version. // // Licensees holding a valid commercial license may use this file in // accordance with the commercial license agreement provided with the software. // // This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE // WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. // // $URL$ // $Id$ // // Author(s) : Fernando Cacciola // #ifndef CGAL_STRAIGHT_SKELETON_PREDICATES_FTC2_H #define CGAL_STRAIGHT_SKELETON_PREDICATES_FTC2_H 1 #include #include #include namespace CGAL { namespace CGAL_SS_i { // Just like the uncertified collinear() returns true IFF r lies in the line p->q // NOTE: r might be in the ray from p or q containing q or p, that is, there is no ordering implied, just that // the three points are along the same line, in any order. template inline Uncertain certified_collinearC2( Point_2 const& p , Point_2 const& q , Point_2 const& r ) { return CGAL_NTS certified_is_equal( ( q.x() - p.x() ) * ( r.y() - p.y() ) , ( r.x() - p.x() ) * ( q.y() - p.y() ) ); } // Just like the uncertified collinear_are_ordered_along_lineC2() returns true IFF, given p,q,r along the same line, // q is in the closed segment [p,r]. template inline Uncertain certified_collinear_are_ordered_along_lineC2( Point_2 const& p , Point_2 const& q , Point_2 const& r ) { if ( CGAL_NTS certainly(p.x() < q.x()) ) return !(r.x() < q.x()); if ( CGAL_NTS certainly(q.x() < p.x()) ) return !(q.x() < r.x()); if ( CGAL_NTS certainly(p.y() < q.y()) ) return !(r.y() < q.y()); if ( CGAL_NTS certainly(q.y() < p.y()) ) return !(q.y() < r.y()); if ( CGAL_NTS certainly(p.x() == q.x()) && CGAL_NTS certainly(p.y() == q.y()) ) return true; return Uncertain::indeterminate(); } // Returns true IFF segments e0,e1 share the same supporting line template Uncertain are_edges_collinearC2( Segment_2 const& e0, Segment_2 const& e1 ) { return certified_collinearC2(e0.source(),e0.target(),e1.source()) & certified_collinearC2(e0.source(),e0.target(),e1.target()) ; } // Returns true IFF the supporting lines for segments e0,e1 are parallel (or the same) template inline Uncertain are_edges_parallelC2( Segment_2 const& e0, Segment_2 const& e1 ) { Uncertain s = certified_sign_of_determinant2x2(e0.target().x() - e0.source().x() ,e0.target().y() - e0.source().y() ,e1.target().x() - e1.source().x() ,e1.target().y() - e1.source().y() ) ; return ( s == Uncertain(ZERO) ) ; } // Returns true IFF the parallel segments are equally oriented. // Precondition: the segments must be parallel. // the three points are along the same line, in any order. template inline Uncertain are_parallel_edges_equally_orientedC2( Segment_2 const& e0, Segment_2 const& e1 ) { return CGAL_NTS certified_sign( (e0.target() - e0.source()) * (e1.target() - e1.source()) ) == POSITIVE; } // Returns true IFF segments e0,e1 share the same supporting line but do not overlap except at the vetices, and have the same orientation. // NOTE: If e1 goes back over e0 (a degenerate antenna or alley) this returns false. template Uncertain are_edges_orderly_collinearC2( Segment_2 const& e0, Segment_2 const& e1 ) { return are_edges_collinearC2(e0,e1) & are_parallel_edges_equally_orientedC2(e0,e1); } template inline Uncertain certified_side_of_oriented_lineC2(const FT &a, const FT &b, const FT &c, const FT &x, const FT &y) { return CGAL_NTS certified_sign(a*x+b*y+c); } // // Constructs a Trisegment_2 which stores 3 edges (segments) such that // if two of them are collinear, they are put first, as e0, e1. // Stores also the number of collinear edges. which should be 0 or 2. // // If the collinearity test is indeterminate for any pair of edges the // resulting sorted trisegment is itself indeterminate // (encoded as a collinear count of -1) // template Uncertain certified_trisegment_collinearity ( Segment_2 const& e0 , Segment_2 const& e1 , Segment_2 const& e2 ) { Uncertain is_01 = are_edges_orderly_collinearC2(e0,e1); if ( is_certain(is_01) ) { Uncertain is_02 = are_edges_orderly_collinearC2(e0,e2); if ( is_certain(is_02) ) { Uncertain is_12 = are_edges_orderly_collinearC2(e1,e2); if ( is_certain(is_12) ) { if ( CGAL_NTS logical_and(is_01 , !is_02 , !is_12 ) ) return TRISEGMENT_COLLINEARITY_01; else if ( CGAL_NTS logical_and(is_02 , !is_01 , !is_12 ) ) return TRISEGMENT_COLLINEARITY_02; else if ( CGAL_NTS logical_and(is_12 , !is_01 , !is_02 ) ) return TRISEGMENT_COLLINEARITY_12; else if ( CGAL_NTS logical_and(!is_01 , !is_02, !is_12 ) ) return TRISEGMENT_COLLINEARITY_NONE; else return TRISEGMENT_COLLINEARITY_ALL; } } } return Uncertain::indeterminate(); } // Given 3 oriented straight line segments: e0, e1, e2 // returns true if there exist some positive offset distance 't' for which the // leftward-offsets of their supporting lines intersect at a single point. // // NOTE: This function can handle the case of collinear and/or parallel segments. // // If two segments are collinear but equally oriented (that is, they share a degenerate vertex) the event exists and // is well defined, In that case, the degenerate vertex can be even a contour vertex or a skeleton node. If it is a skeleton // node, it is properly defined by the trisegment tree that corresponds to the node. // A trisegment tree stores not only the "current event" trisegment but also the trisegments for the left/right seed vertices, // recursivey in case the seed vertices are skeleton nodes as well. // Those seeds are used to determine the actual position of the degenerate vertex in case of collinear edges (since that point is // not given by the collinear edges alone) // template Uncertain exist_offset_lines_isec2 ( intrusive_ptr< Trisegment_2 > const& tri, optional const& aMaxTime ) { typedef Rational Rational ; typedef optional Optional_rational ; typedef Quotient Quotient ; Uncertain rResult = Uncertain::indeterminate(); if ( tri->collinearity() != TRISEGMENT_COLLINEARITY_ALL ) { CGAL_STSKEL_TRAITS_TRACE( ( tri->collinearity() == TRISEGMENT_COLLINEARITY_NONE ? " normal edges" : " collinear edges" ) ) ; Optional_rational t = compute_offset_lines_isec_timeC2(tri) ; if ( t ) { Uncertain d_is_zero = CGAL_NTS certified_is_zero(t->d()) ; if ( is_certain(d_is_zero) ) { if ( !d_is_zero ) { Quotient tq = t->to_quotient() ; rResult = CGAL_NTS certified_is_positive(tq) ; if ( aMaxTime && CGAL_NTS certainly(rResult) ) rResult = CGAL_NTS certified_is_smaller_or_equal(tq,Quotient(*aMaxTime)); CGAL_STSKEL_TRAITS_TRACE("\nEvent time: " << *t << ". Event " << ( rResult ? "exist." : "doesn't exist." ) ) ; } else { CGAL_STSKEL_TRAITS_TRACE("\nDenominator exactly zero, Event doesn't exist." ) ; rResult = false; } } else{ CGAL_STSKEL_TRAITS_TRACE("\nDenominator is probably zero (but not exactly), event existance is indeterminate." ) ; } } else{ CGAL_STSKEL_TRAITS_TRACE("\nEvent time overflowed, event existance is indeterminate." ) ; } } else { CGAL_STSKEL_TRAITS_TRACE("\nAll the edges are collinear. Event doesn't exist." ) ; rResult = false; } return rResult ; } // Given 2 triples of oriented straight line segments: (m0,m1,m2) and (n0,n1,n2), such that // for each triple there exists distances 'mt' and 'nt' for which the offsets lines (at mt and nt resp.), // (m0',m1',m2') and (n0',n1',n2') intersect each in a single point; returns the relative order of mt w.r.t nt. // That is, indicates which offset triple intersects first (closer to the source lines) // PRECONDITION: There exist distances mt and nt for which each offset triple intersect at a single point. template Uncertain compare_offset_lines_isec_timesC2 ( intrusive_ptr< Trisegment_2 > const& m , intrusive_ptr< Trisegment_2 > const& n ) { typedef typename K::FT FT ; typedef Rational Rational ; typedef Quotient Quotient ; typedef optional Optional_rational ; Uncertain rResult = Uncertain::indeterminate(); Optional_rational mt_ = compute_offset_lines_isec_timeC2(m); Optional_rational nt_ = compute_offset_lines_isec_timeC2(n); if ( mt_ && nt_ ) { Quotient mt = mt_->to_quotient(); Quotient nt = nt_->to_quotient(); if ( CGAL_NTS certified_is_positive(mt) && CGAL_NTS certified_is_positive(nt) ) rResult = CGAL_NTS certified_compare(mt,nt); } return rResult ; } // Returns true if the point aP is on the positive side of the line supporting the edge // template Uncertain is_edge_facing_pointC2 ( optional< Point_2 > const& aP, Segment_2 const& aEdge ) { typedef typename K::FT FT ; Uncertain rResult = Uncertain::indeterminate(); if ( aP ) { FT a,b,c ; line_from_pointsC2(aEdge.source().x(),aEdge.source().y(),aEdge.target().x(),aEdge.target().y(),a,b,c); rResult = certified_side_of_oriented_lineC2(a,b,c,aP->x(),aP->y()) == make_uncertain(POSITIVE) ; } return rResult ; } // Given a triple of oriented straight line segments: (e0,e1,e2) such that their offsets // at some distance intersects in a point (x,y), returns true if (x,y) is on the positive side of the line supporting aEdge // template inline Uncertain is_edge_facing_offset_lines_isecC2 ( intrusive_ptr< Trisegment_2 > const& tri, Segment_2 const& aEdge ) { return is_edge_facing_pointC2(construct_offset_lines_isecC2(tri),aEdge); } // Given an event trisegment and two oriented straight line segments e0 and e1, returns the oriented side of the event point // w.r.t the (positive) bisector [e0,e1]. // // The (positive) bisector [e0,e1] is a ray starting at the vertex (e0,e1) (called "v01") // // If e0,e1 are consecutive in the input polygon, v01 = e0.target() = e1.source(). // If they are not consecutive in the input polygon they must had become consecutive at some known previous event. In this // case, the point of the "v01_event" trisegment intersection determines v01 which is to the position of the very first // vertex shared between e0,e1 (at the time they first become consecutive). // // A point *exactly on* the bisector is an offset vertex (e0*,e1*) (that is, belongs to both e0* and e1*). // A point to the positive side of the bisector belongs to e0* but not e1* // A point to the negative side of the bisector belongs to e1* but not e0* // // If e0,e1 intersect in a single point the bisector is an angular bisector. // // One of e0 or e1 is considered the primary edge. // // If e0,e1 are parallel a line perpendicular to the primary edge passing through "v01" is used "as bisector". // // If e0,e1 are collinear then this perpendicular line is a perpendicular bisector of the two segments. // // If e0,e1 are parallel but not collinear then the actual bisector is an equidistant line parallel to e0 and e1. // e0* and e1* overlap and are known to be connected sharing a known vertex v01, which is somewhere along the parallel // line which is the bisector of e0 and e1. // Given a line perpendicular to e0 through v01, a point to its positive side belongs to e0* while a point to its negative side does not. // Given a line perpendicular to e1 through v01, a point to its negative side belongs to e1* while a point to its positive side does not. // // This predicate is used to determine the validity of a split or edge event. // // A split event is the coallision of a reflex wavefront and some opposite offset egde. Unless the three segments // don't actually collide (there is no event), the split point is along the supporting line of the offset edge. // Testing its validity amounts to determining if the split point is inside the closed offset segment instead of // the two open rays before and after the offset segment endpoints. // The offset edge is bounded by its previous and next adjacent edges at the time of the event. Thus, the bisectors // of this edge and its previous/next adjacent edges (at the time of the event) detemine the offset vertices that // bound the opposite edge. // If the opposite edge is 'e' and its previous/next edges are "preve"/"nexte" then the split point is inside the offset // egde if it is NOT to the positive side of [preve,e] *and* NOT to the negative side o [e,nexte]. // (so this predicate answer half the question, at one and other side independenty). // If the split point is exacty over any of this bisectors then the split point ocurres exactly and one (or both) endpoints // of the opposite edge (so it is a pseudo-split event since the opposite edge is not itself split in two halfeves) // When this predicate is called to test (prev,e), e is the primary edge but since it is pass as e1, primary_is_0=false. // This causes the case of parallel but not collinear edges to return positive when the split point is before the source point of e* // (a positive result means invalid split). // Likewise, primary_is_0 must be true when testing (e,nexte) to return negative if the split point is past the target endpoint of e*. // (in the other cases there is no need to discrminate which is 'e' in the call since the edjes do not overlap). // // An edge event is a coallision of three *consecutive* edges, say, e1,e2 and e3. // The coallision causes e2 (the edge in the middle) to collapse and e1,e3 to become consecutive and form a new vertex. // In all cases there is an edge before e1, say e0, and after e3, say e4. // Testing for the validity of an edge event amounts to determine that (e1,e3) (the new vertex) is not before (e0,e1) nor // past (e3,e4). // Thus, and edge event is valid if the new vertex NOT to the positive side of [e0,e1] *and* NOT to the negative side o [e3,e4]. // // PRECONDITIONS: // There exist a single point 'p' corresponding to the event as given by the trisegment // e0 and e1 are known to be consectuve at the time of the event (even if they are not consecutive in the input polygon) // If e0 and e1 are not consecutive in the input, v01_event is the event that defined they very first offset vertex. // If e0 and e1 are consecutive, v01_event is null. // template Uncertain oriented_side_of_event_point_wrt_bisectorC2 ( intrusive_ptr< Trisegment_2 > const& event , Segment_2 const& e0 , Segment_2 const& e1 , intrusive_ptr< Trisegment_2 > const& v01_event // can be null , bool primary_is_0 ) { typedef typename K::FT FT ; typedef Point_2 Point_2 ; typedef Line_2 Line_2 ; Uncertain rResult = Uncertain::indeterminate(); try { Point_2 p = validate(construct_offset_lines_isecC2(event)); Line_2 l0 = validate(compute_normalized_line_ceoffC2(e0)) ; Line_2 l1 = validate(compute_normalized_line_ceoffC2(e1)) ; CGAL_STSKEL_TRAITS_TRACE("Getting oriented side of point " << p2str(p) << " w.r.t bisector [" << s2str(e0) << ( primary_is_0 ? "*" : "" ) << "," << s2str(e1) << ( primary_is_0 ? "" : "*" ) << "]" ) ; // Degenerate bisector? if ( certainly( are_edges_parallelC2(e0,e1) ) ) { CGAL_STSKEL_TRAITS_TRACE("Bisector is not angular." ) ; // b01 is degenerate so we don't have an *angular bisector* but a *perpendicular* bisector. // We need to compute the actual bisector line. CGAL_assertion( v01_event || ( !v01_event && e0.target() == e1.source() ) ) ; Point_2 v01 = v01_event ? validate( construct_offset_lines_isecC2(v01_event) ) : e1.source() ; CGAL_STSKEL_TRAITS_TRACE("v01=" << p2str(v01) << ( v01_event ? " (from skelton node)" : "" ) ) ; // (a,b,c) is a line perpedincular to the primary edge through v01. // If e0 and e1 are collinear this line is the actual perpendicular bisector. // // If e0 and e1 are parallel but not collinear (then neccesarrily facing each other) this line // is NOT the bisector, but the serves to determine the side of the point (projected along the primary ege) w.r.t vertex v01. FT a, b, c ; perpendicular_through_pointC2( primary_is_0 ? l0.a() : l1.a() , primary_is_0 ? l0.b() : l1.b() , v01.x(), v01.y() , a, b, c ); rResult = certified_side_of_oriented_lineC2(a,b,c,p.x(),p.y()); CGAL_STSKEL_TRAITS_TRACE("Point is at " << rResult << " side of degenerate bisector through v01 " << p2str(v01)) ; } else // Valid (non-degenerate) angular bisector { // Scale distance from to the lines. FT sd_p_l0 = validate(l0.a() * p.x() + l0.b() * p.y() + l0.c()) ; FT sd_p_l1 = validate(l1.a() * p.x() + l1.b() * p.y() + l1.c()) ; CGAL_STSKEL_TRAITS_TRACE("sd_p_l1=" << n2str(sd_p_l1) ) ; CGAL_STSKEL_TRAITS_TRACE("sd_p_l0=" << n2str(sd_p_l0) ) ; Uncertain equal = CGAL_NTS certified_is_equal(sd_p_l0,sd_p_l1) ; if ( is_certain(equal) ) { if ( equal ) { CGAL_STSKEL_TRAITS_TRACE("Point is exactly at bisector"); rResult = ON_ORIENTED_BOUNDARY; } else { Uncertain smaller = CGAL_NTS certified_is_smaller( validate(l0.a()*l1.b()), validate(l1.a()*l0.b()) ) ; if ( is_certain(smaller) ) { // Reflex bisector? if ( smaller ) { rResult = CGAL_NTS certified_is_smaller(sd_p_l0,sd_p_l1) ? ON_NEGATIVE_SIDE : ON_POSITIVE_SIDE ; CGAL_STSKEL_TRAITS_TRACE("\nEvent point is at " << rResult << " side of reflex bisector" ) ; } else { rResult = CGAL_NTS certified_is_larger (sd_p_l0,sd_p_l1) ? ON_NEGATIVE_SIDE : ON_POSITIVE_SIDE ; CGAL_STSKEL_TRAITS_TRACE("\nEvent point is at " << rResult << " side of convex bisector" ) ; } } } } } } catch( std::overflow_error const& ) { CGAL_STSKEL_TRAITS_TRACE("Unable to compute value due to overflow."); } catch( CGAL::Uncertain_conversion_exception const& ) { CGAL_STSKEL_TRAITS_TRACE("Indeterminate boolean expression."); } return rResult ; } // Given 2 triples of oriented straight line segments (l0,l1,l2) and (r0,r1,r2), such that // the offsets at time 'tl' for triple 'l' intersects in a point (lx,ly) and // the offsets at time 'tr' for triple 'r' intersects in a point (rx,ry) // returns true if "tl==tr" and "(lx,ly)==(rx,ry)" // PRECONDITIONS: // There exist single points at which the offset lines for 'l' and 'r' at 'tl', 'tr' intersect. // template Uncertain are_events_simultaneousC2 ( intrusive_ptr< Trisegment_2 > const& l, intrusive_ptr< Trisegment_2 > const& r ) { typedef typename K::FT FT ; typedef Point_2 Point_2 ; typedef Rational Rational ; typedef Quotient Quotient ; typedef optional Optional_rational ; typedef optional Optional_point_2 ; Uncertain rResult = Uncertain::indeterminate(); Optional_rational lt_ = compute_offset_lines_isec_timeC2(l); Optional_rational rt_ = compute_offset_lines_isec_timeC2(r); if ( lt_ && rt_ ) { Quotient lt = lt_->to_quotient(); Quotient rt = rt_->to_quotient(); if ( CGAL_NTS certified_is_positive(lt) && CGAL_NTS certified_is_positive(rt) ) { Uncertain equal_times = CGAL_NTS certified_is_equal(lt,rt); if ( is_certain(equal_times) ) { if ( equal_times ) { Optional_point_2 li = construct_offset_lines_isecC2(l); Optional_point_2 ri = construct_offset_lines_isecC2(r); if ( li && ri ) rResult = CGAL_NTS logical_and( CGAL_NTS certified_is_equal(li->x(),ri->x()) , CGAL_NTS certified_is_equal(li->y(),ri->y()) ) ; } else rResult = false; } } } return rResult; } } // namespace CGAL_SS_i } // end namespace CGAL #endif // CGAL_STRAIGHT_SKELETON_PREDICATES_FTC2_H //