incircle_c2.h

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

// Copyright (c) 2003,2004,2006  INRIA Sophia-Antipolis (France).
// 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/Apollonius_graph_2/include/CGAL/Apollonius_graph_2/Incircle_C2.h $
// $Id: Incircle_C2.h 35183 2006-11-15 16:23:37Z hemmer $
// 
//
// Author(s)     : Menelaos Karavelas <[e-mail]>



#ifndef CGAL_APOLLONIUS_GRAPH_2_INCIRCLE_C2_H
#define CGAL_APOLLONIUS_GRAPH_2_INCIRCLE_C2_H

#include <CGAL/Apollonius_graph_2/basic.h>

#include <CGAL/Apollonius_graph_2/Predicate_constructions_C2.h>

#include <CGAL/Apollonius_graph_2/Bounded_side_of_ccw_circle_C2.h>


CGAL_BEGIN_NAMESPACE

CGAL_APOLLONIUS_GRAPH_2_BEGIN_NAMESPACE

//--------------------------------------------------------------------

template< class K >
class Sign_of_distance_from_bitangent_line_2
{
public:
  typedef Bitangent_line_2<K>               Bitangent_line;
  typedef typename K::Site_2                Site_2;
  typedef Inverted_weighted_point_2<K>      Inverted_weighted_point;
  typedef typename K::FT                    FT;
  typedef typename K::Sign                  Sign;

public:

  inline Sign
  operator()(const Bitangent_line& bl, const Site_2& q,
	     const Field_with_sqrt_tag&) const
    {
#ifdef AG2_PROFILE_PREDICATES
      ag2_predicate_profiler::distance_from_bitangent_counter++;
#endif
      FT a = bl.a1() + bl.a2() * CGAL::sqrt(bl.delta());
      FT b = bl.b1() + bl.b2() * CGAL::sqrt(bl.delta());
      FT c = bl.c1() + bl.c2() * CGAL::sqrt(bl.delta());
      FT r = a * q.x() + b * q.y() + c - q.weight() * bl.d();
      return CGAL::sign(r);
    }

  inline Sign
  operator()(const Bitangent_line& bl, const Site_2& q,
	     const Integral_domain_without_division_tag&) const
    {
#ifdef AG2_PROFILE_PREDICATES
      ag2_predicate_profiler::distance_from_bitangent_counter++;
#endif
      FT A = bl.a1() * q.x() + bl.b1() * q.y() + bl.c1()
	- q.weight() * bl.d();
      FT B = bl.a2() * q.x() + bl.b2() * q.y() + bl.c2();
      return sign_a_plus_b_x_sqrt_c(A, B, bl.delta());
    }
};

//--------------------------------------------------------------------


template< class K >
class Sign_of_distance_from_CCW_circle_2
{
public:
  typedef Bitangent_line_2<K>            Bitangent_line;
  typedef Inverted_weighted_point_2<K>   Inverted_weighted_point;
  typedef typename K::FT                 FT;
  typedef typename K::Sign               Sign;

public:
  inline Sign
  operator()(const Bitangent_line& bl,
	     const Inverted_weighted_point& v,
	     const Field_with_sqrt_tag&) const
    {
      FT a = bl.a1() + bl.a2() * CGAL::sqrt(bl.delta());
      FT b = bl.b1() + bl.b2() * CGAL::sqrt(bl.delta());
      FT c = bl.c1() + bl.c2() * CGAL::sqrt(bl.delta());
      FT r = a * v.x() + b * v.y() + c * v.p() - v.weight() * bl.d();
      return CGAL::sign(r);
    }

  inline Sign
  operator()(const Bitangent_line& bl,
	     const Inverted_weighted_point& v,
	     const Integral_domain_without_division_tag&) const
    {
      FT A = bl.a1() * v.x() + bl.b1() * v.y() + bl.c1() * v.p()
	- v.weight() * bl.d();
      FT B = bl.a2() * v.x() + bl.b2() * v.y() + bl.c2() * v.p();

      return sign_a_plus_b_x_sqrt_c(A, B, bl.delta());
    }
};


template < class Weighted_point >
class Weighted_point_less_than
{
public:
  inline
  bool operator()(const Weighted_point& p1,
		  const Weighted_point& p2) const
  {
    if ( p1.x() == p2.x() ) {
      return p1.y() < p2.y();
    }
    return p1.x() < p2.x();
  }
};

template < class K, class MTag >
class Vertex_conflict_2
{
public:
  typedef K                                 Kernel;
  typedef MTag                              Method_tag;

  typedef typename K::Point_2               Point_2;
  typedef typename K::Site_2                Site_2;
  typedef Weighted_point_inverter_2<K>      Weighted_point_inverter;
  typedef Inverted_weighted_point_2<K>      Inverted_weighted_point;
  typedef Bitangent_line_2<K>               Bitangent_line;
  typedef Voronoi_radius_2<K>               Voronoi_radius;
  typedef typename K::FT                    FT;
  typedef typename K::Orientation           Orientation;
  typedef typename K::Sign                  Sign;
  typedef typename K::Bounded_side          Bounded_side;

  typedef Bounded_side_of_CCW_circle_2<K>   Bounded_side_of_CCW_circle;

  typedef Sign_of_distance_from_bitangent_line_2<K>
                                     Sign_of_distance_from_bitangent_line;

  typedef Sign_of_distance_from_CCW_circle_2<K>
                                         Sign_of_distance_from_CCW_circle;

private:
  inline Orientation
  orientation(const Bitangent_line& l, const Point_2& p,
	      const Field_with_sqrt_tag&) const
    {
      FT A = l.a1() * p.x() + l.b1() * p.y() + l.c1();
      FT B = l.a2() * p.x() + l.b2() * p.y() + l.c2();
      FT P = A + B * CGAL::sqrt(l.delta());
      return CGAL::sign(P);
    }

  inline Orientation
  orientation(const Bitangent_line& l, const Point_2& p,
	      const Integral_domain_without_division_tag&) const
    {
      FT A = l.a1() * p.x() + l.b1() * p.y() + l.c1();
      FT B = l.a2() * p.x() + l.b2() * p.y() + l.c2();
      return sign_a_plus_b_x_sqrt_c(A, B, l.delta());
    }

  
  inline Orientation
  orientation(const Bitangent_line& l,
	      const Inverted_weighted_point& u) const
    {
      FT A = l.a1() * u.x() / u.p() + l.b1() * u.y() / u.p() + l.c1();
      FT B = l.a2() * u.x() / u.p() + l.b2() * u.y() / u.p() + l.c2();
      FT P = A + B * CGAL::sqrt(l.delta());
      return CGAL::sign(P);
    }

public:
  typedef Sign                result_type;
  typedef Site_2              argument_type;
  struct Arity {};

  inline
  Sign operator()(const Site_2& p1, const Site_2& p2,
		  const Site_2& p3, const Site_2& q) const
  {
#ifdef AG2_PROFILE_PREDICATES
    ag2_predicate_profiler::incircle_counter++;
#endif
    //
    Method_tag tag;
    Weighted_point_inverter inverter(p1);
    Inverted_weighted_point u2 = inverter(p2);
    Inverted_weighted_point u3 = inverter(p3);

    Voronoi_radius vr_123(u2, u3);

    Bounded_side bs = Bounded_side_of_CCW_circle()(vr_123, tag );

    if ( bs != ON_UNBOUNDED_SIDE ) { return NEGATIVE; }

    Inverted_weighted_point v = inverter(q);
    Bitangent_line blinv_23(u2, u3);
    Sign s = Sign_of_distance_from_CCW_circle()(blinv_23, v, tag);
    return s;
  }

  inline
  Sign operator()(const Site_2& p1, const Site_2& p2,
		  const Site_2& q) const
  {
    Method_tag tag;
    //
    Bitangent_line bl_21(p2, p1);
    Sign s = Sign_of_distance_from_bitangent_line()(bl_21, q, tag);
    if ( s != ZERO ) { return s; }

    Bitangent_line bl1_perp = bl_21.perpendicular(p1.point());
    Bitangent_line bl2_perp = bl_21.perpendicular(p2.point());
    Orientation o1 = orientation(bl1_perp, q.point(), tag);
    Orientation o2 = orientation(bl2_perp, q.point(), tag);

    CGAL_assertion( o1 != COLLINEAR || o2 != COLLINEAR );
    if ( o1 == o2 ) { return POSITIVE; }
    return NEGATIVE;
  }  

};

//--------------------------------------------------------------------

CGAL_APOLLONIUS_GRAPH_2_END_NAMESPACE

CGAL_END_NAMESPACE

#endif // CGAL_APOLLONIUS_GRAPH_2_INCIRCLE_C2_H