arr_basic_addition_visitor.h

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

// Copyright (c) 1997  Tel-Aviv University (Israel).
// 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/Arrangement_2/include/CGAL/Sweep_line_2/Arr_basic_addition_visitor.h $
// $Id: Arr_basic_addition_visitor.h 37160 2007-03-16 14:33:01Z lrineau $
// 
//
// Author(s)     : Baruch Zukerman <[e-mail]>

#ifndef CGAL_ARR_BASIC_ADDITION_VISITOR_H
#define CGAL_ARR_BASIC_ADDITION_VISITOR_H

CGAL_BEGIN_NAMESPACE

template<class Traits, class Arrangement_, class Event,class Subcurve>
class Arr_basic_addition_visitor : 
  public Arr_construction_visitor<Traits,Arrangement_,Event,Subcurve>
{
protected:

  typedef Arrangement_                                     Arrangement;
  
  typedef Arr_construction_visitor<Traits,
                                   Arrangement,
                                   Event,
                                   Subcurve>               Base;

  typedef Arr_basic_addition_visitor<Traits,
                               Arrangement,
                               Event,
                               Subcurve>                   Self;

  typedef typename Base::SL_iterator                       SL_iterator;
  typedef typename Base::Halfedge_handle                   Halfedge_handle;
  typedef typename Base::Vertex_handle                     Vertex_handle;
  typedef typename Base::SubCurveIter                      SubCurveIter;
  typedef typename Base::SubCurveRevIter                   SubCurveRevIter;
  typedef typename Traits::X_monotone_curve_2              X_monotone_curve_2;
  typedef typename Traits::Point_2                         Point_2;
  
  typedef typename Arrangement::Face_handle                Face_handle;
  typedef typename Arrangement::Face_const_handle          Face_const_handle;
  
public:

  Arr_basic_addition_visitor(Arrangement *arr): Base(arr)
  {}

  void before_sweep()
  {
    this->m_lh = 
      this->m_arr_access.bottom_left_fictitious_vertex()->incident_halfedges();
    if (this->m_lh->source()->boundary_in_x() != MINUS_INFINITY)
      this->m_lh = this->m_lh->next()->twin();
   
    this->m_bh = this->m_lh->next();
   
    this->m_th = 
      this->m_arr_access.top_left_fictitious_vertex()->incident_halfedges();
    if(this->m_th->source()->boundary_in_x() == MINUS_INFINITY)
      this->m_th = this->m_th->next()->twin();

    this->m_rh = 
      this->m_arr_access.bottom_right_fictitious_vertex()->incident_halfedges();
    if (this->m_rh->source()->boundary_in_x() == PLUS_INFINITY)
      this->m_rh = this->m_rh->twin();
    else
      this->m_rh = this->m_rh->next();

    CGAL_assertion (this->m_lh->direction() == LARGER);
    CGAL_assertion (this->m_lh->face() != 
                    this->m_arr_access.fictitious_face());
    CGAL_assertion (this->m_lh->target() == 
                    this->m_arr_access.bottom_left_fictitious_vertex());

    CGAL_assertion (this->m_bh->direction() == SMALLER);
    CGAL_assertion (this->m_bh->face() != 
                    this->m_arr_access.fictitious_face());
    CGAL_assertion (this->m_bh->source() ==
                    this->m_arr_access.bottom_left_fictitious_vertex());

    CGAL_assertion (this->m_rh->direction() == SMALLER);
    CGAL_assertion (this->m_rh->face() != 
                    this->m_arr_access.fictitious_face());
    CGAL_assertion (this->m_rh->source() == 
                    this->m_arr_access.bottom_right_fictitious_vertex());

    CGAL_assertion (this->m_th->direction() == LARGER);
    CGAL_assertion (this->m_th->face() != 
                    this->m_arr_access.fictitious_face());
    CGAL_assertion (this->m_th->target() == 
                    this->m_arr_access.top_left_fictitious_vertex());
  }

  void before_handle_event(Event* event)
  {
    if(!event->is_finite())
    {
       if(event->get_unbounded_curve().get_halfedge_handle() ==
          Halfedge_handle(NULL))
         Base::before_handle_event(event);
       else
       {
         Boundary_type x_inf = event->infinity_at_x();
         if(x_inf == MINUS_INFINITY)
         {
           this->m_lh = this->m_lh->twin()->next()->twin();
           this->m_prev_minus_inf_x_event = NULL;
         }
         else
           if(x_inf == PLUS_INFINITY)
             this->m_rh = this->m_rh->twin()->prev()->twin();
           else
           {
             Boundary_type y_inf = event->infinity_at_y();
             if(y_inf == MINUS_INFINITY)
               this->m_bh = this->m_bh->twin()->prev()->twin();
             else
             {
               CGAL_assertion(y_inf == PLUS_INFINITY);
               this->m_th = this->m_th->twin()->next()->twin();
               this->m_prev_plus_inf_y_event = NULL;
             }
           }
       }
    }

    event->get_is_curve_in_arr().resize(event->get_num_right_curves(),false);

    if(!event->has_right_curves())
    {
      // update the event with the highest left halfedge
      for(SubCurveRevIter iter = event->left_curves_rbegin();
          iter != event->left_curves_rend();
          ++iter)
      {
        Halfedge_handle he;
        if((he =(*iter)->get_last_curve().get_halfedge_handle()) !=
         Halfedge_handle(NULL))
        {
          event->set_halfedge_handle(he->twin());
          return;
        }
      }
    }

    if(!event->has_left_curves())
    {
      int i = 0;
      // indicates if there's halfedge to the right of the event
      for(SubCurveRevIter iter = event->right_curves_rbegin();
          iter != event->right_curves_rend();
          ++iter, ++i)
      {
        // update the event with the highest right halfedge
        Halfedge_handle he;
        if((he = (*iter)->get_last_curve().get_halfedge_handle()) !=
           Halfedge_handle(NULL))
        {
          event->get_is_curve_in_arr()[i] = true;
          if(event->get_halfedge_handle() ==
             Halfedge_handle(NULL))
            event->set_halfedge_handle(he);
        }
      }
      return;
    }

    // the event has left and right curves
    int i = 0;
    bool exist_right_halfedge = false; 
    for(SubCurveRevIter iter = event->right_curves_rbegin();
        iter != event->right_curves_rend();
        ++iter, ++i)
    {
      Halfedge_handle he;
      if((he = (*iter)->get_last_curve().get_halfedge_handle()) !=
         Halfedge_handle(NULL))
      {
        exist_right_halfedge = true;
        event->get_is_curve_in_arr()[i] = true;
        if(!is_split_event(*iter, event))
          // halfedge will not be splitted 
          event->set_halfedge_handle(he);
        else
        {
          he = split_edge((*iter)->get_last_curve().get_halfedge_handle(),
                          (*iter),
                           event->get_point());
          
          // 'he' has the same source as the splitted halfedge
          event->set_halfedge_handle(he);
          X_monotone_curve_2& last_curve =
            const_cast<X_monotone_curve_2&>((*iter)->get_last_curve());
          last_curve.set_halfedge_handle(he);
          
          //there cannot be another existing halfedge that need to be splitted
          // because they are disjoint
          return;
        }
      }
    }

    if(exist_right_halfedge)
    {
      return;
    }
    // if we have reached here, there are no halfedges to the right of 
    // the event, but still can be on the left of the event
    for(SubCurveRevIter iter = event->left_curves_rbegin();
        iter != event->left_curves_rend();
        ++iter)
    {
      Halfedge_handle he;
      if((he =(*iter)->get_last_curve().get_halfedge_handle()) !=
        Halfedge_handle(NULL))
      {
        event->set_halfedge_handle(he->twin());
        return;
      }
    }
  }


  void add_subcurve(const X_monotone_curve_2& cv, Subcurve* sc)
  {
    if(cv.get_halfedge_handle() == Halfedge_handle(NULL))
      Base::add_subcurve(cv,sc);
    else
    {
      // sc is an overlap Subcurve of existing edge and new curve,
      // which means that the edeg will have to be modified
      if (sc->get_orig_subcurve1())
      {
        this->m_arr_access.arrangement().modify_edge
          (this->current_event()->get_halfedge_handle()->
           next()->twin(),
           cv.base());
      }

      Halfedge_handle next_ccw_he = 
        this->current_event()->get_halfedge_handle()->next()->twin();
                                                                
      this->current_event()->set_halfedge_handle(next_ccw_he);
    }
  }

  bool after_handle_event(Event* event, SL_iterator iter, bool flag)
  {
    return (Base::after_handle_event(event,iter,flag));
  }


  Halfedge_handle _insert_in_face_interior (const X_monotone_curve_2& cv,
                                            Subcurve* sc)
  {
    Halfedge_handle he_above = ray_shoot_up(sc);
    Vertex_handle v1 = 
      this->m_arr_access.create_vertex(this->get_last_event(sc)->get_point());
    Vertex_handle v2 =
      this->m_arr_access.create_vertex(this->current_event()->get_point());