straight_skeleton_pred_ftc2.h

很多二维 三维几何计算算法 C++ 类库

// Copyright (c) 2006 Fernando Luis Cacciola Carballal. All rights reserved.
//
// This file is part of CGAL (www.cgal.org); you may redistribute it under
// the terms of the Q Public License version 1.0.
// See the file LICENSE.QPL distributed with CGAL.
//
// 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: svn+ssh://scm.gforge.inria.fr/svn/cgal/branches/CGAL-3.3-branch/Straight_skeleton_2/include/CGAL/predicates/Straight_skeleton_pred_ftC2.h $
// $Id: Straight_skeleton_pred_ftC2.h 36633 2007-02-27 18:19:42Z fcacciola $
//
// Author(s)     : Fernando Cacciola <[e-mail]>
//
#ifndef CGAL_STRAIGHT_SKELETON_PREDICATES_FTC2_H 
#define CGAL_STRAIGHT_SKELETON_PREDICATES_FTC2_H 1

#include <CGAL/constructions/Straight_skeleton_cons_ftC2.h>
#include <CGAL/Uncertain.h>
#include <CGAL/certified_quotient_predicates.h>

CGAL_BEGIN_NAMESPACE


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<class K>
inline
Uncertain<bool> certified_collinearC2( Point_2<K> const& p
                                     , Point_2<K> const& q
                                     , Point_2<K> 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 in the closed segment [p,r].
template<class K>
inline
Uncertain<bool> certified_collinear_are_ordered_along_lineC2( Point_2<K> const& p
                                                            , Point_2<K> const& q
                                                            , Point_2<K> 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 make_uncertain(true);
  
  return Uncertain<bool>::indeterminate();
}

// Returns true IFF segments e0,e1 share the same supporting line, 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<class K>
Uncertain<bool> are_edges_orderly_collinearC2( Segment_2<K> const& e0, Segment_2<K> const& e1 )
{
  return    certified_collinearC2(e0.source(),e0.target(),e1.source())
          &
            (  certified_collinear_are_ordered_along_lineC2(e0.source(),e0.target(),e1.source())
             | certified_collinear_are_ordered_along_lineC2(e1.source(),e0.source(),e0.target())
            )
          & certified_collinearC2(e0.source(),e0.target(),e1.target()) 
          & 
            (  certified_collinear_are_ordered_along_lineC2(e0.source(),e0.target(),e1.target()) 
             | certified_collinear_are_ordered_along_lineC2(e1.target(),e0.source(),e0.target()) 
            );
}

// Returns true IFF the supporting lines for segments e0,e1 are parallel (or the same)
template<class K>
inline
Uncertain<bool> are_edges_parallelC2( Segment_2<K> const& e0, Segment_2<K> const& e1 )
{
  Uncertain<Sign> 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<Sign>(ZERO) ) ;
}

template <class FT>
inline
Uncertain<Sign> 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<class K>
Uncertain<Trisegment_collinearity> certified_trisegment_collinearity ( Segment_2<K> const& e0
                                                                     , Segment_2<K> const& e1
                                                                     , Segment_2<K> const& e2
                                                                     )
{
  Uncertain<Trisegment_collinearity> rR = Uncertain<Trisegment_collinearity>::indeterminate();
  
  Uncertain<bool> is_01 = are_edges_orderly_collinearC2(e0,e1);
  if ( !CGAL_NTS is_indeterminate(is_01) )
  {
    Uncertain<bool> is_02 = are_edges_orderly_collinearC2(e0,e2);
    if ( !CGAL_NTS is_indeterminate(is_02) )
    {
      Uncertain<bool> is_12 = are_edges_orderly_collinearC2(e1,e2);
      if ( !CGAL_NTS is_indeterminate(is_12) )
      {
        if ( CGAL_NTS logical_and(is_01 , !is_02 , !is_12 ) )
          rR = make_uncertain(TRISEGMENT_COLLINEARITY_01);
        else if ( CGAL_NTS logical_and(is_02 , !is_01 , !is_12 ) )
          rR = make_uncertain(TRISEGMENT_COLLINEARITY_02);
        else if ( CGAL_NTS logical_and(is_12 , !is_01 , !is_02 ) )
          rR = make_uncertain(TRISEGMENT_COLLINEARITY_12);
        else if ( CGAL_NTS logical_and(!is_01 , !is_02, !is_12  ) )
          rR = make_uncertain(TRISEGMENT_COLLINEARITY_NONE);
        else 
          rR = make_uncertain(TRISEGMENT_COLLINEARITY_ALL);
      }
    }
  }

  return rR ;
}



// 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 event trisegment that corresponds to the node.
// A Seeded_trisegment stores not only the "current event" trisegment but also the trisegments for the left/right seed vertices.
// 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<class K>
Uncertain<bool> exist_offset_lines_isec2 ( Seeded_trisegment_2<K> const& st )
{
  typedef typename K::FT FT ;
  
  typedef Rational<FT>       Rational ;
  typedef optional<Rational> Optional_rational ;
  
  Uncertain<bool> rResult = Uncertain<bool>::indeterminate();

  if ( st.event().collinearity() != TRISEGMENT_COLLINEARITY_ALL ) 
  {
    CGAL_STSKEL_TRAITS_TRACE( ( st.event().collinearity() == TRISEGMENT_COLLINEARITY_NONE ? " normal edges" : " collinear edges" ) ) ;

    Optional_rational t = compute_offset_lines_isec_timeC2(st) ;
    if ( t )
    {
      Uncertain<bool> d_is_zero = CGAL_NTS certified_is_zero(t->d()) ;
      if ( ! CGAL_NTS is_indeterminate(d_is_zero) )
      {
        if ( !d_is_zero )
        {
          rResult = CGAL_NTS certified_is_positive(t->to_quotient()) ;
          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 = make_uncertain(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 = make_uncertain(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<class K>
Uncertain<Comparison_result> compare_offset_lines_isec_timesC2 ( Seeded_trisegment_2<K> const& m
                                                               , Seeded_trisegment_2<K> const& n 
                                                               )
{
  typedef typename K::FT FT ;
  
  typedef Trisegment_2<K> Trisegment_2 ;
  
  typedef Rational<FT>       Rational ;
  typedef Quotient<FT>       Quotient ;
  typedef optional<Rational> Optional_rational ;
  
  Uncertain<Comparison_result> rResult = Uncertain<Comparison_result>::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();
   
    CGAL_assertion ( CGAL_NTS certified_is_positive(mt) ) ;
    CGAL_assertion ( CGAL_NTS certified_is_positive(nt) ) ;

    rResult = CGAL_NTS certified_compare(mt,nt);
  }
  
  return rResult ;

}

// Given a point (px,py) and 2 triples of oriented straight line segments: (m0,m1,m2) and (n0,n1,n2),
// such that their offsets at distances 'mt' and 'nt' intersects in points (mx,my) and (nx,ny),
// returns the relative order of the distances from (px,py) to (mx,my) and (nx,ny).
// That is, indicates which offset triple intersects closer to (px,py)
// PRECONDITION: There exist single points at which the offset line triples 'm' and 'n' at 'mt' and 'nt' intersect.
template<class K>
Uncertain<Comparison_result>
compare_offset_lines_isec_dist_to_pointC2 ( optional< Point_2<K> > const& p
                                          , Seeded_trisegment_2<K> const& m
                                          , Seeded_trisegment_2<K> const& n 
                                          )
{
  typedef typename K::FT FT ;
  
  typedef Trisegment_2<K> Trisegment_2 ;
  
  typedef Rational<FT>       Rational ;
  typedef Quotient<FT>       Quotient ;
  typedef optional<Rational> Optional_rational ;
  
  Uncertain<Comparison_result> rResult = Uncertain<Comparison_result>::indeterminate();
  
  if ( p )
  {
    optional<FT> dm = compute_offset_lines_isec_dist_to_pointC2(p,m);
    optional<FT> dn = compute_offset_lines_isec_dist_to_pointC2(p,n);

    if ( dm && dn )
      rResult = CGAL_NTS certified_compare(*dm,*dn);
  }

  return rResult ;
}

// Given 3 triples of oriented straight line segments: (s0,s1,s2), (m0,m1,m2) and (n0,n1,n2),
// such that their offsets at distances 'st', 'mt' and 'nt' intersects in points (sx,sy), (mx,my) and (nx,ny),
// returns the relative order order of the distances from (sx,sy) to (mx,my) and (nx,ny).
// That is, indicates which offset triple intersects closer to (sx,sy)
// PRECONDITION: There exist single points at which the offsets at 'st', 'mt' and 'nt' intersect.
template<class K>
Uncertain<Comparison_result>
compare_offset_lines_isec_dist_to_pointC2 ( Seeded_trisegment_2<K> const& s
                                          , Seeded_trisegment_2<K> const& m
                                          , Seeded_trisegment_2<K> const& n
                                          )
{
  return compare_offset_lines_isec_dist_to_pointC2(construct_offset_lines_isecC2(s),m,n);
}

// Returns true if the point aP is on the positive side of the line supporting the edge
//
template<class K>
Uncertain<bool> is_edge_facing_pointC2 ( optional< Point_2<K> > const& aP, Segment_2<K> const& aEdge )
{
  typedef typename K::FT FT ;
  
  Uncertain<bool> rResult = Uncertain<bool>::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<class K>
inline Uncertain<bool> is_edge_facing_offset_lines_isecC2 ( Seeded_trisegment_2<K> const& st, Segment_2<K> const& aEdge )
{
  return is_edge_facing_pointC2(construct_offset_lines_isecC2(st),aEdge);
}


// 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 inside the passed offset zone.
// 
// An offset zone [z0,z1,z2], where zi is a line, is a region where the corresponding offset edges (oriented segment)
// Z0'->Z1'->Z2' remain connected in the absence of topological changes.
// It is the area (bounded or not) to the left of z1, to the right of the angular bisector (z0,z1) 
// and to the left of the angular bisector (z1,z2).
// This area represents all the possible offset edges Z1'.
//