apollonius_graph_2_impl.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/Apollonius_graph_2_impl.h $
// $Id: Apollonius_graph_2_impl.h 32657 2006-07-20 16:30:15Z mkaravel $
// 
//
// Author(s)     : Menelaos Karavelas <[e-mail]>


#ifndef CGAL_APOLLONIUS_GRAPH_2_IMPL_H
#define CGAL_APOLLONIUS_GRAPH_2_IMPL_H

// class implementation continued
//=================================

CGAL_BEGIN_NAMESPACE


//--------------------------------------------------------------------
// test method
//--------------------------------------------------------------------
template<class Gt, class Agds, class LTag>
bool
Apollonius_graph_2<Gt,Agds,LTag>::
is_valid(bool verbose, int level) const
{
  if (level < 0) { return true; }

  if (number_of_vertices() <= 1) { return true; }

  // level 0 test: check the TDS
  bool result = this->_tds.is_valid(verbose, level);
  //  bool result(true);

  //  CGAL_assertion( result );

  if ( result && verbose ) {
    std::cerr << "AGDS is ok... " << std::flush;
  }

  if (level == 0) { return result; }

  // level 1 test: do the incircle tests

  if (number_of_vertices() < 3)  return true;

  //  CGAL_triangulation_assertion(result);

  for (All_edges_iterator eit = all_edges_begin();
       eit != all_edges_end(); ++eit) {
    Edge e = *eit;
    Face_handle f = e.first;
    Vertex_handle v = tds().mirror_vertex(f, e.second);
    if ( f->vertex(e.second) == v ) { continue; }
    if ( !is_infinite(v) ) {
      result = result &&
	( incircle(f, v->site()) != NEGATIVE );
      //    CGAL_triangulation_assertion(result);
    }
    Edge sym_e = sym_edge(e);
    f = sym_e.first;
    v = tds().mirror_vertex(f, sym_e.second);
    if ( !is_infinite(v) ) {
      result = result &&
	( incircle(f, v->site()) != NEGATIVE );
      //    CGAL_triangulation_assertion(result);
    }
  }

  if ( result && verbose ) {
    std::cerr << "Apollonius diagram is ok..." << std::flush;
  }
  if ( !result && verbose ) {
    std::cerr << "Apollonius diagram is NOT valid..." << std::flush;
  }

  //  CGAL_triangulation_assertion(result);
  return result;
}



//--------------------------------------------------------------------
// embedding and visualization methods and constructions for primal
// and dual
//--------------------------------------------------------------------

// circumcenter
template<class Gt, class Agds, class LTag>
typename Apollonius_graph_2<Gt,Agds,LTag>::Point_2
Apollonius_graph_2<Gt,Agds,LTag>::
circumcenter(const Face_handle& f) const
{
  CGAL_triangulation_precondition (dimension()==2 || !is_infinite(f));
  return circumcenter(f->vertex(0)->site(),
		      f->vertex(1)->site(),
		      f->vertex(2)->site());
}

template<class Gt, class Agds, class LTag>
typename Apollonius_graph_2<Gt,Agds,LTag>::Point_2
Apollonius_graph_2<Gt,Agds,LTag>::
circumcenter(const Site_2& p0, const Site_2& p1, 
	     const Site_2& p2) const
{
  return
    geom_traits().construct_Apollonius_vertex_2_object()(p0, p1, p2);
}

// circumcircle
template<class Gt, class Agds, class LTag>
typename Apollonius_graph_2<Gt,Agds,LTag>::Site_2
Apollonius_graph_2<Gt,Agds,LTag>::
circumcircle(const Face_handle& f) const
{
  CGAL_triangulation_precondition (dimension()==2 || !is_infinite(f));
  return circumcircle(f->vertex(0)->site(),
		      f->vertex(1)->site(),
		      f->vertex(2)->site());
}

template<class Gt, class Agds, class LTag>
typename Apollonius_graph_2<Gt,Agds,LTag>::Site_2
Apollonius_graph_2<Gt,Agds,LTag>::
circumcircle(const Site_2& p0, const Site_2& p1, 
	     const Site_2& p2) const
{
  return
    geom_traits().construct_Apollonius_site_2_object()(p0, p1, p2);
}


template<class Gt, class Agds, class LTag>
typename Gt::Line_2
Apollonius_graph_2<Gt,Agds,LTag>::
circumcircle(const Site_2& p0, const Site_2& p1) const
{
  return
    geom_traits().construct_Apollonius_site_2_object()(p0, p1);
}


// dual
template<class Gt, class Agds, class LTag>
typename Gt::Object_2
Apollonius_graph_2<Gt,Agds,LTag>::
dual(const Face_handle& f) const
{
  if ( !is_infinite(f) ) {
    Site_2 cc = circumcircle(f);
    return geom_traits().construct_object_2_object()(cc);
  }

  int i_inf(-1);
  for (int i = 0; i < 3; i++) {
    if ( is_infinite( f->vertex(i) ) ) {
      i_inf = i;
      break;
    }
  }
  typename Gt::Line_2 ll = circumcircle(f->vertex((i_inf+1)%3)->site(),
					f->vertex((i_inf+2)%3)->site());
  return geom_traits().construct_object_2_object()(ll);
}


template<class Gt, class Agds, class LTag>
typename Gt::Object_2
Apollonius_graph_2<Gt,Agds,LTag>::
dual(const Edge e) const
{
  CGAL_triangulation_precondition( !is_infinite(e) );

  if ( dimension() == 1 ) {
    Site_2 p = (e.first)->vertex(cw(e.second))->site();
    Site_2 q = (e.first)->vertex(ccw(e.second))->site();

    return construct_Apollonius_bisector_2_object()(p,q);
  }

  // dimension == 2
  // none of the two adjacent faces is infinite
  if( (!is_infinite(e.first)) &&
      (!is_infinite(e.first->neighbor(e.second))) ) {
    Site_2 p = (e.first)->vertex( ccw(e.second) )->site();
    Site_2 q = (e.first)->vertex(  cw(e.second) )->site();
    Site_2 r = (e.first)->vertex(     e.second  )->site();
    Site_2 s = tds().mirror_vertex(e.first, e.second)->site();
    return construct_Apollonius_bisector_segment_2_object()(p,q,r,s);
  }

  // both of the adjacent faces are infinite
  if ( is_infinite(e.first) &&
       is_infinite(e.first->neighbor(e.second)) )  {
    Site_2 p = (e.first)->vertex(cw(e.second))->site();
    Site_2 q = (e.first)->vertex(ccw(e.second))->site();
    return construct_Apollonius_bisector_2_object()(p,q);
  }

  // only one of the adjacent faces is infinite
  CGAL_triangulation_assertion( is_infinite( e.first ) ||
				is_infinite( e.first->neighbor(e.second) )
				);

  CGAL_triangulation_assertion( !(is_infinite( e.first ) &&
				  is_infinite( e.first->neighbor(e.second) )
				  )
				);

  CGAL_triangulation_assertion
    (  is_infinite( e.first->vertex(e.second) ) ||
       is_infinite( tds().mirror_vertex(e.first, e.second) )  );

  Edge ee = e;
  if ( is_infinite( e.first->vertex(e.second) )  ) {
    ee = sym_edge(e);
  }
  Site_2 p = ee.first->vertex( ccw(ee.second) )->site();
  Site_2 q = ee.first->vertex(  cw(ee.second) )->site();
  Site_2 r = ee.first->vertex(     ee.second  )->site();

  return construct_Apollonius_bisector_ray_2_object()(p,q,r);
}



// primal
template<class Gt, class Agds, class LTag>
typename Gt::Object_2
Apollonius_graph_2<Gt,Agds,LTag>::
primal(const Edge e) const
{
  typedef typename Geom_traits::Segment_2  Segment;
  typedef typename Geom_traits::Ray_2      Ray;
  typedef CGAL::Hyperbola_segment_2<Gt>    Hyperbola_segment;
  typedef CGAL::Parabola_segment_2<Gt>     Parabola_segment;
  //  typedef typename Geom_traits::Hyperbola_segment_2  Hyperbola_segment;
  //  typedef typename Geom_traits::Parabola_segment_2   Parabola_segment;

  //  CGAL_triangulation_precondition( !is_infinite(e) );

  if ( number_of_vertices() != 2 ) {
    if ( is_infinite(e) ) {
      Ray ray;
      if (  is_infinite( e.first->vertex(cw(e.second)) )  ) {
	Site_2 p = e.first->vertex( ccw(e.second) )->site();
	Site_2 r = e.first->vertex( e.second )->site();
	Site_2 s = tds().mirror_vertex( e.first, e.second )->site();
	ray = construct_Apollonius_primal_ray_2_object()(p,r,s);
      } else {
	CGAL_triangulation_assertion
	  (   is_infinite( e.first->vertex(ccw(e.second)) )   );
	Site_2 q = e.first->vertex( cw(e.second) )->site();
	Site_2 r = e.first->vertex( e.second )->site();
	Site_2 s = tds().mirror_vertex( e.first, e.second )->site();
	ray = construct_Apollonius_primal_ray_2_object()(q,s,r);
      }
      return make_object(ray);
    }
  }

  if ( dimension() == 1 ) {
    Site_2 p = (e.first)->vertex(cw(e.second))->site();
    Site_2 q = (e.first)->vertex(ccw(e.second))->site();
    Segment seg = construct_Apollonius_primal_segment_2_object()(p, q);
    return make_object(seg);

  }

  // dimension == 2
  if( (!is_infinite(e.first)) &&
      (!is_infinite(e.first->neighbor(e.second))) ) {
    Site_2 p = (e.first)->vertex( ccw(e.second) )->site();
    Site_2 q = (e.first)->vertex(  cw(e.second) )->site();
    Site_2 r = (e.first)->vertex(     e.second  )->site();
    Site_2 s = tds().mirror_vertex(e.first, e.second)->site();
    return construct_Apollonius_primal_segment_2_object()(p,q,r,s);
  }

  // both of the adjacent faces are infinite
  if ( is_infinite(e.first) &&
       is_infinite(e.first->neighbor(e.second)) )  {
    Site_2 p = (e.first)->vertex(cw(e.second))->site();
    Site_2 q = (e.first)->vertex(ccw(e.second))->site();
    Segment seg = construct_Apollonius_primal_segment_2_object()(p,q);
    return make_object(seg);
  }

  // only one of the adjacent faces is infinite
  Edge ee = e;
  if ( is_infinite(e.first) ) {
    ee = sym_edge(e);
  }
  Site_2 p = (ee.first)->vertex( ccw(ee.second) )->site();
  Site_2 q = (ee.first)->vertex(  cw(ee.second) )->site();
  Site_2 r = (ee.first)->vertex(     ee.second  )->site();
  Parabola_segment ps =
    construct_Apollonius_primal_segment_2_object()(p,q,r);
  return make_object(ps);
}


//--------------------------------------------------------------------
// combinatorial operations
//--------------------------------------------------------------------
template<class Gt, class Agds, class LTag>
typename Apollonius_graph_2<Gt,Agds,LTag>::Edge
Apollonius_graph_2<Gt,Agds,LTag>::
flip(Face_handle& f, int i)
{
  CGAL_triangulation_precondition ( f != Face_handle() );
  CGAL_triangulation_precondition (i == 0 || i == 1 || i == 2);
  CGAL_triangulation_precondition( dimension()==2 ); 

  CGAL_triangulation_precondition( f->vertex(i) != tds().mirror_vertex(f,i) );

  this->_tds.flip(f, i);

  return Edge(f, ccw(i));
}

template<class Gt, class Agds, class LTag>
typename Apollonius_graph_2<Gt,Agds,LTag>::Edge
Apollonius_graph_2<Gt,Agds,LTag>::
flip(Edge e)
{
  return flip(e.first, e.second);
}

template<class Gt, class Agds, class LTag>
typename Apollonius_graph_2<Gt,Agds,LTag>::Vertex_handle
Apollonius_graph_2<Gt,Agds,LTag>::
insert_in_face(Face_handle& f, const Site_2& p)
{
  Vertex_handle v = this->_tds.insert_in_face( f );

  v->set_site(p);
  return v;
}

template<class Gt, class Agds, class LTag>
bool
Apollonius_graph_2<Gt,Agds,LTag>::
is_degree_2(const Vertex_handle& v) const
{
  Face_circulator fc = incident_faces(v);
  Face_circulator fc1 = fc;
  ++(++fc1);
  return ( fc == fc1 );
}

template<class Gt, class Agds, class LTag>
typename Apollonius_graph_2<Gt,Agds,LTag>::Vertex_handle
Apollonius_graph_2<Gt,Agds,LTag>::
insert_degree_2(Edge e)
{
  return this->_tds.insert_degree_2(e.first, e.second);
}

template<class Gt, class Agds, class LTag>
typename Apollonius_graph_2<Gt,Agds,LTag>::Vertex_handle
Apollonius_graph_2<Gt,Agds,LTag>::
insert_degree_2(Edge e, const Site_2& p)
{
  Vertex_handle v = insert_degree_2(e);

  v->set_site(p);
  return v;
}


template<class Gt, class Agds, class LTag>
void
Apollonius_graph_2<Gt,Agds,LTag>::
remove_degree_2(Vertex_handle v)
{
  CGAL_triangulation_precondition( is_degree_2(v) );

  this->_tds.remove_degree_2( v );
}


template<class Gt, class Agds, class LTag>
void
Apollonius_graph_2<Gt,Agds,LTag>::
remove_degree_3(Vertex_handle v)
{
#ifdef CGAL_T2_USE_ITERATOR_AS_HANDLE
  remove_degree_3(v, Face_handle());
#else
  remove_degree_3(v, NULL);
#endif
}


template<class Gt, class Agds, class LTag>
void
Apollonius_graph_2<Gt,Agds,LTag>::
#ifdef CGAL_T2_USE_ITERATOR_AS_HANDLE
remove_degree_3(Vertex_handle v, Face_handle f) // af:was Face*
#else
remove_degree_3(Vertex_handle v, Face* f)
#endif
{
  CGAL_triangulation_precondition( degree(v) == 3 );
  this->_tds.remove_degree_3(v, f);
}

//--------------------------------------------------------------------
// insertion of weighted point
//--------------------------------------------------------------------

template<class Gt, class Agds, class LTag>
typename Apollonius_graph_2<Gt,Agds,LTag>::Vertex_handle
Apollonius_graph_2<Gt,Agds,LTag>::
insert_first(const Site_2& p)
{
  CGAL_triangulation_precondition(number_of_vertices() == 0);
  Vertex_handle v = this->_tds.insert_second();
  v->set_site(p);
  return v;
  //  return Delaunay_graph::insert_first(p);
}

template<class Gt, class Agds, class LTag>
typename Apollonius_graph_2<Gt,Agds,LTag>::Vertex_handle
Apollonius_graph_2<Gt,Agds,LTag>::
insert_second(const Site_2& p)
{
  CGAL_triangulation_precondition( number_of_vertices() == 1 );
  Vertex_handle vnew;
  Vertex_handle v(finite_vertices_begin());
  if ( is_hidden(v->site(), p) ) {
    v->add_hidden_site(p);
    vnew = Vertex_handle();  
  } else if ( is_hidden(p, v->site()) ) {
    v->add_hidden_site(v->site());
    v->set_site(p);
    vnew = v;
  } else {
    CGAL_triangulation_precondition(number_of_vertices() == 1);
    vnew = this->_tds.insert_dim_up(infinite_vertex(), true);
    vnew->set_site(p);
    //    vnew = Delaunay_graph::insert_second(p);
  }

  return vnew;
}

template<class Gt, class Agds, class LTag>
typename Apollonius_graph_2<Gt,Agds,LTag>::Vertex_handle
Apollonius_graph_2<Gt,Agds,LTag>::
insert_third(const Site_2& p)
{
  CGAL_triangulation_precondition( number_of_vertices() == 2 );

  Vertex_handle v1(finite_vertices_begin());
  Vertex_handle v2(++finite_vertices_begin());

  if ( is_hidden(v1->site(), p) ) {
    v1->add_hidden_site(p);
    return Vertex_handle();
  }
  if ( is_hidden(v2->site(), p) ) {
    v2->add_hidden_site(p);
    return Vertex_handle();
  }

  bool t1 = is_hidden(p, v1->site());
  bool t2 = is_hidden(p, v2->site());

  if ( t1 && !t2 ) {
    v1->add_hidden_site(v1->site());
    v1->set_site(p);
    return v1;
  } else if ( !t1 && t2 ) {
    v2->add_hidden_site(v2->site());
    v2->set_site(p);
    return v2;
  } else if ( t1 && t2 ) {
    v1->add_hidden_site(v1->site());
    v1->add_hidden_site(v2->site());
    v1->set_site(p);
    remove_second(v2);
    return v1;
  }

  Vertex_handle v = this->_tds.insert_dim_up(infinite_vertex());
  v->set_site(p);

  Face_handle f(finite_faces_begin());

  Point_2 p1 = f->vertex(0)->site().point();
  Point_2 p2 = f->vertex(1)->site().point();
  Point_2 p3 = f->vertex(2)->site().point();

  Orientation o =
    geom_traits().orientation_2_object()(p1, p2, p3);

  if ( o != LEFT_TURN ) {
    f->reorient();
    for (int i = 0; i < 3; i++) {
      f->neighbor(i)->reorient();
    }
  }

  Conflict_type ct =
    finite_edge_conflict_type_degenerated(v1->site(), v2->site(), p);