gen_point_location.h

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

   vertically downwards/upwards.
   If the ray does not intersect any node or edge of |G|, then |nil| is 
   returned.\\
   The class |\Mtype| is generic, it is parameterized with a traits class 
   |PLocTraits| which widely controls its behaviour.
   The traits may even change the return type of a query and its semantics.
   There are predined traits classes for the LEDA graph types, which are
   described below in a seperate section.
}*/
public:
  // copied types from PLocTraits
  typedef typename PLocTraits::Point             Point;
  typedef typename PLocTraits::XCoord            XCoord;
  typedef typename PLocTraits::PredLessThanX     PredLessThanX;

  typedef typename PLocTraits::Graph             Graph;
  typedef typename PLocTraits::Node              Node;
  typedef typename PLocTraits::Edge              Edge;
  typedef typename PLocTraits::NodeIterator      NodeIterator;
  typedef typename PLocTraits::IncEdgeIterator   IncEdgeIterator;

  typedef typename PLocTraits::Curve             Curve;
  typedef typename PLocTraits::PredCompareCurves PredCompareCurves;

  typedef typename PLocTraits::QueryResult       QueryResult;

/*{\Mtypes}*/
  // define additional types 
  typedef GenericLocation<Node, Edge> Location;
  /*{\Mtypedef usual return value for the point loaction.}*/

  enum Direction { downwards, upwards};
  /*{\Menum used to specify the direction for the point location.}*/

  typedef CGAL_LEDA_SCOPE::pp_dictionary<Curve, Location, PredCompareCurves>   
                                                              Sweepline;
  typedef GenericXStructure<XCoord, PredLessThanX, Sweepline> XStructure;
  typedef typename Sweepline::item                            SL_item;
  typedef typename XStructure::Sweepline_iterator Sweepline_iterator;
  /*{\Mcreation}*/ 
  PointLocator() { clear(); }
  /*{\Mcreate creates an empty |\Mtype|.}*/

  PointLocator(const Graph& G, const PLocTraits& PLT = PLocTraits()) : 
   traits(PLT) { init(G); }
  /*{\Mcreate creates a |\Mtype| for the graph |G| and the traits |PLT|.}*/
     
  /*{\Moperations}*/
  void clear() { X_Structure.clear(); traits.clear(); }
  /*{\Mop makes |\Mvar| empty.}*/


  void init(const Graph& G, const PLocTraits& PLT) { traits = PLT; init(G); }
  /*{\Mop makes |\Mvar| a |\Mtype| for the graph |G| and the traits |PLT|.}*/

  void init(const Graph& G);
  /*{\Mop makes |\Mvar| a |\Mtype| for the graph |G|.}*/


  QueryResult locate(const Point& p, const Direction dir) const
  { return dir == downwards ? locate_down(p) : locate_up(p); }
  /*{\Mop locates the point |p| in the direction |dir|.}*/

  QueryResult locate_down(const Point& p) const;
  /*{\Mop locates the point |p| vertically downwards.}*/

  QueryResult locate_up(const Point& p) const;
  /*{\Mop locates the point |p| vertically upwards.}*/

  Location location(Sweepline_iterator S, SL_item it) const
  { return (it == nil ? Location() : S->inf(it)); }

  std::string str(const Sweepline& S) const
  { std::ostringstream os; os << "Sweepline:\n";
    SL_item it;
    forall_items(it,S) {  os << "  " << S.key(it) << std::endl; }
    return os.str();
  }


private:
  PLocTraits traits;
  XStructure X_Structure;

};

template <class PLocTraits>
void
PointLocator<PLocTraits>::init(const Graph& G)
{
  traits.sweep_begin(G);
  PredLessThanX LtX = traits.getLessThanX();
  typedef std::map<XCoord, std::list<Node>, PredLessThanX> dictionary;
  typedef typename dictionary::iterator dic_iterator;
  dictionary stops(LtX);
  // Note: X_Structure, Sweepline, and stops copy compare object

  NodeIterator ni = traits.Nodes_begin(G), beyond = traits.Nodes_end(G);
  for(; ni != beyond; ++ni) {
    XCoord currentX = traits.getXCoord(G, ni);
    stops[currentX].push_front(traits.toNode(ni));
  }

  Sweepline SL(traits.getCompareCurves());
  X_Structure.init(stops.size(), LtX);
  dic_iterator stop;
  for(stop = stops.begin(); stop != stops.end(); ++stop) {
    std::list<Node>& NodesOnSL = stop->second;
    traits.sweep_moveto(traits.getXCoord(G, *NodesOnSL.begin()));
      std::list<Edge> EmergingEdges, VerticalEdges;

      // explore the nodes on SL
      typename std::list<Node>::iterator cur_node;
      for(cur_node = NodesOnSL.begin(); 
          cur_node != NodesOnSL.end(); ++cur_node) {
        IncEdgeIterator ei     = traits.IncEdges_begin(G, *cur_node);
        IncEdgeIterator beyond = traits.IncEdges_end(G, *cur_node);
          CGAL_NEF_TRACEN("NODE: "<<(*cur_node)->point());
        for(; ei != beyond; ++ei) { 
          switch (traits.ClassifyEdge(G, traits.toEdge(ei), *cur_node)) {
            case PLocTraits::StartingNonVertical: 
              EmergingEdges.push_front(traits.toEdge(ei)); break;
            case PLocTraits::StartingVertical:    
              VerticalEdges.push_front(traits.toEdge(ei)); break;
            case PLocTraits::EndingNonVertical:
              SL.del(traits.makeCurve(G, traits.toEdge(ei))); break;
            case PLocTraits::EndingVertical: break;
          }
        }
      }

      // compute SL_at_X

      typename std::list<Edge>::iterator cur_edge;
      for(cur_edge=VerticalEdges.begin(); 
          cur_edge!=VerticalEdges.end(); ++cur_edge) 
        SL.insert(traits.makeCurve(G, *cur_edge), Location(*cur_edge));
      for(cur_node=NodesOnSL.begin();
          cur_node!=NodesOnSL.end(); ++cur_node)
        SL.insert(traits.makeCurve(G, *cur_node), Location(*cur_node));
      Sweepline SL_at_X = SL;

      // compute SL_in_X_plus

      for(cur_edge=VerticalEdges.begin(); 
          cur_edge!=VerticalEdges.end(); ++cur_edge)
        SL.del(traits.makeCurve(G, *cur_edge));
      for(cur_node=NodesOnSL.begin();
          cur_node!=NodesOnSL.end(); ++cur_node)
        SL.del(traits.makeCurve(G, *cur_node));

      for(cur_edge=EmergingEdges.begin();
          cur_edge!=EmergingEdges.end(); ++cur_edge) 
        SL.insert(traits.makeCurve(G, *cur_edge), Location(*cur_edge));

    X_Structure.insertLines(traits.getXCoord(G, *NodesOnSL.begin()), 
                            SL_at_X, SL);
  }

  traits.sweep_end();
}

template <class PLocTraits>
typename PointLocator<PLocTraits>::QueryResult
PointLocator<PLocTraits>::
locate_down(const typename PLocTraits::Point& p) const
{
  Sweepline_iterator line_at_x = X_Structure.getLineAt(traits.getXCoord(p)),
                     line_plus = line_at_x;
  CGAL_NEF_TRACEN("locate_down "<<str(*line_at_x));
  Curve p_curve = traits.makeCurve(p);
  PredCompareCurves cmp = traits.getCompareCurves();
  SL_item it = line_at_x->locate_pred(p_curve), it_plus(0);
  if ( it && line_at_x->inf(it).is_node() &&
       cmp(p_curve, line_at_x->key(it))!=0 ) {
    // p hit a feature exactly
    line_plus = line_at_x+1;
    if ( line_plus != X_Structure.end() )
      it_plus = line_plus->locate_pred(p_curve);
  }
  return traits.PostProcess(location(line_at_x,it),
                            location(line_plus,it_plus),p);
}

template <class PLocTraits>
typename PointLocator<PLocTraits>::QueryResult
PointLocator<PLocTraits>::locate_up(const typename PLocTraits::Point& p) const
{
  Sweepline_iterator line_at_x = 
    X_Structure.getLineAt(traits.getXCoord(p)), line_plus;
  Curve p_curve = traits.makeCurve(p);
  PredCompareCurves cmp = traits.getCompareCurves();
  SL_item it = line_at_x->locate_succ(p_curve), it_plus(0);
  if ( it && line_at_x->inf(it).is_node() &&
       cmp(p_curve, line_at_x->key(it))!=0 ) {
    // p hit a feature exactly
    line_plus = line_at_x+1;
    if ( line_plus != X_Structure.end() )
      it_plus = line_plus->locate_succ(p_curve);
  }
  return traits.PostProcess(location(line_at_x,it),
                            location(line_plus,it_plus), p);
}

/*{\Mimplementation
  The implementation of the data type |\Mtype| is based on partially 
  persistent binary search trees.
  The expected space requirement is $O(k)$ where $k$ is the sum of the number 
  of nodes and the number of edges in the graph $G$.
  The expected time needed for construction and the operation |init| is 
  $O(k \cdot \log k)$, for the |locate|-operations it is $O(\log k)$. The
  operation |clear| runs in $O(k)$.
}*/
/*{\Mtext
  \headerline{\arabic{manctr}. Predefined traits classes}
  \stepcounter{manctr}
  All predefined traits classes have in common that the return type of a query 
  is the type |Location|.
  The embedding of the given graph |G| is a straight-line embedding, so that
  it is totally determined by the position of the nodes of |G|.
  Such a position is specified by a |Point| which can be one of the LEDA point
  types |point| or |rat_point|. The positions can be specified implicitly by 
  the node attribute of a parameterized graph (e.g. |GRAPH<Point,...>|) or 
  explicitly by a |node_array<Point>|. In case of explicit specification a
  |node_array| with the positions of the nodes can be passed to the constructor
  of the traits class.
  Further, the point location processes for maps and for standard graphs differ
  slightly. As a map is a bidirected graph where each edge knows its reversal,
  the traits classes for maps can ensure the following property:
  If the result of a query for point |p| is an edge |e| (not containing |p|),
  then |e| bounds the face of |G| which contains |p|, i.e. |p| lies to the
  left of |e|.\\
  Here comes a list of the predefined traits classes:\\[-5.5ex]
  \begin{itemize}
  \item |PLocTraits<Graph>|: standard traits for implicitly specified node 
    positions\\
    |Graph| can be |GRAPH<Point,...>| (standard graph) or 
    |PLANAR_MAP<Point,...,...>| (map).
  \item |PLocTraits_NodeArray<Graph,Point>|: std. traits for explicitly 
    specified node positions\\
    |Graph| can be |graph| (standard graph) or |planar_map| (map).
  \item |PLocTraits_Map<Graph>| and |PLocTraits_Map_NodeArray<Graph,Point>|:\\
    The parameter |Graph| can be |GRAPH<Point,...>| and |graph| respectively.
    These traits classes assume that the given graphs are maps.
  \item |PLocTraits< GRAPH<Circle,Point> >|: traits class for closest-site 
    voronoi diagrams
  \end{itemize}
  Note that a traits class instantiated with |Graph| can also handle graph 
  types which are derived from |Graph|. Thus |PLocTraits< graph<Point,T> >| 
  can be used for graphs of type |ugraph<Point,T>| for example.
}*/
/*{\Mexample
First we show an example where the node positions are given implicitly
as node attributes:
\begin{verbatim}
  typedef PointLocator< PLocTraits< GRAPH<Point, int> > > PLocator1;
  typedef PLocator1::Location Location;

  UGRAPH<Point, int> G;
  ... // construct G

  PLocator1 PL1(G);
  Point p = ...; // compute p
  Location L1 = PL1.locate_down(p);
\end{verbatim}

The second example shows how a |node_array| can be used to determine the
node positions:
\begin{verbatim}
  typedef PLocTraits_NodeArray<planar_map,Point> PLocTraits2;
  typedef PointLocator<PLocTraits2> PLocator2;

  planar_map pm;
  node_array<Point> na;
  ... // construct pm and na

  PLocator2 PL2(pm, PLocTraits2(na));
  Point q = ...; // compute q
  Location L2 = PL2.locate_up(q);
\end{verbatim}
}*/

#endif // GEN_POINT_LOCATION_H