point_set.h

A Library of Efficient Data Types and Algorithms,封装了常用的ADT及其相关算法的软件包

   /*{\Mop  if |T| contains a node $v$ with $|pos(v)| = p$ 
   the result is $v$ otherwise the result is |nil|. 
   The optional second argument is an edge of |\Mvar|, where the |locate| 
   operation starts searching |p|. }*/

   node   lookup(POINT p, const list<edge>& loc_start) const;
   /*{\Mop  returns |lookup(p,e)| with |e| in |loc_start|.
            If |loc_start| is empty, we return |lookup(p, NULL)|. 
	    The operation tries to choose a good starting edge for the $lookup$ 
	    operation from |loc_start|.
	    \precond All edges in |loc_start| must be edges of |\Mvar|.}*/   

   node   insert(POINT p);
   /*{\Mop  inserts point $p$ into |T| and returns the corresponding node. 
            More precisely, if there is already a node |v| in |T| positioned 
            at $p$ (i.e., |pos(v)| is equal to |p|) then |pos(v)| is changed to 
            |p| (i.e., |pos(v)| is made identical to |p|) and if there is no 
            such node then a new node $v$ with |pos(v) = p| is added to |T|. 
            In either case, $v$ is returned.}*/


   void del(node v);

   /*{\Mop removes the node $v$, i.e., makes |T| a Delaunay triangulation 
   for $S \setminus \sset{|pos(v)|}$. }*/

   void del(POINT p);

   /*{\Mop removes the node $p$, i.e., makes |T| a Delaunay triangulation 
   for $S \setminus p$. }*/


   node   nearest_neighbor(POINT p);
   /*{\Mop  computes a node $v$ of |T| that 
   is closest to $p$,
   i.e., $|dist(p,pos(v))| = \min\{\ |dist(p,pos(u))| \mid u\in T\ \}$. This is
   a non-const operation.}*/

   node   nearest_neighbor(node w) const;
   /*{\Mop  computes a node $v$ of |T| that 
   is closest to $p = T[w]$,
   i.e., $|dist(p,pos(v))| = \min\{\ |dist(p,pos(u))| \mid u\in T\ \}$.}*/

   node   nearest_neighborA(node w) const;
   node   nearest_neighborC(POINT p);
   node   nearest_neighborD(POINT p) const; 

   list<node>   nearest_neighbors(POINT p, int k);
   /*{\Mop  returns the $k$ nearest neighbors of $p$, i.e., a list 
   of the $\min(k,\Labs{S})$ nodes of |T| closest to $p$. The list is
   ordered by distance from |p|. This is a non-const operation.}*/ 

   list<node>   nearest_neighbors(node w, int k) const;
   /*{\Mop  returns the $k$ nearest neighbors of $p = T[w]$, i.e., a list 
   of the $\min(k,\Labs{S})$ nodes of |T| closest to $p$. The list is
   ordered by distance from |p|.}*/ 


   list<node> range_search(const CIRCLE& C);
   /*{\Mop returns the list of all nodes contained in the closure of disk $C$.\\
           \precond $C$ must be a proper circle (not a straight line). 
   This is a non-const operation.}*/

   list<node> range_search(node v,const POINT& p) const;
   /*{\Mop returns the list of all nodes contained in the closure of disk $C$
   with center $pos[v]$ and having $p$ in its boundary.}*/


   list<node> range_search(const POINT& a, const POINT& b, const POINT& c);
   /*{\Mop returns the list of all nodes contained in the closure 
           of the triangle $(a,b,c)$.\\
           \precond $a$, $b$, and $c$ must not be collinear. 
           This is a non-const operation.}*/
   
   
   list<node> range_search_parallelogram(const POINT& a, const POINT& b, 
                                                         const POINT& c);
   /*{\Mop returns the list of all nodes contained in the closure of the 
           parallelogram $(a,b,c,d)$  with $d = a + (c-b)$.\\
           \precond $a$, $b$, and $c$ must not be collinear. 
           This is a non-const operation.}*/   

   list<node> range_search(const POINT& a, const POINT& b);
   /*{\Mop returns the list of all nodes contained in the closure 
           of the rectangle with diagonal $(a,b)$. 
           This is a non-const operation.}*/


   list<edge> minimum_spanning_tree() const; 
   /*{\Mop returns the list of edges of |T| that comprise a minimum spanning
           tree of |S|. }*/
   
   list<edge> relative_neighborhood_graph();
   /*{\Mop returns the list of edges of |T| that comprise a relative 
           neighborhood graph of |S|. }*/   

   void   compute_voronoi(GRAPH<CIRCLE,POINT>& V) const;
   /*{\Mop  computes the corresponding Voronoi diagram $V$. 
            Each node of $VD$ is labeled with its defining circle.
            Each edge is labeled with the site lying in the face to
            its left. }*/


   /*{\Mtext {\bf Drawing Routines}

   The functions in this section were designed to support the drawing of 
   Delaunay triangulations and Voronoi diagrams. 
   \setlength{\typewidth}{0cm}
   \setlength{\callwidth}{3cm}
   \computewidths
   }*/

   void   draw_nodes(void (*draw_node)(const POINT&)); 
   /*{\Mopl calls |draw_node(pos(v))| for every node $v$ of $T$. }*/


   void   draw_edge(edge e,
                    void (*draw_diagram_edge)(const POINT&,const POINT&),
                    void (*draw_triang_edge) (const POINT&,const POINT&),
                    void (*draw_hull_dart)   (const POINT&,const POINT&));

   /*{\Mopl calls
      |draw_diagram_edge(pos_source(e),pos_target(e)| if |e| is a diagram dart,
      |draw_hull_dart(pos_source(e),pos_target(e)| if |e| is a hull dart,
      and |draw_triang_edge(pos_source(e),pos_target(e)| if |e| is a
      non-diagram edge. }*/


   void   draw_edges( void (*draw_diagram_edge)(const POINT&,const POINT&),
                      void (*draw_triang_edge) (const POINT&,const POINT&),
                      void (*draw_hull_dart)   (const POINT&,const POINT&));
   /*{\Mopl calls the corresponding function for all edges of |T|.}*/


   void   draw_edges(const list<edge>& L,
                     void (*draw_edge)(const POINT&, const POINT&));
   /*{\Mopl calls |draw_edge(pos_source(e),pos_target(e)| for 
   every edge $e \in L$. }*/


   void   draw_voro_edges(void (*draw_edge)(const POINT&,const POINT&),
                          void (*draw_ray) (const POINT&,const POINT&));

   /*{\Mopl calls |draw_edge| and |draw_ray| for the edges of the 
   Voronoi diagram.}*/


   void   draw_hull(void (*draw_poly)(const list<POINT>&));
   /*{\Mopl calls |draw_poly| with the list of vertices of the convex hull. }*/


   void   draw_voro(const GRAPH<CIRCLE,POINT>&,
                    void (*draw_node)(const POINT&), 
                    void (*draw_edge)(const POINT&,const POINT&),
                    void (*draw_ray) (const POINT&,const POINT&));
   /*{\Mopl calls ... }*/



   
   void checking_on()
   { check = true; }
   /*{\Xop enables checking mode.}*/

   void checking_off()
   { check = false; }
   /*{\Xop disables checking mode.}*/

   void save_state(const POINT& p) const;
   /*{\Xop in checking mode: saves the state of the data structure on 
   files [[point_set_error.graph]] and [[point_set_error.aux]]. 
   The graph part is written on the former file and
   |hull_dart|, |cur_dart| and $p$ are written on the latter file.
   No action is performed if the checking mode is disabled.
   }*/

   void save_state(const POINT& p, const edge& answer) const;
   /*{\Xop in checking mode: saves the state of the data structure on 
   files [[point_error.graph]] and [[point_error.aux]]. 
   The graph part is written on the former file and
   |hull_dart|, |cur_dart|, $p$, and |answer| are written on the latter file.
   No action is performed if the checking mode is disabled.
   }*/

   bool check_state(const string& location) const;
   /*{\Xop in checking mode: 
   checks the current state of the data structure. 
   If it finds an error it writes a diagnostic messages to |cerr|.
   No action is performed if the checking mode is disabled.}*/

   bool     IS_NON_DIAGRAM_DART(edge e) const;
   /*{\Xop checks whether $e$ is a non-diagram dart. }*/

   bool     IS_NON_DIAGRAM_EDGE(edge e) const;
   /*{\Xop as above. }*/

   // for testing
   edge get_cur_dart()  const { return cur_dart; }
   void set_cur_dart(edge e)  { cur_dart = e;    }
   void set_hull_dart(edge e) { hull_dart = e;   }

   /*
     edge get_cur_edge()  const { return cur_dart; }
     void set_cur_edge(edge e)  { cur_dart = e;    }
     void set_hull_edge(edge e) { hull_dart = e;   }
     */

};



inline POINT POINT_SET::pos(node v) const
{ return inf(v); }

inline POINT POINT_SET::pos_source(edge e) const
{ return inf(source(e)); }

inline POINT POINT_SET::pos_target(edge e) const
{ return inf(target(e)); }

inline SEGMENT POINT_SET::seg(edge e) const           
{ return SEGMENT(inf(source(e)),inf(target(e))); }

inline LINE POINT_SET::supporting_line(edge e) const           
{ return LINE(inf(source(e)),inf(target(e))); }

inline edge  POINT_SET::get_hull_dart() const
{ return hull_dart; }

inline edge  POINT_SET::get_hull_edge() const
{ return hull_dart; }

inline bool  POINT_SET::is_diagram_dart(edge e) const
{ return (inf(e) & NON_DIAGRAM_DART) == 0; }

inline bool  POINT_SET::is_diagram_edge(edge e) const
{ return POINT_SET::is_diagram_dart(e); }

inline bool  POINT_SET::is_hull_dart(edge e) const
{ return (inf(e) & HULL_DART) != 0; }

inline bool  POINT_SET::is_hull_edge(edge e) const
{ return POINT_SET::is_hull_dart(e); }


inline int POINT_SET::orientation(edge e, POINT p) const
{ return pos(source(e)).orientation(pos(target(e)),p); }

inline int  POINT_SET::dim() const
{ int n = number_of_nodes();
  if (n <= 1) 
    return n - 1;
  else
    return (is_hull_dart(reversal(hull_dart))) ? 1 : 2 ;
}




/*{\Mimplementation
The main ingredients for the implementation are Delaunay flipping, 
segment walking, and plane sweep.

The constructor |POINT_SET(list<POINT> S)| first constructs a 
triangulation of |S| by sweeping and then makes the triangulation Delaunay by
a sequence of Delaunay flips. 

|Locate| walks through the triangulation along the segment from some 
fixed point of $T$ to the query point. |Insert| first locates the point, 
then updates the triangulation locally, and finally performs flips to 
reestablish the Delaunay property. |Delete| deletes the node, 
retriangulates the resulting face, and then performs flips. Nearest 
neighbor searching, circular range queries, and triangular range 
queries insert the query point into the triangulation, then perform 
an appropriate graph search on the triangulation, and finally remove
the query point.

All algorithms show good expected behavior.

For details we refer the reader to the LEDA implementation report 
"Point Sets and Dynamic Delaunay Triangulations".

}*/


LEDA_END_NAMESPACE