point_set.h

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

/*******************************************************************************
+
+  LEDA 4.5  
+
+
+  POINT_SET.h
+
+
+  Copyright (c) 1995-2004
+  by Algorithmic Solutions Software GmbH
+  All rights reserved.
+ 
*******************************************************************************/

// $Revision: 1.4 $  $Date: 2004/02/10 13:57:36 $


#include <LEDA/geo_global_enums.h>

LEDA_BEGIN_NAMESPACE

/*{\Manpage {POINT_SET} {} {Point Sets and Delaunay Triangulations} {T}}*/


/*{\Moptions nextwarning=no}*/
/*{\Mdefinition

There are three instantiations of |POINT_SET|: 
|point_set| (floating point kernel),
|rat_point_set| (rational kernel) and
|real_point_set| (real kernel).
The respective header file name corresponds to the type name (with ``.h''
appended).

An instance $T$ of data type |\Mname| is a planar embedded bidirected
graph (map) representing the {\em Delaunay Triangulation} of its vertex set.
The position of a vertex $v$ is given by |T.pos(v)| and we use 
$S = \{ |T.pos(v)| \mid v \in T \}$ to denote the underlying point set.
Each face of $T$ (except for the outer face) is  a triangle whose 
circumscribing circle does not contain any point of $S$ in its interior.
For every edge $e$, the sequence 
\[e, |T.face_cycle_succ(e)|, |T.face_cycle_succ(T.face_cycle_succ(e))|,\ldots\]
traces the boundary of the face to the left of $e$.
The edges of the outer face of $T$ form the convex hull of $S$; the trace of 
the convex hull is clockwise.
The subgraph obtained from $T$ by removing all diagonals of
co-circular quadrilaterals  is called the {\em Delaunay Diagram}
of $S$.

|\Mname| provides all {\em constant} graph operations, 
e.g., |T.reversal(e)| returns the reversal of edge $e$, |T.all_edges()|
returns the list of all edges of $T$, and |forall_edges(e,T)| iterates over
all edges of $T$. In addition, |\Mname| provides
operations for inserting and deleting points,
point location, nearest neighbor searches, and navigation in both
the triangulation and the diagram.

|\Mname|s are essentially objects of type |GRAPH<POINT,int>|, where the 
node information is the position of the node and the edge information is 
irrelevant. For a graph $G$ of type |GRAPH<POINT,int>| the function
|Is_Delaunay(G)| tests whether $G$ is a Delaunay triangulation of its vertices.

The data type |\Mname| is illustrated by the |point_set_demo| in the 
LEDA demo directory.

Be aware that the nearest neighbor queries for a point (not for a node) and
the range search queries for circles, triangles, and rectangles are non-const 
operations and modify the underlying graph. The set of nodes and edges is 
not changed; however, it is not guaranteed that the underlying Delaunay 
triangulation is unchanged.

}*/

class __exportC POINT_SET : public  GRAPH<POINT,int>
{
protected:

   // for gw_observer
   vector get_position(node v)
   { point p = inf(v).to_point();
     return p.to_vector();
    }


   edge cur_dart;
   edge hull_dart;

   bool check; // functions are checked if true

   // for marking nodes in search procedures
   int cur_mark;
   node_map<int> mark;

   void init_node_marks()
   { mark.init(*this,-1);
     cur_mark = 0;
   }

   void mark_node(node v) const 
   { ((node_map<int>&)mark)[v] = cur_mark; }

   void unmark_node(node v) const 
   { ((node_map<int>&)mark)[v] = cur_mark - 1; }

   bool is_marked(node v)  const { return mark[v] == cur_mark; }

   void unmark_all_nodes() const 
   { ((int&)cur_mark)++; 
     if ( cur_mark == MAXINT)
     ((POINT_SET*)this) -> init_node_marks();  
                                   //cast away constness
   }

   
   void mark_edge(edge e, delaunay_edge_info k) 
   { assign(e,k); }


   //void del_hull_node(node);

   node  new_node(POINT p) 
   { node v = GRAPH<POINT,int>::new_node(p); 
     mark[v] = -1;
     return v;
   }

   edge  new_edge(node v, node w) 
   { return GRAPH<POINT,int>::new_edge(v,w,0); }

   edge  new_edge(edge e, node w) 
   { return GRAPH<POINT,int>::new_edge(e,w,0,0); }

   void  del_node(node v)  { GRAPH<POINT,int>::del_node(v); }
   void  del_edge(edge e)  { GRAPH<POINT,int>::del_edge(e); }



   void init_hull();
   void make_delaunay(list<edge>&);
   void make_delaunay();


   void check_locate(edge answer,const POINT& p) const;


   //bool simplify_face(node v, list<edge>& E);


   void dfs(node s, const CIRCLE& C, list<node>& L) const;
   /* a procedure used in range_search(const CIRCLE& C) */


   void dfs(node s, const POINT& pv, const POINT& p, list<node>& L) const;
   /* a procedure used in range_search(nodev, const POINT& p) */



   void  draw_voro_edge(const CIRCLE& c1, const CIRCLE& c2,
                        void (*draw_edge)(const POINT&,const POINT&),
                        void (*draw_ray) (const POINT&,const POINT&));


public:

   /*{\Mcreation T }*/

   POINT_SET();
   /*{\Mcreate  creates an empty |POINT_SET| |T|.}*/ 

   POINT_SET(const list<POINT>& S); 
   /*{\Mcreate  creates a |POINT_SET| |T| of the points in $S$. 
                If $S$ contains multiple occurrences of points only the last 
                occurrence of each point is retained.}*/


   POINT_SET(const GRAPH<POINT,int>& G);
   /*{\Mcreate  initializes |T| with a copy of $G$.\\
                \precond |Is_Delaunay(G)| is true.}*/

   POINT_SET(const POINT_SET&);

   POINT_SET& operator=(const POINT_SET&);
   ~POINT_SET() {}

   /*{\Moperations 2.5 4.5 }*/

   void  init(const list<POINT>& L);
   /*{\Mop makes |T|  a |POINT_SET| for the points in $S$.}*/



   POINT  pos(node v) const;
   /*{\Mop  returns the position of node $v$. }*/

   POINT  pos_source(edge e) const;
   /*{\Mop  returns the position of $source(e)$. }*/

   POINT  pos_target(edge e) const;
   /*{\Mop  returns the position of $target(e)$. }*/

   SEGMENT seg(edge e) const;
   /*{\Mop   returns the line segment corresponding to edge $e$ 
             (|SEGMENT(T.pos_source(e),T.pos_target(e))|). }*/

   LINE    supporting_line(edge e) const;
   /*{\Mop   returns the supporting line of edge $e$ 
             (|LINE(T.pos_source(e),T.pos_target(e))|). }*/

   int     orientation(edge e, POINT p) const;
   /*{\Mop   returns $orientation(T.seg(e),p)$.}*/

   int     dim() const;
   /*{\Mop   returns $-1$ if $S$ is empty, returns $0$ if $S$
   consists of only one point,     
             returns $1$ if $S$ consists of at least two points 
   and all points in $S$ 
             are collinear, and returns $2$ otherwise.
   }*/

   list<POINT>  points() const;
   /*{\Mop  returns $S$. }*/
   
   bool         get_bounding_box(POINT& lower_left, POINT& upper_right) const;
   /*{\Mop  returns the lower left and upper right corner of the bounding box of |\Mvar|. The operation returns
   |true|, if |\Mvar| is not empty, |false| otherwise. }*/
   
   list<node>   get_convex_hull() const;
   /*{\Mop  returns the convex hull of |\Mvar|.}*/

   edge   get_hull_dart() const;
   /*{\Mop  returns a dart of the outer face  of |T| (i.e., a dart of the 
            convex hull). }*/

   edge   get_hull_edge() const;
   /*{\Mop  as above. }*/

   bool   is_hull_dart(edge e) const;
   /*{\Mop  returns true if $e$ is a dart of the convex hull of |T|, i.e.,
   a dart on the face cycle of the outer face. }*/

   bool   is_hull_edge(edge e) const;
   /*{\Mop  as above. }*/

   bool   is_diagram_dart(edge e) const;
   /*{\Mop  returns true if $e$ is a dart of the Delaunay diagram, i.e., either
   a dart on the convex hull or a dart where the incident triangles have 
   distinct circumcircles.}*/

   bool   is_diagram_edge(edge e) const;
   /*{\Mop  as above. }*/


   edge   d_face_cycle_succ(edge e) const;
   /*{\Mop  returns the face cycle successor of $e$ in the Delaunay diagram 
            of |T|. \precond  $e$ belongs to the Delaunay diagram.}*/

   edge   d_face_cycle_pred(edge e) const;
   /*{\Mop  returns the face cycle predecessor of $e$ in the Delaunay diagram 
            of |T|. \precond  $e$ belongs to the Delaunay diagram.}*/

   bool   empty() { return number_of_nodes() == 0; }
   /*{\Mop  decides whether |T| is empty. }*/

   void   clear() { GRAPH<POINT,int>::clear(); cur_dart = hull_dart = nil; }
   /*{\Mop  makes |T| empty. }*/



   edge   locate(POINT p, edge loc_start = NULL) const;
   /*{\Mop  returns an edge |e| of |T| that contains |p| or that 
   borders the face that contains $p$. In the former case, 
   a hull dart is returned if $p$ lies on the boundary of the convex hull.
   In the latter case we have 
   |T.orientation(e,p) > 0| except if all points of |T| are collinear and 
   |p| lies on the induced line. In this case |target(e)| is visible from 
   |p|. The function returns |nil| if |T| has no edge.
   The optional second argument is an edge of |\Mvar|, where the |locate| 
   operation starts searching. }*/


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

   node   lookup(POINT p, edge loc_start = NULL) const;