segment_overlay_traits.h

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

// Copyright (c) 1997-2000  Max-Planck-Institute Saarbruecken (Germany).
// 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/Nef_2/include/CGAL/Nef_2/Segment_overlay_traits.h $
// $Id: Segment_overlay_traits.h 37506 2007-03-26 16:05:24Z hachenb $
// 
//
// Author(s)     : Michael Seel <[e-mail]>
#ifndef CGAL_SEGMENT_OVERLAY_TRAITS_H
#define CGAL_SEGMENT_OVERLAY_TRAITS_H

#include <assert.h>
#undef CGAL_NEF_DEBUG
#define CGAL_NEF_DEBUG 23
#include <CGAL/Nef_2/debug.h>

#if defined(CGAL_USE_LEDA)
#include <CGAL/LEDA_basic.h>
#if CGAL_LEDA_VERSION < 500
#include <LEDA/tuple.h>
#include <LEDA/slist.h>
#include <LEDA/list.h>
#include <LEDA/map.h>
#include <LEDA/map2.h>
#include <LEDA/sortseq.h>
#include <LEDA/p_queue.h>
#else
#include <LEDA/core/tuple.h>
#include <LEDA/core/slist.h>
#include <LEDA/core/list.h>
#include <LEDA/core/map.h>
#include <LEDA/core/map2.h>
#include <LEDA/core/sortseq.h>
#include <LEDA/core/p_queue.h>
#endif
#include <utility>
#include <sstream>

namespace CGAL {
#ifdef CGAL_NEF_DEBUG
#define PIS(s) (s->first())
#endif

template <typename IT, typename PMDEC, typename GEOM>
class leda_seg_overlay_traits {
public:
  typedef IT                               ITERATOR;
  typedef std::pair<IT,IT>                 INPUT;
  typedef PMDEC                            OUTPUT;
  typedef typename PMDEC::Vertex_handle    Vertex_handle;
  typedef typename PMDEC::Halfedge_handle  Halfedge_handle;
  typedef GEOM                             GEOMETRY;
  typedef typename GEOMETRY::Point_2       Point_2;
  typedef typename GEOMETRY::Segment_2     Segment_2;

  typedef leda_two_tuple<Segment_2,ITERATOR> seg_pair;
  typedef seg_pair*                          ISegment;
  typedef leda_list<seg_pair>                IList;
  typedef typename IList::iterator           ilist_iterator;


  // types interfacing the generic sweep frame:
  ITERATOR its, ite;
  OUTPUT&  GO;
  const GEOMETRY& K;

  class cmp_segs_at_sweepline : public CGAL_LEDA_SCOPE::leda_cmp_base<ISegment>
  { const Point_2& p;
    ISegment s_bottom, s_top; // sentinel segments
    const GEOMETRY& K;
  public:
   cmp_segs_at_sweepline(const Point_2& pi, 
     ISegment s1, ISegment s2, const GEOMETRY& k) : 
     p(pi), s_bottom(s1), s_top(s2), K(k) {}

   int operator()(const ISegment& is1, const ISegment& is2) const
   { // Precondition: p is identical to the left endpoint of s1 or s2. 
     if ( is2 == s_top || is1 == s_bottom ) return -1;
     if ( is1 == s_top || is2 == s_bottom ) return 1;
     if ( is1 == is2 ) return 0;
     const Segment_2& s1 = is1->first();
     const Segment_2& s2 = is2->first();
     int s = 0;
     if ( p == K.source(s1) )      s =   K.orientation(s2,p);
     else if ( p == K.source(s2) ) s = - K.orientation(s1,p);
     else CGAL_assertion_msg(0,"compare error in sweep.");
     if ( s || K.is_degenerate(s1) || K.is_degenerate(s2) ) 
       return s;
    
     s = K.orientation(s2,K.target(s1));
     if (s==0) return ( is1 - is2 );
     // overlapping segments are not equal
     return s;
   }
  };

  struct cmp_pnts_xy : public CGAL_LEDA_SCOPE::leda_cmp_base<Point_2>
  { const GEOMETRY& K;
  public:
   cmp_pnts_xy(const GEOMETRY& k) : K(k) {}
   int operator()(const Point_2& p1, const Point_2& p2) const
   { return K.compare_xy(p1,p2); }
  };


  typedef leda_sortseq<Point_2,CGAL_LEDA_SCOPE::seq_item>        EventQueue; 
  typedef leda_sortseq<ISegment,CGAL_LEDA_SCOPE::seq_item>       SweepStatus;
  typedef leda_p_queue<Point_2,ISegment>                         SegQueue; 
  typedef leda_map<CGAL_LEDA_SCOPE::seq_item,Halfedge_handle>    AssocEdgeMap;
  typedef leda_slist<ITERATOR>                                   IsoList;
  typedef leda_map<CGAL_LEDA_SCOPE::seq_item, IsoList* >         AssocIsoMap;
  typedef leda_map2<ISegment,ISegment,CGAL_LEDA_SCOPE::seq_item> EventHash;

    CGAL_LEDA_SCOPE::seq_item  event;
    Point_2                    p_sweep;
    cmp_pnts_xy                cmp;
    EventQueue                 XS;
    seg_pair                   sl,sh;
    cmp_segs_at_sweepline      SLcmp;
    SweepStatus                YS;
    SegQueue                   SQ;

    EventHash                  IEvent;
    IList                      Internal;
    AssocEdgeMap               Edge_of;
    AssocIsoMap                Isos_of;

    leda_seg_overlay_traits(const INPUT& in, OUTPUT& G, 
      const GEOMETRY& k) : 
      its(in.first), ite(in.second), GO(G), K(k),
      cmp(K), XS(cmp), SLcmp(p_sweep,&sl,&sh,K), YS(SLcmp), SQ(cmp),
      IEvent(0), Edge_of(0), Isos_of(0) {}


  leda_string dump_structures() const
  { 
    std::ostringstream out;
    out << "SQ= ";
    CGAL_LEDA_SCOPE::pq_item pqit;
    forall_items(pqit,SQ) {
      if (SQ.prio(pqit)==XS.key(XS.succ(XS.min_item()))) 
      { out << SQ.inf(pqit)->first(); }
      pqit = SQ.next_item(pqit);
    }
    CGAL_LEDA_SCOPE::seq_item sit;
    out << "\nXS=\n";
    forall_items(sit,XS)
      out << "  " << XS.key(sit) << " " << XS.inf(sit) 
          <<std::endl;
    out << "YS=\n";
    for( sit = YS.max_item(); sit; sit=YS.pred(sit) )
      out << "  "<<YS.key(sit)->first()<<" "<<YS.inf(sit)<<std::endl;
    leda_string res(out.str().c_str()); 
    return res;
  }


  Point_2 source(ISegment is) const
  { return K.source(is->first()); }
  Point_2 target(ISegment is) const
  { return K.target(is->first()); }
  ITERATOR original(ISegment s) const
  { return s->second(); }

  int orientation(CGAL_LEDA_SCOPE::seq_item sit, const Point_2& p) const
  { return K.orientation(YS.key(sit)->first(),p); }

  bool collinear(CGAL_LEDA_SCOPE::seq_item sit1, 
                 CGAL_LEDA_SCOPE::seq_item sit2) const
  { Point_2 ps = source(YS.key(sit2)), pt = target(YS.key(sit2));
    return ( orientation(sit1,ps)==0 &&
             orientation(sit1,pt)==0 );
  }


  void compute_intersection(CGAL_LEDA_SCOPE::seq_item sit0)
  {    
    CGAL_LEDA_SCOPE::seq_item sit1 = YS.succ(sit0);
    if ( sit0 == YS.min_item() || sit1 == YS.max_item() ) return;
    ISegment s0 = YS.key(sit0);
    ISegment s1 = YS.key(sit1);
    int or0 = K.orientation(s0->first(),target(s1));
    int or1 = K.orientation(s1->first(),target(s0));
    if ( or0 <= 0 && or1 >= 0  ) { 
      CGAL_LEDA_SCOPE::seq_item it = IEvent(YS.key(sit0),YS.key(sit1));
      if ( it==0 ) {
        Point_2 q = K.intersection(s0->first(),s1->first());
        it = XS.insert(q,sit0);
      }
      YS.change_inf(sit0, it);
    }
  } 

  void initialize_structures()
  {
    CGAL_NEF_TRACEN("initialize_structures");
    ITERATOR it_s;  
    for ( it_s=its; it_s != ite; ++it_s ) {
      Segment_2 s = *it_s;
      CGAL_LEDA_SCOPE::seq_item it1 = 
            XS.insert( K.source(s), CGAL_LEDA_SCOPE::seq_item(nil));
      CGAL_LEDA_SCOPE::seq_item it2 = 
            XS.insert( K.target(s), CGAL_LEDA_SCOPE::seq_item(nil));
      if (it1 == it2) {
        if ( Isos_of[it1] == 0 ) Isos_of[it1] = new IsoList;
        Isos_of[it1]->push(it_s);
        continue;  // ignore zero-length segments in SQ/YS
      }
          
      Point_2 p = XS.key(it1);
      Point_2 q = XS.key(it2);
          
      Segment_2 s1; 
      if ( K.compare_xy(p,q) < 0 ) 
        s1 = K.construct_segment(p,q);
      else
        s1 = K.construct_segment(q,p);
          
      Internal.append(seg_pair(s1,it_s));
      SQ.insert(K.source(s1),&Internal[Internal.last()]);
    }

    // insert a lower and an upper sentinel segment
    YS.insert(&sl,CGAL_LEDA_SCOPE::seq_item(nil));
    YS.insert(&sh,CGAL_LEDA_SCOPE::seq_item(nil));
    CGAL_NEF_TRACEN("end of initialization\n"<<YS.size());
  }

  bool event_exists() 
  { 
    if (!XS.empty()) { 
      // event is set at end of loop and in init
      event = (XS.min)();
      p_sweep = XS.key(event);
      return true;
    }
    return false; 
  }

  void procede_to_next_event() 
  { XS.del_item(event); }

  void process_event() 
  {
    CGAL_NEF_TRACEN("\n\n >>> process_event: "<<p_sweep<<" "<<XS[event]<<" "<<event);

    Vertex_handle v = GO.new_vertex(p_sweep);
    CGAL_LEDA_SCOPE::seq_item sit = XS.inf(event);
        
      CGAL_LEDA_SCOPE::seq_item sit_succ(0), sit_pred(0), 
                                sit_pred_succ(0), sit_first(0);
      if (sit == nil) 
        {
          Segment_2 s_sweep = K.construct_segment(p_sweep,p_sweep);
          seg_pair sp(s_sweep, ite);
          sit_succ = YS.locate( &sp );
          if ( sit_succ != YS.max_item() && 
               orientation(sit_succ,p_sweep) == 0 ) 
            sit = sit_succ;
          else  {
            sit_pred = YS.pred(sit_succ);
            sit_pred_succ = sit_succ;
          }
          CGAL_NEF_TRACEN("looked up p_sweep "<<PIS(YS.key(sit_succ)));
        }



      /* If no segment contains p_sweep then sit_pred and sit_succ are
         correctly set after the above locate operation, if a segment
         contains p_sweep sit_pred and sit_succ are set below when
         determining the bundle.*/

      if (sit != nil) { // key(sit) is an ending or passing segment
        CGAL_NEF_TRACEN("ending/passing segs");
        while ( YS.inf(sit) == event ||
                YS.inf(sit) == YS.succ(sit) ) // overlapping
          sit = YS.succ(sit);
        sit_succ = YS.succ(sit); 
        CGAL_LEDA_SCOPE::seq_item sit_last = sit;

        CGAL_LEDA_SCOPE::seq_item xit = YS.inf(sit_last);
        if (xit) { 
          ISegment s1 = YS.key(sit_last);
          ISegment s2 = YS.key(sit_succ);
          IEvent(s1,s2) = xit;
            CGAL_NEF_TRACEN("hashing "<<PIS(s1)<<PIS(s2)<<xit);
        } 
          
        bool overlapping;
        do {
          ISegment s = YS.key(sit);
          CGAL_LEDA_SCOPE::seq_item sit_next = YS.pred(sit);
          overlapping = (YS.inf(sit_next) == sit);
          Halfedge_handle e = Edge_of[sit];
          if ( !overlapping ) {
            CGAL_NEF_TRACEN("connecting edge to node "<<PIS(s)<<" "<<sit);
            GO.link_as_target_and_append(v,e);
          }
          GO.supporting_segment(e,original(s));
          if ( target(s) == p_sweep ) { // ending segment
              CGAL_NEF_TRACEN("ending segment "<<PIS(s));
            if ( overlapping ) YS.change_inf(sit_next,YS.inf(sit));
            YS.del_item(sit);
            GO.ending_segment(v,original(s));
          } else {  // passing segment
              CGAL_NEF_TRACEN("passing segment "<<PIS(s));
            if ( YS.inf(sit) != YS.succ(sit) ) 
              YS.change_inf(sit, CGAL_LEDA_SCOPE::seq_item(0));
            GO.passing_segment(v,original(s));
          }
          sit = sit_next;
        } 
        while ( YS.inf(sit) == event || overlapping ||
                YS.inf(sit) == YS.succ(sit) );
                  
        sit_pred = sit;
        sit_first = sit_pred_succ = YS.succ(sit_pred); // first item of bundle

        CGAL_NEF_TRACE("event bundles between\n   "<<PIS(YS.key(sit_succ)));
        CGAL_NEF_TRACEN("\n   "<<PIS(YS.key(sit_pred)));

        while ( sit != sit_succ ) {
          CGAL_LEDA_SCOPE::seq_item sub_first = sit;
          CGAL_LEDA_SCOPE::seq_item sub_last  = sub_first;
                            
          while (YS.inf(sub_last) == YS.succ(sub_last))
            sub_last = YS.succ(sub_last);
                            
          if (sub_last != sub_first)
            YS.reverse_items(sub_first, sub_last);
                            
          sit = YS.succ(sub_first);
        }
                        
        // reverse the entire bundle
        if (sit_first != sit_succ) 
          YS.reverse_items(YS.succ(sit_pred),YS.pred(sit_succ));


      } // if (sit != nil)

    assert(sit_pred);
    GO.halfedge_below(v,Edge_of[sit_pred]);
    if ( Isos_of[event] != 0 ) {
      const IsoList& IL = *(Isos_of[event]);
      CGAL_LEDA_SCOPE::slist_item iso_it;
      for (iso_it = IL.first(); iso_it; iso_it=IL.succ(iso_it) ) 
        GO.trivial_segment(v,IL[iso_it] );
      delete (Isos_of[event]); // clean up the list
    }


    ISegment next_seg;
    CGAL_LEDA_SCOPE::pq_item next_it = SQ.find_min();
    while ( next_it && 
            (next_seg = SQ.inf(next_it), p_sweep == source(next_seg)) ) {
      CGAL_LEDA_SCOPE::seq_item s_sit = YS.locate_succ(next_seg);
      CGAL_LEDA_SCOPE::seq_item p_sit = YS.pred(s_sit);

      CGAL_NEF_TRACEN("inserting "<<PIS(next_seg)<<" at "<<PIS(YS.key(s_sit))); 
      if ( YS.max_item() != s_sit &&
           orientation(s_sit, source(next_seg) ) == 0 &&
           orientation(s_sit, target(next_seg) ) == 0 )
        sit = YS.insert_at(s_sit, next_seg, s_sit);
      else 
        sit = YS.insert_at(s_sit, next_seg, CGAL_LEDA_SCOPE::seq_item(nil));
      assert(YS.succ(sit)==s_sit);

      if ( YS.min_item() != p_sit &&
           orientation(p_sit, source(next_seg) ) == 0 &&
           orientation(p_sit, target(next_seg) ) == 0 )
        YS.change_inf(p_sit, sit);
      assert(YS.succ(p_sit)==sit);
                 
      XS.insert(target(next_seg), sit);
      GO.starting_segment(v,original(next_seg));
                 
      // delete minimum and assign new minimum to next_seg
      SQ.del_min();    
      next_it = SQ.find_min();
    }

    for( CGAL_LEDA_SCOPE::seq_item sitl = YS.pred(sit_succ); sitl != sit_pred; 
         sitl = YS.pred(sitl) ) {
      if ( YS.inf(sitl) != YS.succ(sitl) ) { // non-overlapping
        CGAL_NEF_TRACEN("non-overlapping "<<PIS(YS.key(sitl))<<" "<<sitl);
        Edge_of[sitl] = GO.new_halfedge_pair_at_source(v);
      } else {
        CGAL_NEF_TRACEN("overlapping "<<PIS(YS.key(sitl)));
        Edge_of[sitl] = Edge_of[ YS.succ(sitl) ];
      }
    }
    sit_first = YS.succ(sit_pred);


    assert(sit_pred); assert(sit_pred_succ);
    CGAL_LEDA_SCOPE::seq_item xit = YS.inf(sit_pred);
    if ( xit ) { 
      ISegment s1 = YS.key(sit_pred);
      ISegment s2 = YS.key(sit_pred_succ);
      IEvent(s1,s2) = xit;
        CGAL_NEF_TRACEN("hashing "<<PIS(s1)<<PIS(s2)<<xit);
      YS.change_inf(sit_pred, CGAL_LEDA_SCOPE::seq_item(0));
    }