/*******************************************************************************
+
+  LEDA 3.5
+
+  plane_alg.h
+
+  This file is part of the LEDA research version (LEDA-R) that can be 
+  used free of charge in academic research and teaching. Any commercial
+  use of this software requires a license which is distributed by the
+  LEDA Software GmbH, Postfach 151101, 66041 Saarbruecken, FRG
+  (fax +49 681 31104).
+
+  Copyright (c) 1991-1997  by  Max-Planck-Institut fuer Informatik
+  Im Stadtwald, 66123 Saarbruecken, Germany     
+  All rights reserved.
+ 
*******************************************************************************/
#ifndef LEDA_PLANE_ALG_H
#define LEDA_PLANE_ALG_H

#if !defined(LEDA_ROOT_INCL_ID)
#define LEDA_ROOT_INCL_ID 350094
#include <LEDA/REDEFINE_NAMES.h>
#endif

/*{\Manpage {plane_alg} {} {Plane Algorithms} }*/

/*{\Mtext
\bigskip
All functions listed in this section work for geometric objects based
on both floating-point and exact (rational) arithmetic. In particular,
$point$ can be replace by $rat\_point$, $segment$ by $rat\_segment$,
and $circle$ by $rat\_circle$. {\bf Note} that only the $rat$-versions
will produce correct results for all inputs. 
}*/

#include <LEDA/graph.h>


enum delaunay_edge_info{ DIAGRAM_EDGE = 0, NON_DIAGRAM_EDGE = 1, HULL_EDGE = 2};


#if !defined(NO_FLOAT_ALGORITHMS)

#include <LEDA/point.h>
#include <LEDA/segment.h>
#include <LEDA/line.h>
#include <LEDA/circle.h>


/*{\Mtext
\bigskip
$\bullet$ {\bf Triangulations}
\setopdims 1 1.9 
}*/


edge TRIANGULATE_POINTS(const list<point>& L, GRAPH<point,int>& T);
/*{\Mfuncl computes a triangulation (planar map) $T$ of the points in $L$ and 
           returns an edge of the outer face (convex hull). }*/

int DELAUNAY_FLIPPING(GRAPH<point,int>& T, int f=1);
int DELAUNAY_FLIPPING(GRAPH<point,int>& T, list<edge> L, int f=1);
int DELAUNAY_FLIP  (const list<point>&,GRAPH<point,int>&);
int F_DELAUNAY_FLIP(const list<point>&,GRAPH<point,int>&);
void DELAUNAY_STOLFI(const list<point>&,GRAPH<point,int>&,bool=false);
void DELAUNAY_DWYER (const list<point>&,GRAPH<point,int>&,bool=false);


void DELAUNAY_TRIANG(const list<point>& L, GRAPH<point,int>& DT);
/*{\Mfuncl computes the delaunay triangulation $DT$ of the points in $L$. }*/

void DELAUNAY_DIAGRAM(const list<point>& L, GRAPH<point,int>& DD);
/*{\Mfuncl computes the delaunay diagram $DD$ of the points in $L$. }*/



void F_DELAUNAY_TRIANG(const list<point>& L, GRAPH<point,int>& FDT);
/*{\Mfuncl computes the furthest point delaunay triangulation $FDT$ of the 
           points in $L$. }*/

void F_DELAUNAY_DIAGRAM(const list<point>& L, GRAPH<point,int>& FDD);
/*{\Mfuncl computes the furthest point delaunay diagram $FDD$ of the 
           points in $L$. }*/



void MIN_SPANNING_TREE(const list<point>& L, GRAPH<point,int>& T);
/*{\Mfuncl computes the Euclidian minimum spanning tree $T$ of the 
           points in $L$. }*/




/*{\Mtext
\bigskip
$\bullet$ {\bf Line segment intersection}
}*/

void SWEEP_SEGMENTS(const list<segment>& L, GRAPH<point,segment>& G, 
                                                    bool embed=false);

/*{\Mfuncl
SWEEP\_SEGMENTS takes a list of segments $L$ as input and computes 
the planar graph $G$ induced by the set of straight line segments
in $L$. The nodes of $G$ are all endpoints and all proper intersection
points of segments in $L$. The edges of $G$ are the maximal relatively open
subsegments of segments in $L$ that contain no node of $G$. The edges are
directed as the corresponding segments. If the flag $embed$ is true,
|SWEEP_SEGMENTS| computes the corresponding planar map. 
The algorithm (\cite{BO79}) runs in time $O((n+s)\log n)$ where $n$ is the 
number of segments and $s$ is the number of vertices of the graph $G$.  }*/

void SWEEP_SEGMENTS(const list<segment>&, list<point>&);


void MULMULEY_SEGMENTS(const list<segment>& L, GRAPH<point,segment>& G);

void BALABAN_SEGMENTS(const list<segment>& L, 
                               void (*rep_func)(const segment&,const segment&));

void TRIVIAL_SEGMENTS(const list<segment>& L, 
                               void (*rep_func)(const segment&,const segment&));



void SEGMENT_INTERSECTION(const list<segment>& L, list<point>& P);
/*{\Mfuncl
SEGMENT\_INTERSECTION takes a list of segments $L$ as input and computes 
the list of intersection points between all segments in $L$.
The algorithm (\cite{BO79}) has running time $O((n+k)\log n)$, 
where $n$ is the number of segments and $k$ is the number of intersections.
}*/



/*{\Mtext
\bigskip
$\bullet$ {\bf Convex Hulls}
\setopdims 2.65 0.5 
}*/


list<point> CONVEX_HULL(list<point>);
/*{\Mfuncl
CONVEX\_HULL takes as argument a list of points and returns the polygon
representing the convex hull of $L$. It is based on a randomized incremental 
algorithm. 
Running time: $O(n\log n)$ (with high probability), where $n$ is the number 
of points.
}*/


/*{\Mtext
\bigskip
$\bullet$ {\bf Closest Pairs}
\setopdims 1.3 1.6 
}*/

double CLOSEST_PAIR(list<point>& L, point& r1, point& r2);
/*{\Mfuncl
CLOSEST\_PAIR takes as input a list of points $L$. It computes a pair
of points $r1,r2 \in L$ with minimal euclidean distance and returns the
squared distance between $r1$ and $r2$. 
The algorithm (\cite{???}) has running time $O(n\log n)$ 
where $n$ is the number of input points.
}*/



/*{\Mtext
\bigskip
$\bullet$ {\bf Voronoi Diagrams}
}*/

void DELAUNAY_TO_VORONOI(const GRAPH<point,int>& DT, 
                                   GRAPH<circle,point>& VD);

void VORONOI(const list<point>& L, GRAPH<circle,point>& VD);
/*{\Mfuncl 
VORONOI takes as input a list of points (sites) |L|. It computes a directed 
graph $VD$ representing the planar subdivision defined by the Voronoi diagram 
of |L|. For each node $v$ of |VD| $G$.inf($v$) is the corresponding Voronoi 
vertex ($point$) and for each edge $e$  $G$.inf($e$) is the site ($point$) 
whose Voronoi region is bounded by $e$. 
The algorithm has running time $O(n^2)$ in the worst case and $O(n\log n)$ 
with high probability, where $n$ is the number of sites.
}*/


void VORONOI(const list<point>& L, double R, GRAPH<point,point>& VD);


void F_DELAUNAY_TO_VORONOI(const GRAPH<point,int>& DT, 
                                     GRAPH<circle,point>& VD);


void F_VORONOI(const list<point>& L, GRAPH<circle,point>& FVD);
/*{\Mfuncl computes the farthest point Voronoi Diagram |FVD| of the points
           in |L|. }*/


circle LARGEST_EMPTY_CIRCLE(const list<point>& L);
/*{\Mfuncl computes a largest circle whose center lies inside the convex
           hull of |L| that contains no point of |L| in its interior. }*/ 

circle SMALLEST_ENCLOSING_CIRCLE(const list<point>& L);
/*{\Mfuncl computes a smallest circle containing all points of |L| in 
           its interior. }*/ 

void ALL_EMPTY_CIRCLES(const list<point>& L, list<circle>& CL);
/*{\Mfuncl computes the list |CL| of all empty circles passing through three
           or more points of |L|. }*/

void ALL_ENCLOSING_CIRCLES(const list<point>& L, list<circle>& CL);
/*{\Mfuncl computes the list |CL| of all enclosing circles passing through three
           or more points of |L|. }*/


bool MIN_AREA_ANNULUS(const list<point>& L, 
                                  point& center, point& ipoint, point& opoint);
/*{\Mfuncl computes the minimum area annulus containing the points of |L|. 
           The annulus is returned by its |center| and a point 
           on the inner and the outer circle respectively.}*/

bool MIN_WIDTH_ANNULUS(const list<point>& L, 
                                  point& center, point& ipoint, point& opoint);
/*{\Mfuncl computes the minimum width annulus containing the points of |L|. 
           The annulus is returned by its |center| and a point 
           on the inner and the outer circle respectively.}*/


/*{\Mtext
\bigskip
$\bullet$ {\bf Miscellaneous Functions}
}*/



bool Is_Simple_Polygon(const list<point>& L);
/*{\Mfuncl
takes as input a list of points $L$ and returns $true$ if $L$
is the vertex sequence of a simple polygon and false otherwise. 
The algorithms has running time $O(n\log n)$, where $n$ is the
number of points in $L$. }*/

#endif



#if !defined(NO_RAT_ALGORITHMS)

#include <LEDA/rat_point.h>
#include <LEDA/rat_segment.h>
#include <LEDA/rat_line.h>
#include <LEDA/rat_circle.h>


edge TRIANGULATE_POINTS(const list<rat_point>&,GRAPH<rat_point,int>&);

int DELAUNAY_FLIPPING(GRAPH<rat_point,int>& T, int f=1);
int DELAUNAY_FLIPPING(GRAPH<rat_point,int>& T, list<edge> L,int f=1);

int DELAUNAY_FLIP  (const list<rat_point>&,GRAPH<rat_point,int>&);
int F_DELAUNAY_FLIP(const list<rat_point>&,GRAPH<rat_point,int>&);

void DELAUNAY_STOLFI(const list<rat_point>&,GRAPH<rat_point,int>&,bool=false);
void DELAUNAY_DWYER (const list<rat_point>&,GRAPH<rat_point,int>&,bool=false);


void DELAUNAY_TRIANG(const list<rat_point>& L,GRAPH<rat_point,int>& G);
void DELAUNAY_DIAGRAM(const list<rat_point>& L,GRAPH<rat_point,int>& G);


void F_DELAUNAY_TRIANG(const list<rat_point>& L, GRAPH<rat_point,int>& G);
void F_DELAUNAY_DIAGRAM(const list<rat_point>& L, GRAPH<rat_point,int>& G);



void MIN_SPANNING_TREE(const list<rat_point>& L, GRAPH<rat_point,int>& T);


void SWEEP_SEGMENTS(const list<rat_segment>&, GRAPH<rat_point,rat_segment>&, bool=false);

void SWEEP_SEGMENTS(const list<rat_segment>&, list<rat_point>&);



void MULMULEY_SEGMENTS(const list<rat_segment>& L, 
                                 GRAPH<rat_point,rat_segment>& G);

void BALABAN_SEGMENTS(const list<rat_segment>& L,
                      void (*rep_func)(const rat_segment&, const rat_segment&));

void TRIVIAL_SEGMENTS(const list<rat_segment>& L,
                      void (*rep_func)(const rat_segment&, const rat_segment&));

list<rat_point> CONVEX_HULL(list<rat_point>);

rational CLOSEST_PAIR(list<rat_point>& L, rat_point& r1, rat_point& r2);


void DELAUNAY_TO_VORONOI(const GRAPH<rat_point,int>& DT, 
                                   GRAPH<rat_circle,rat_point>& VD);

void VORONOI(const list<rat_point>& L, GRAPH<rat_circle,rat_point>& VD);

void F_DELAUNAY_TO_VORONOI(const GRAPH<rat_point,int>& DT, 
                                   GRAPH<rat_circle,rat_point>& VD);

void F_VORONOI(const list<rat_point>& L, GRAPH<rat_circle,rat_point>& VD);


rat_circle LARGEST_EMPTY_CIRCLE     (const list<rat_point>& L);
rat_circle SMALLEST_ENCLOSING_CIRCLE(const list<rat_point>& L);

void ALL_EMPTY_CIRCLES (const list<rat_point>&, list<rat_circle>&);
void ALL_ENCLOSING_CIRCLES(const list<rat_point>&, list<circle>&);


bool MIN_AREA_ANNULUS(const list<rat_point>& L, rat_point& center, 
                                                          rat_point& ipoint, 
                                                          rat_point& opoint);

bool MIN_WIDTH_ANNULUS(const list<rat_point>& L, rat_point& center, 
                                                           rat_point& ipoint,
                                                           rat_point& opoint);


bool Is_Simple_Polygon(const list<rat_point>& L);

#endif



#if LEDA_ROOT_INCL_ID == 350094
#undef LEDA_ROOT_INCL_ID
#include <LEDA/UNDEFINE_NAMES.h>
#endif

#endif
