segment_delaunay_graph_hierarchy_2_impl.h

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

// Copyright (c) 2003,2004,2005,2006  INRIA Sophia-Antipolis (France) and
// Notre Dame University (U.S.A.).  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/Segment_Delaunay_graph_2/include/CGAL/Segment_Delaunay_graph_2/Segment_Delaunay_graph_hierarchy_2_impl.h $
// $Id: Segment_Delaunay_graph_hierarchy_2_impl.h 37297 2007-03-20 08:23:06Z afabri $
// 
//
// Author(s)     : Menelaos Karavelas <[e-mail]>




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

CGAL_BEGIN_NAMESPACE


//===========================================================================

//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
//  constructors
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------

template<class Gt, class ST, class STag, class DS, class LTag>
void
Segment_Delaunay_graph_hierarchy_2<Gt,ST,STag,DS,LTag>::
init_hierarchy(const Geom_traits& gt)
{
  hierarchy[0] = this; 
  for(unsigned int i = 1; i < sdg_hierarchy_2__maxlevel; ++i) {
    hierarchy[i] = new Base(gt);
  }
}

template<class Gt, class ST, class STag, class DS, class LTag>
Segment_Delaunay_graph_hierarchy_2<Gt,ST,STag,DS,LTag>::
Segment_Delaunay_graph_hierarchy_2(const Gt& gt)
  : Base(gt), random((long)0)
{ 
  init_hierarchy(gt);
}


// copy constructor duplicates vertices and faces
template<class Gt, class ST, class STag, class DS, class LTag>
Segment_Delaunay_graph_hierarchy_2<Gt,ST,STag,DS,LTag>::
Segment_Delaunay_graph_hierarchy_2
(const Segment_Delaunay_graph_hierarchy_2<Gt,ST,STag,DS,LTag> &sdg)
    : Base(sdg.geom_traits()), random((long)0)
{ 
  // create an empty triangulation to be able to delete it !
  init_hierarchy(sdg.geom_traits());
  copy(sdg);
} 

//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
//  destructor
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
template<class Gt, class ST, class STag, class DS, class LTag>
Segment_Delaunay_graph_hierarchy_2<Gt,ST,STag,DS,LTag>:: 
~Segment_Delaunay_graph_hierarchy_2()
{
  clear();
  for(unsigned int i = 1; i < sdg_hierarchy_2__maxlevel; ++i){ 
    delete hierarchy[i];
  }
}

//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
// assignment operator
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
template<class Gt, class ST, class STag, class DS, class LTag>
Segment_Delaunay_graph_hierarchy_2<Gt,ST,STag,DS,LTag> &
Segment_Delaunay_graph_hierarchy_2<Gt,ST,STag,DS,LTag>::
operator=(const Segment_Delaunay_graph_hierarchy_2<Gt,ST,STag,DS,LTag> &sdg)
{
  if ( this != &sdg ) {
    copy(sdg);
  }
  return *this;
}

//====================================================================
//====================================================================
//                   METHODS FOR INSERTION
//====================================================================
//====================================================================

//--------------------------------------------------------------------
// insertion of a point
//--------------------------------------------------------------------

template<class Gt, class ST, class STag, class DS, class LTag>
std::pair<bool,int>
Segment_Delaunay_graph_hierarchy_2<Gt,ST,STag,DS,LTag>::
insert_point(const Point_2& p, const Storage_site_2& ss, int level,
	     Vertex_handle* vertices)
{
  CGAL_precondition( level != UNDEFINED_LEVEL );

  int new_level = level;

  bool lies_on_seg = false;

  Vertex_handle vertex;
  Vertex_handle vs1, vs2;
  Vertex_handle vnear[sdg_hierarchy_2__maxlevel];

  Site_2 t = Site_2::construct_site_2(p);

  nearest_neighbor(t, vnear, false);

  size_type n = hierarchy[0]->number_of_vertices();
  if ( n > 2 ) {
    Arrangement_type at_res = this->arrangement_type(t, vnear[0]);

    CGAL_assertion( at_res == AT2::DISJOINT ||
		    at_res == AT2::INTERIOR ||
		    at_res == AT2::IDENTICAL );

    if ( vnear[0]->is_point() ) {
      if ( at_res == AT2::IDENTICAL ) {
	vertex = vnear[0];
	merge_info(vertex, ss);
      } else {
	vertex = hierarchy[0]->insert_point2(ss, t, vnear[0]);
      }
    } else { // nearest neighbor is a segment
      CGAL_assertion( vnear[0]->is_segment() );
      CGAL_assertion( at_res == AT2::DISJOINT ||
		      at_res == AT2::INTERIOR );

      if ( at_res == AT2::INTERIOR ) {
	CGAL_assertion( t.is_input() );
	lies_on_seg = true;

	int vnear_level = find_level(vnear[0]);

	// I need to find the level of the nearest neighbor that t
	// lies on and update the level of t
	if ( new_level < vnear_level ) {
	  new_level = vnear_level;
	}

	Vertex_triple vt =
	  hierarchy[0]->insert_exact_point_on_segment(ss, t, vnear[0]);
	vertex = vt.first;
	vs1 = vt.second;
	vs2 = vt.third;
      } else {
	vertex = hierarchy[0]->insert_point2(ss, t, vnear[0]);
      }
    }
  } else if ( n == 0 ) {
    vertex = hierarchy[0]->insert_first(ss, p);
  } else if ( n == 1 ) {
    vertex = hierarchy[0]->insert_second(ss, p);
  } else if ( n == 2 ) {
    vertex = hierarchy[0]->insert_third(ss, p);
  }

  CGAL_assertion( vertex != Vertex_handle() );

  if ( vertices != NULL ) { vertices[0] = vertex; }

  // insert at other levels
  Vertex_handle previous = vertex;
  Vertex_handle vs1_prev = vs1;
  Vertex_handle vs2_prev = vs2;

  //  Storage_site_2 ss = vertex->storage_site();

  int k = 1;
  while ( k <= new_level ) {
    size_type nv = hierarchy[k]->number_of_vertices();
    if ( nv > 2 ) {
      if ( nv < sdg_hierarchy_2__minsize ) {
	CGAL_assertion( vnear[k] == Vertex_handle() );
	vnear[k] = hierarchy[k]->nearest_neighbor(p);
      }
      Arrangement_type at_res = this->arrangement_type(t, vnear[k]->site());
      if ( at_res == AT2::INTERIOR ) {
	Vertex_triple vt =
	  hierarchy[k]->insert_exact_point_on_segment(ss, t, vnear[k]);
	vertex = vt.first;
	vs1 = vt.second;
	vs2 = vt.third;

	CGAL_assertion( (same_segments(vs1_prev->site(), vs1->site()) &&
			 same_segments(vs2_prev->site(), vs2->site())) ||
			(same_segments(vs1_prev->site(), vs2->site()) &&
			 same_segments(vs2_prev->site(), vs1->site())) );
	if ( same_segments(vs1_prev->site(), vs1->site()) ) {
	  vs1->set_down(vs1_prev);
	  vs1_prev->set_up(vs1);
	  vs1_prev = vs1;

	  vs2->set_down(vs2_prev);
	  vs2_prev->set_up(vs2);
	  vs2_prev = vs2;
	} else {
	  vs1->set_down(vs2_prev);
	  vs2_prev->set_up(vs1);
	  vs2_prev = vs1;

	  vs2->set_down(vs1_prev);
	  vs1_prev->set_up(vs2);
	  vs1_prev = vs2;
	}
      } else {
	vertex = hierarchy[k]->insert_point(ss, t, vnear[k]);	
      }
    } else if ( nv == 2 ) {
      vertex = hierarchy[k]->insert_third(t, ss);
    } else { // nv == 0 || nv == 1
      vertex = hierarchy[k]->insert_no_register(ss, p, vnear[k]);
    }

    CGAL_assertion( vertex != Vertex_handle() );

    if ( vertices != NULL ) { vertices[k] = vertex; }

    vertex->set_down(previous); // link with other levels
    previous->set_up(vertex);
    previous = vertex;
    k++;
  }
  return std::make_pair(lies_on_seg, new_level);
}


template<class Gt, class ST, class STag, class DS, class LTag>
void
Segment_Delaunay_graph_hierarchy_2<Gt,ST,STag,DS,LTag>::
insert_point(const Site_2& t, const Storage_site_2& ss,
	     int low, int high, Vertex_handle vbelow,
	     Vertex_handle* vertices)
{
  CGAL_precondition( low >= 1 && low <= high );
  CGAL_precondition( vbelow != Vertex_handle() );

  Vertex_handle vertex;
  Vertex_handle vnear[sdg_hierarchy_2__maxlevel];

  nearest_neighbor(t, vnear, false);

  Vertex_handle previous = vbelow;

  // insert at all levels
  int k = low;
  while ( k <= high ) {
    // MK::ERROR: this is a hack. I need to change the code in the
    // segment Delaunay graph class, so that I can insert sites as
    // the first, second, or third site...; actually this is
    // problematic only if the number of vertices is exactly 2; it
    // cannot be smaller since we already have added the endpoints
    // of the segment at level k.
    size_type n = hierarchy[k]->number_of_vertices();
    if ( n > 2 ) {
      vertex = hierarchy[k]->insert_point(ss, t, vnear[k]);
    } else if ( n == 2 ) {
      vertex = hierarchy[k]->insert_third(t, ss);
    } else {
      if ( ss.is_input() ) {
	vertex = hierarchy[k]->insert_no_register(ss, t.point(), vnear[k]);
      } else {
	break;
      }
      // ideally what should be instead of the break-statement above is the
      // following statement(s) in the #if-#endif block
#if 0
    } else if ( n == 1 ) {
      vertex = hierarchy[k]->insert_second(t, ss);
    } else {
      CGAL_assertion( n == 0 );
      vertex = hierarchy[k]->insert_first(t, ss);
#endif
    }

    CGAL_assertion( vertex != Vertex_handle() );

    if ( vertices != NULL ) { vertices[k] = vertex; }

    vertex->set_down(previous); // link with other levels
    previous->set_up(vertex);
    previous = vertex;
    k++;
  }
}


//--------------------------------------------------------------------
// insertion of a segment
//--------------------------------------------------------------------
template<class Gt, class ST, class STag, class DS, class LTag>
typename
Segment_Delaunay_graph_hierarchy_2<Gt,ST,STag,DS,LTag>::Vertex_handle
Segment_Delaunay_graph_hierarchy_2<Gt,ST,STag,DS,LTag>::
insert_segment(const Point_2& p0, const Point_2& p1,
	       const Storage_site_2& ss, int level)
{
  // the tag is true so we DO insert segments in hierarchy
  if ( level == UNDEFINED_LEVEL ) {
    level = random_level();
  }

  Site_2 t = Site_2::construct_site_2(p0, p1);

  if ( is_degenerate_segment(t) ) {
    Storage_site_2 ss_src = ss.source_site();
    convert_info(ss_src, ss, true);
    return insert_point(p0, ss_src, level);
  }

  Vertex_handle vertices0[sdg_hierarchy_2__maxlevel];
  Vertex_handle vertices1[sdg_hierarchy_2__maxlevel];

  Storage_site_2 ss_src = ss.source_site();
  convert_info(ss_src, ss, true);
#if 1
  insert_point(p0, ss_src, level, vertices0);
#else
  std::pair<bool,int> res = insert_point(p0, ss_src, level, vertices0);
  if ( res.first ) { level = res.second; }
#endif

  Storage_site_2 ss_trg = ss.target_site();
  convert_info(ss_trg, ss, false);
  insert_point(p1, ss_trg, level, vertices1);

  CGAL_assertion( vertices0[0] != Vertex_handle() );
  CGAL_assertion( vertices1[0] != Vertex_handle() );

  Vertex_handle vertex;

  if ( hierarchy[0]->number_of_vertices() == 2 ) {
    static Segments_in_hierarchy_tag stag;

    vertex = hierarchy[0]->insert_third(ss, vertices0[0], vertices1[0]);
    insert_segment_in_upper_levels(t, vertex->storage_site(),
				   vertex, vertices0, level, stag);
  } else {
    vertex = insert_segment_interior(t, ss, vertices0, level);
  }

  return vertex;
}

template<class Gt, class ST, class STag, class DS, class LTag>
typename
Segment_Delaunay_graph_hierarchy_2<Gt,ST,STag,DS,LTag>::Vertex_handle
Segment_Delaunay_graph_hierarchy_2<Gt,ST,STag,DS,LTag>::
insert_segment_interior(const Site_2& t, const Storage_site_2& ss,
			const Vertex_handle* vertices, int level)
{
  // insert the interior of a segment, and DO insert segments in
  // upper levels of the hierarchy
  CGAL_precondition( t.is_segment() );
  CGAL_precondition( this->number_of_vertices() >= 2 );

  CGAL_assertion( vertices[0] != Vertex_handle() );
  // MK: add here code that checks if the inserted segment has already
  // been inserted; MAYBE THIS IS NOT NEEDED; I ALREADY DO IT IN
  // arrangement_type

  // the tags
  static Intersections_tag          itag;
  static Segments_in_hierarchy_tag  stag;