segment_overlay_traits.h

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

    compute_intersection(sit_pred); 
    sit = YS.pred(sit_succ);
    if (sit != sit_pred)
      compute_intersection(sit);


  }

  void complete_structures() {}
  void check_invariants() {CGAL_NEF_TRACEN("check_invariants\n"<<dump_structures());}
  void check_final() {}

}; // leda_seg_overlay_traits

} // namespace CGAL

#endif // defined(CGAL_USE_LEDA)
#if !defined(CGAL_USE_LEDA)
#include <list>
#include <map>
#include <string>
#include <sstream>

namespace CGAL {

template <typename IT, typename PMDEC, typename GEOM>
class stl_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 std::pair<Segment_2,ITERATOR>     seg_pair;
  typedef seg_pair*                         ISegment;
  typedef std::list<seg_pair>               IList;
  typedef typename IList::const_iterator    ilist_iterator;


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


  class lt_segs_at_sweepline 
  { 
    const Point_2& p;
    ISegment s_bottom, s_top; // sentinel segments
    const GEOMETRY& K;

  public:
    lt_segs_at_sweepline(const Point_2& pi, 
			 ISegment s1, ISegment s2, 
			 const GEOMETRY& k) 
     : p(pi), s_bottom(s1), s_top(s2), K(k) 
    {}
    
    lt_segs_at_sweepline(const lt_segs_at_sweepline& lt) 
      : p(lt.p), s_bottom(lt.s_bottom), s_top(lt.s_top), K(lt.K) 
    {}
    
    bool 
    operator()(const ISegment& is1, const ISegment& is2) const
    { 
      if ( is2 == s_top || is1 == s_bottom ) return true;
      if ( is1 == s_top || is2 == s_bottom ) return false;
      if ( is1 == is2 ) return false;
      // Precondition: p is contained in s1 or s2. 
      const Segment_2& s1 = is1->first;
      const Segment_2& s2 = is2->first;

      CGAL_assertion_msg(( K.orientation(s1,p) == 0 ) ||  ( K.orientation(s2,p) == 0 ) ,"compare error in sweep.");

      int s = - K.orientation(s1,p);
      if ( s == 0 )      
	s =  K.orientation(s2,p);
      if ( s || K.is_degenerate(s1) || K.is_degenerate(s2) ) 
	return ( s < 0 );
      
      s = K.orientation(s2,K.target(s1));
      if (s==0) return ( is1 - is2 ) < 0;
      // overlapping segments are not equal
      return ( s < 0 );
    }
  };
  

  struct lt_pnts_xy { 
    const GEOMETRY& K;
    
  public:
    lt_pnts_xy(const GEOMETRY& k) 
      : K(k) 
    {}
    
    lt_pnts_xy(const lt_pnts_xy& lt) 
      : K(lt.K) 
    {}
    
    int 
    operator()(const Point_2& p1, const Point_2& p2) const
    { 
      return K.compare_xy(p1,p2) < 0; 
    }
  };
  


  typedef std::map<ISegment, Halfedge_handle, lt_segs_at_sweepline> 
                                                         SweepStatus;
  typedef typename SweepStatus::iterator                 ss_iterator;
  typedef typename SweepStatus::value_type               ss_pair;

  typedef std::list<ITERATOR>                            IsoList;
  typedef std::map<Point_2, IsoList*, lt_pnts_xy>        EventQueue;
  typedef typename EventQueue::iterator                  event_iterator;
  typedef typename EventQueue::value_type                event_pair;

  typedef std::multimap<Point_2, ISegment, lt_pnts_xy>   SegQueue;
  typedef typename SegQueue::iterator                    seg_iterator;
  typedef typename SegQueue::value_type                  ps_pair;

  event_iterator    event;
  Point_2           p_sweep;
  EventQueue        XS;
  seg_pair          sl,sh;
  SweepStatus       YS;
  SegQueue          SQ;
  IList             Internal;

  stl_seg_overlay_traits(const INPUT& in, OUTPUT& G, const GEOMETRY& k) 
    : its(in.first), ite(in.second), GO(G), K(k), 
    XS(lt_pnts_xy(K)), YS(lt_segs_at_sweepline(p_sweep,&sl,&sh,K)),
    SQ(lt_pnts_xy(K)) 
  {}


  std::string dump_structures() const
  { 
    std::ostringstream out; 
    out << "EventQueue:\n";
    typename EventQueue::const_iterator sit1;
    for(sit1 = XS.begin(); sit1 != XS.end(); ++sit1) 
      out << "  " << sit1->first << std::endl;

    out << "SegQueue:\n";
    typename SegQueue::const_iterator sit2;
    for(sit2 = SQ.begin(); sit2 != SQ.end(); ++sit2) 
      out << "  " << sit2->first << " " << sit2->second
          << " " << sit2->first << std::endl;

    out << "SweepStatus:\n";
    typename SweepStatus::const_iterator sit3;
    for( sit3 = YS.begin(); sit3 != YS.end(); ++sit3 )
      out << sit3->first << std::endl;
    return out.str();
  }

  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(ss_iterator sit, const Point_2& p) const
  { return K.orientation(sit->first->first,p); }

  bool collinear(ss_iterator sit1, ss_iterator sit2) const
  { Point_2 ps = source(sit2->first), pt = target(sit2->first);
    return ( orientation(sit1,ps)==0 &&
             orientation(sit1,pt)==0 );
  }

  void compute_intersection(ss_iterator sit0)
  {    
    // Given an item |sit0| in the Y-structure compute the point of 
    // intersection with its successor and (if existing) insert it into 
    // the event queue and do all necessary updates.
    ss_iterator sit1 = sit0; ++sit1;
    CGAL_NEF_TRACEN("compute_intersection "<<sit0->first<<" "<<sit1->first);
    if ( sit0 == YS.begin() || sit1 == --YS.end() ) return;
    const Segment_2& s0 = sit0->first->first;
    const Segment_2& s1 = sit1->first->first;
    int or0 = K.orientation(s0,K.target(s1));
    int or1 = K.orientation(s1,K.target(s0));
    if ( or0 <= 0 && or1 >= 0  ) { 
      Point_2 q = K.intersection(s0,s1);
      XS.insert(event_pair(q,0)); // only done if none existed!!!
    }
  } 

  void initialize_structures()
  {
    /* INITIALIZATION
       - insert all vertices into the x-structure
       - insert sentinels into y-structure
       - exploit the fact that insert operations into the x-structure
         leave previously inserted points unchanged to achieve that
         any pair of endpoints $p$ and $q$ with |p == q| are identical
    */
    CGAL_NEF_TRACEN("initialize_structures");
    
    ITERATOR it_s;  
    for ( it_s=its; it_s != ite; ++it_s ) {
      const Segment_2& s = *it_s;
      event_iterator it1 = (XS.insert(event_pair(K.source(s),0))).first;
      event_iterator it2 = (XS.insert(event_pair(K.target(s),0))).first;
      // note that the STL only inserts if key is not yet in XS
      if (it1 == it2) { 
        if ( it1->second == 0 ) it1->second = new IsoList;
        it1->second->push_front(it_s);
        continue;  // ignore zero-length segments regarding YS
      }
          
      Point_2 p = it1->first;
      Point_2 q = it2->first;
          
      Segment_2 s1; 
      if ( K.compare_xy(p,q) < 0 ) 
        s1 = K.construct_segment(p,q);
      else
        s1 = K.construct_segment(q,p);
          
      Internal.push_back(seg_pair(s1,it_s));
      SQ.insert(ps_pair(K.source(s1),&Internal.back()));
    }

    // insert a lower and an upper sentinel segment to avoid special
    // cases when traversing the Y-structure
    YS.insert(ss_pair(&sl,Halfedge_handle()));
    YS.insert(ss_pair(&sh,Halfedge_handle()));
    CGAL_NEF_TRACEN("end of initialization\n");
  }


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

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

  void process_event() 
  {
    CGAL_NEF_TRACEN("\n\n >>> process_event: "<<p_sweep);

    Vertex_handle v = GO.new_vertex(p_sweep);
    ss_iterator sit_succ, sit_pred, sit_first, sit;
    Segment_2 s_sweep = K.construct_segment(p_sweep,p_sweep);
    seg_pair sp(s_sweep, ite);
    sit_succ = YS.upper_bound(&sp);
    sit = sit_succ; --sit;

    
      /* |sit| is determined by upper bounding the search for the
         segment (p_sweep,p_sweep) and taking its predecessor.
         if the segment associated to |sit| contains |p_sweep| then
         there's a bundle of segments containing |p_sweep|.
         We compute the successor (|sit_succ)|) and 
         predecessor (|sit_pred|) items. */
      
       if ( sit == YS.begin() || orientation(sit,p_sweep) != 0 ) {
        sit_pred = sit;
        sit = YS.end();
      }

      /* If no segments contain 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 != YS.end() ) { // sit->first is ending or passing segment
        // Determine upper bundle item:
        CGAL_NEF_TRACEN("ending/passing segs");
      
        /* Walk down until |sit_pred|, close edges for all segments 
           in the bundle, delete all segments in the bundle, but 
           reinsert the continuing ones */

        std::list<ISegment> L_tmp;
        bool overlapping;
        do {
          ISegment s = sit->first;
          ss_iterator sit_next(sit); --sit_next;
          overlapping = (sit_next != YS.begin()) && collinear(sit,sit_next);
          Halfedge_handle e = sit->second;
          if ( overlapping ) {
            CGAL_NEF_TRACEN("overlapping segment "<<s);
          } else {
            CGAL_NEF_TRACEN("connecting edge to node "<<s);
            GO.link_as_target_and_append(v,e);
            /* in this case we close the output edge |e| associated to 
               |sit| by linking |v| as its target and by appending the 
               twin edge to |v|'s adjacency list. */
          }
          GO.supporting_segment(e,original(s));

          if ( target(s) == p_sweep ) {
              CGAL_NEF_TRACEN("ending segment "<<s);
            GO.ending_segment(v,original(s));
          } else { // passing segment, take care of the node here!
              CGAL_NEF_TRACEN("passing segment "<<s);
            L_tmp.push_back(s);
            GO.passing_segment(v,original(s));
           }
          sit = sit_next;
        } 
        while ( sit != YS.begin() && orientation(sit,p_sweep) == 0 );
              
        sit_pred = sit_first = sit;
        ++sit_first; // first item of the bundle

        CGAL_NEF_TRACE("event bundles between\n   "<<sit_succ->first);
        CGAL_NEF_TRACEN("\n   "<<sit_pred->first);

        /* Interfaceproposition for next chunk:
           - succ(sit_pred) == sit_first == sit_succ
           - bundle not empty: sit_first != sit_succ
        */

        // delete and reinsert the continuing bundle
        YS.erase(sit_first,sit_succ);
        typename std::list<ISegment>::const_iterator lit;
        for ( lit = L_tmp.begin(); lit != L_tmp.end(); ++lit ) {
          YS.insert(sit_pred,ss_pair(*lit,Halfedge_handle()));
        }
      } // if (sit != ss_iterator() )


      assert( sit_pred != YS.end() );
      GO.halfedge_below(v,sit_pred->second);
      if ( event->second != 0 ) {
        const IsoList& IL = *(event->second);
        typename IsoList::const_iterator iso_it;
        for (iso_it = IL.begin(); iso_it != IL.end(); ++iso_it) 
          GO.trivial_segment(v,*iso_it);
        delete (event->second);
      }


      ISegment next_seg;
      seg_iterator next_it = SQ.begin();
      while ( next_it != SQ.end() && 
              ( next_seg = next_it->second, p_sweep == source(next_seg)) ) {
        CGAL_NEF_TRACEN("inserting "<<next_seg);
        YS.insert(ss_pair(next_seg,Halfedge_handle()));
        GO.starting_segment(v,original(next_seg));
        // delete minimum and assign new minimum to next_seg
        SQ.erase(SQ.begin());
        next_it = SQ.begin();
      }
      // we insert new edge stubs, non-linked at target
      ss_iterator sit_curr = sit_succ, sit_prev = sit_succ;
      for( --sit_curr; sit_curr != sit_pred; 
           sit_prev = sit_curr, --sit_curr ) {
        CGAL_NEF_TRACEN("checking outedge "<<sit_curr->first<<"\n   "<<sit_prev->first);
        if ( sit_curr != YS.begin() && sit_prev != --YS.end() &&
             collinear(sit_curr,sit_prev) ) // overlapping
          sit_curr->second = sit_prev->second;
        else {
          CGAL_NEF_TRACEN("creating new edge");
          sit_curr->second = GO.new_halfedge_pair_at_source(v);
        }
      }
      sit_first = sit_prev;


      // compute possible intersections between |sit_pred| and its
      // successor and |sit_succ| and its predecessor
      CGAL_NEF_TRACEN("pred,succ = "<<sit_pred->first<<" "<<sit_succ->first);
      compute_intersection(sit_pred); 
      sit = sit_succ; --sit;
      if (sit != sit_pred)
        compute_intersection(sit);

  }

  void complete_structures() {}
  void check_invariants() {CGAL_NEF_TRACEN("check_invariants\n"<<dump_structures());}
  void check_final() {}


}; // stl_seg_overlay_traits

} // namespace CGAL

#endif // !defined(CGAL_USE_LEDA)

namespace CGAL {
#if defined(CGAL_USE_LEDA)
#define Segment_overlay_traits leda_seg_overlay_traits
static const char* const sweepversion = "LEDA segment overlay sweep";
#else
#define Segment_overlay_traits stl_seg_overlay_traits
static const char* const sweepversion = "STL segment overlay sweep";
#endif
} // namespace CGAL

#include <CGAL/generic_sweep.h>
#endif // CGAL_SEGMENT_OVERLAY_TRAITS_H