gen_point_location.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/gen_point_location.h $
// $Id: gen_point_location.h 33222 2006-08-10 15:14:32Z ameyer $
// 
//
// Author(s)     : Michael Seel <[e-mail]>


#ifndef GEN_POINT_LOCATION_H
#define GEN_POINT_LOCATION_H

#include <CGAL/LEDA_basic.h>
#if CGAL_LEDA_VERSION < 500
#include <LEDA/pp_dictionary.h>
#else
#include <LEDA/core/pp_dictionary.h>
#endif
#include <sstream>
#include <string>
#include <list>
#include <vector>
#include <map>
#include <CGAL/Nef_2/geninfo.h>

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

// #define CHECKING_OFF

// for dictionary
template <class Node>
inline std::ostream& operator<<(std::ostream& o, const std::list<Node>& n) 
{ return o; }

/*{\Manpage {GenericLocation}{Node, Edge}
{Return Type for Planar Point Location}{L}}*/

template <class Node, class Edge>
class GenericLocation {
/*{\Mdefinition
  An instance of the data type |\Mtype| is used as return value for planar 
  point location. It can store a node or an edge of a graph or the special
  value |nil| which is used to signal that no node or edge could be found.
}*/
  typedef void* GenPtr;
public:
/*{\Mtypes}*/ 
  enum Type { NIL, NODE, EDGE };
  /*{\Menum This enumeration allows to specify the 3 basic types of the 
     values that a |\Mtype| can represent.}*/

  /*{\Mcreation}*/ 
    GenericLocation()       { init(); }
    /*{\Mcreate creates a |\Mtype| and initializes with the value |nil|.}*/
    GenericLocation(Node n) { init(n); }
    /*{\Mcreate creates a |\Mtype| and initializes with the node |n|.}*/
    GenericLocation(Edge e) { init(e); }
    /*{\Mcreate creates a |\Mtype| and initializes with the edge |e|.}*/

    ~GenericLocation() { clear(); }

    GenericLocation(const GenericLocation<Node, Edge>& L) { assign(L); }
    GenericLocation<Node, Edge>& operator=(
      const GenericLocation<Node, Edge>& L)
    { clear(); assign(L); return *this; }

  /*{\Moperations}*/
    operator const Node&() const
    {
  #if !defined(CHECKING_OFF)
      if (type != NODE) 
        CGAL_LEDA_SCOPE::error_handler(1, "Location: not convertible to node");
  #endif
      return geninfo<Node>::const_access(value);
    }
    /*{\Mconversion converts |\Mvar| into a node.\\
       \precond |\Mvar| represents a node.}*/

    operator const Edge&() const
    { 
  #if !defined(CHECKING_OFF)
      if (type != EDGE) 
        CGAL_LEDA_SCOPE::error_handler(1, "Location: not convertible to edge");
  #endif
      return geninfo<Edge>::const_access(value);
    }
    /*{\Mconversion converts |\Mvar| into an edge.\\
       \precond |\Mvar| represents an edge.}*/

    GenericLocation<Node, Edge>& operator=(Node n)
    { clear(); init(n); return *this; }
    /*{\Mbinop makes |\Mvar| represent the node |n|.}*/

    GenericLocation<Node, Edge>& operator=(Edge e)
    { clear(); init(e); return *this; }
    /*{\Mbinop makes |\Mvar| represent the edge |e|.}*/

    Type get_type() const { return type; }
    /*{\Mop returns the type of the value contained in |\Mvar|.}*/

    bool is_nil()  const { return type == NIL; }
    /*{\Mop returns |true| iff |\Mvar| represents the value |nil|.}*/

    bool is_node() const { return type == NODE; }
    /*{\Mop returns |true| iff |\Mvar| represents a node.}*/

    bool is_edge() const { return type == EDGE; }
    /*{\Mop returns |true| iff |\Mvar| represents an edge.}*/

  private:
    void init() { type = NIL; }
    void init(Node n) 
    { type = NODE; 
      geninfo<Node>::create(value); 
      geninfo<Node>::access(value) = n; 
    }
    void init(Edge e) 
    { type = EDGE; 
      geninfo<Edge>::create(value); 
      geninfo<Edge>::access(value) = e; 
    }

    void clear()
    { 
      switch(type) {
       case NODE: geninfo<Node>::clear(value); break;
       case EDGE: geninfo<Edge>::clear(value); break;
       case NIL: break;
      }
    }

    void assign(const GenericLocation<Node, Edge>& L)
    { 
      type = L.type;
      switch(type) {
       case NODE: 
         geninfo<Node>::access(value) = geninfo<Node>::const_access(L.value); 
         break;
       case EDGE: 
         geninfo<Edge>::access(value) = geninfo<Edge>::const_access(L.value);
         break;
       case NIL: break;
      }
    }

  public:
    typedef GenericLocation<Node, Edge> self;


private:
  Type   type;
  GenPtr value;
};

/*{\Mimplementation
  The data type |\Mtype| is implemented as a union of the types |Node| and 
  |Edge|. There is only constant time and space overhead.
}*/
template <class Node, class Edge>
inline
bool 
operator==(const GenericLocation<Node, Edge>& L1, 
           const GenericLocation<Node, Edge>& L2)
{ 
  if (L1.get_type() != L2.get_type()) return false;
  switch (L1.get_type()) {
   case GenericLocation<Node, Edge>::NIL:  return true;
   case GenericLocation<Node, Edge>::NODE: return Node(L1) == Node(L2);
   case GenericLocation<Node, Edge>::EDGE: return Edge(L1) == Edge(L2);
  }
}

template <class Node, class Edge>
inline
bool 
operator!=(const GenericLocation<Node, Edge>& L1, 
           const GenericLocation<Node, Edge>& L2)
{ return ! (L1==L2); }

template <class Node, class Edge>
std::ostream& operator<<(std::ostream& o, 
                         const GenericLocation<Node, Edge>& L)
{
  switch (L.get_type()) {
   case GenericLocation<Node, Edge>::NIL:  return o<<"nil";
   case GenericLocation<Node, Edge>::NODE: return o<<"node("<<&*Node(L)<<')';
   case GenericLocation<Node, Edge>::EDGE: return o<<"edge("<<&*Edge(L)<<')';
  }
  return o;
}

template <class Node, class Edge>
std::istream& operator>>(std::istream& i, GenericLocation<Node, Edge>&)
{ return i; }
template <class XCoord, class PredLessThanX, class Sweepline>
class GenericXStructure {
public:
  typedef std::vector<XCoord>    Array_Coordinates;
  typedef std::vector<Sweepline> Array_Sweeplines;
  typedef typename Array_Coordinates::const_iterator Coord_iterator;
  typedef typename Array_Sweeplines::const_iterator  Sweepline_iterator;
private:
  int stops;
  PredLessThanX     LtX;
  Array_Coordinates Coordinates;
  Array_Sweeplines  SweepLines;
  // SweepLines[0] is EmptyLine;
public:
  GenericXStructure() { clear(); }
  GenericXStructure(int n, const PredLessThanX& cmp) { init(n, cmp); }
  ~GenericXStructure() { clear(); }

  void init(int n, const PredLessThanX& cmp)
  { CGAL_NEF_TRACEN("XSinit "<<n); 
    LtX = cmp;
    Coordinates = Array_Coordinates(n);
    SweepLines =  Array_Sweeplines(2*n+1);
    stops = 0;
  }

  void clear()
  { Coordinates.clear();
    SweepLines.clear();
    stops = 0;
  }

  void insertLines(const XCoord& X, 
                   const Sweepline& atX, const Sweepline& inXplus)
  { CGAL_NEF_TRACEN("XSinsert "<<X); 
    Coordinates[stops]    = X;
    SweepLines[2*stops+1]   = atX;
    SweepLines[2*stops+2] = inXplus;
    ++stops;
  }

  Sweepline_iterator getLineAt(const XCoord& X) const
  { CGAL_NEF_TRACEN("XSgetLineAt "<<X);
    Sweepline_iterator sit = SweepLines.begin(); // EmptyLine
    if ( LtX(X,*Coordinates.begin()) ) {
      CGAL_NEF_TRACEN("infinity first");
      return sit; // ]-infinity, x0[
    }
    Coord_iterator stopit = std::lower_bound (
        Coordinates.begin(),Coordinates.end(),X,LtX);
    /* determines stopit maximal such that 
       \forall j \in [begin,stopit) : *j < X
       as a consequence now: *stopit >= X */
    bool found_exact = false;
    if ( LtX(X,*stopit) ) --stopit;  // X <  *stopit
    else found_exact = true;         // X >= *stopit
      
    CGAL_NEF_TRACEN("stopit "<<*stopit);
    int offset = stopit-Coordinates.begin();
    return found_exact ? 
      SweepLines.begin() + (2*offset+1) :
      SweepLines.begin() + (2*offset+2);
  }

  Sweepline_iterator begin() const { return SweepLines.begin(); }
  Sweepline_iterator end() const { return SweepLines.end();}

};
/*{\Manpage {PointLocator} {PLocTraits} {Planar Point Location} {PL}}*/

template <class PLocTraits>
class PointLocator {
/*{\Mdefinition
   An instance |\Mvar| of the parameterized data type |\Mtype| can be used
   to perform point location queries in the two-dimensional plane.
   Every non-empty instance |\Mvar| is associated with an embedded planar 
   graph |G|, which has to remain unchanged while it is referenced by |PL|.\\
   A location query for a point |p| returns the first object (node or edge)
   of |G| which is intersected by the straight ray starting in |p| and going