Plane Algorithms (plane_alg)

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. Note that only the rat-versions will produce correct results for all inputs.

$\bullet$ Triangulations

edge	TRIANGULATE_POINTS(list<point> L, GRAPH<point,int>& T)
		computes a triangulation (planar map) T of the points in L and returns an edge of the outer face (convex hull).
void	DELAUNAY_TRIANG(list<point> L, GRAPH<point,int>& DT)
		computes the delaunay triangulation DT of the points in L.
void	DELAUNAY_DIAGRAM(list<point> L, GRAPH<point,int>& DD)
		computes the delaunay diagram DD of the points in L.
void	F_DELAUNAY_TRIANG(list<point> L, GRAPH<point,int>& FDT)
		computes the furthest point delaunay triangulation FDT of the points in L.
void	F_DELAUNAY_DIAGRAM(list<point> L, GRAPH<point,int>& FDD)
		computes the furthest point delaunay diagram FDD of the points in L.
void	MIN_SPANNING_TREE(list<point> L, GRAPH<point,int>& T)
		computes the Euclidian minimum spanning tree T of the points in L.

$\bullet$ Line segment intersection

void	SWEEP_SEGMENTS(list<segment> L, GRAPH<point,segment>& G, bool embed=false)
		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 ([10]) 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	MULMULEY_SEGMENTS(list<segment> L, GRAPH<point,segment>& G, bool embed=false)
		MULMULEY_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. There are three options for the kind of the resulting graph. If MULMULEY_SEGMENTS gets an undirected graph G, it computes the corresponding undirected planar map. If G is directed, the output depends on the value of flag embed. If embed has value true, it computes the corresponding planar map. Otherwise, the edges are directed as the corresponding segments. The computation follows the incremental algorithm of Mulmuley ([62]) whose expected running time is O(s + n log n) where n is the number of segments and s is the number of vertices of the graph G.
void	SEGMENT_INTERSECTION(list<segment> L, void (*report)(segment, segment ))
		takes a list of segments L as input and executes for every pair (s_1,s_2) of intersecting segments report(s_1,s_2). The algorithm ([6]) has running time O(n log^2 n + k), where n is the number of segments and k is the number intersecting pairs of segments.
void	SEGMENT_INTERSECTION(list<segment> L, list<point>& S)
		takes a list of segments L as input, computes the set of (proper) intersection points between all segments in L and stores this set in S. The algorithm ([10]) has running time O((L+S)log L).

$\bullet$ Convex Hulls

list<point>	CONVEX_HULL(list<point> L)
		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(nlog n) (with high probability), where n is the number of points.

$\bullet$ Closest Pairs

double	CLOSEST_PAIR(list<point>& L, point& r1, point& r2)
		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 ([69]) has running time O(nlog n) where n is the number of input points.

$\bullet$ Voronoi Diagrams

void	VORONOI(list<point> L, GRAPH<circle,point>& VD)
		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[v] is the corresponding Voronoi vertex (point) and for each edge e G[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(nlog n) with high probability, where n is the number of sites.
void	F_VORONOI(list<point> L, GRAPH<circle,point>& FVD)
		computes the farthest point Voronoi Diagram FVD of the points in L.
circle	LARGEST_EMPTY_CIRCLE(list<point> L)
		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(list<point> L)
		computes a smallest circle containing all points of L in its interior.
void	ALL_EMPTY_CIRCLES(list<point> L, list<circle>& CL)
		computes the list CL of all empty circles passing through three or more points of L.
void	ALL_ENCLOSING_CIRCLES(list<point> L, list<circle>& CL)
		computes the list CL of all enclosing circles passing through three or more points of L.
bool	MIN_AREA_ANNULUS(list<point> L, point& center, point& ipoint, point& opoint)
		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(list<point> L, point& center, point& ipoint, point& opoint)
		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.

$\bullet$ Miscellaneous Functions

bool	Is_Simple_Polygon(list<point> L)
		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(nlog n), where n is the number of points in L.

$\bullet$ Properties of Geometric Graphs

We give procedures to check properties of geometric graphs. A geometric graph is a straight-line embedded map. A geometric graph is of type GRAPH<POINT,etype> where POINT is any of the two-dimensional point types and etype is an arbitrary type. The position of any node v is given by G[v]. In the functions below we use geo_graph as a template parameter which can stand for any such type.

bool	Is_CCW_Ordered(geo_graph G)
		returns true if for all nodes v the neighbors of v are in increasing counter-clockwise order around v.
bool	Is_CCW_Ordered_Plane_Map(geo_graph G)
		Equivalent to Is_Plane_Map(G) and Is_CCW_Ordered(G).
void	SORT_EDGES(geo_graph& G)	Reorders the edges of G such that for every node v the edges in A(v) are in non-decreasing order by angle.
bool	Is_CCW_Convex_Face_Cycle(geo_graph G, edge e)
		returns true if the face cycle of G containing e defines a counter-clockwise convex polygon, i.e, if the face cycle forms a cyclically increasing sequence of edges according to the compare-by-angles ordering.
bool	Is_CCW_Weakly_Convex_Face_Cycle(geo_graph G, edge e)
		returns true if the face cycle of G containing e defines a counter-clockwise weakly convex polygon, i.e, if the face cycle forms a cyclically non-decreasing sequence of edges according to the compare-by-angles ordering.
bool	Is_CW_Convex_Face_Cycle(geo_graph G, edge e)
		returns true if the face cycle of G containing e defines a clockwise convex polygon, i.e, if the face cycle forms a cyclically decreasing sequence of edges according to the compare-by-angles ordering.
bool	Is_CW_Weakly_Convex_Face_Cycle(geo_graph G, edge e)
		returns true if the face cycle of G containing e defines a clockwise weakly convex polygon, i.e, if the face cycle forms a cyclically non-increasing sequence of edges according to the compare-by-angles ordering.
bool	Is_Convex_Subdivision(geo_graph G)
		returns true if G is a convex planar subdivision.
bool	Is_Triangulation(geo_graph G)
		returns true if G is convex planar subdivision in which every bounded face is a triangle or if all nodes of G lie on a common line.

The next tests check Delaunay triangulations and Voronoi diagrams of point sites. These diagrams come in two kinds: nearest or furthest. An appropriate enumeration type delaunay_voronoi_kind with members NEAREST and FURTHEST is defined in plane_alg.h.

bool	Is_Delaunay_Triangulation(GRAPH<POINT,int> G, delaunay_voronoi_kind kind)
		checks whether G is a nearest (kind = NEAREST) or furthest (kind = FURTHEST) site Delaunay triangulation of its vertex set. G is a Delaunay triangulation iff it is a triangulation and all triangles have the Delaunay property. A triangle has the Delaunay property if no vertex of an adjacent triangle is contained in the interior (kind = NEAREST) or exterior (kind = FURTHEST) of the triangle.
bool	Is_Delaunay_Diagram(GRAPH<POINT,int> G, delaunay_voronoi_kind kind)
		checks whether G is a nearest (kind = NEAREST) or furthest (kind = FURTHEST) site Delaunay diagram of its vertex set. G is a Delaunay diagram if it is a convex subdivision, if the vertices of any bounded face are co-circular, and if every triangulation of G is a Delaunay triangulation.
bool	Is_Voronoi_Diagram(GRAPH<CIRCLE,POINT> G, delaunay_voronoi_kind kind)
		checks whether G represents a nearest (kind = NEAREST) or furthest (kind = FURTHEST) site Voronoi diagram. Voronoi diagrams of point sites are represented as planar maps as follows: There is a vertex for each vertex of the Voronoi diagram and, in addition, a vertex ``at infinity'' for each ray of the Voronoi diagram. Vertices at infinity have degree one. The edges of the graph correspond to the edges of the Voronoi diagram. The chapter on Voronoi diagrams of the LEDA-book [58] contains more details. Each edge is labeled with the site (class POINT) owning the region to its left and each vertex is labeled with a triple of points (= the three defining points of a CIRCLE). For a ``finite'' vertex the three points are any three sites associated with regions incident to the vertex (and hence the center of the circle is the position of the vertex in the plane) and for a vertex at infinity the three points are collinear and the first point and the third point of the triple are the sites whose regions are incident to the vertex at infinity. Let a and c be the first and third point of the triple respectively; a and c encode the geometric position of the vertex at infinity as follows: the vertex lies on the perpendicular bisector of a and c and to the left of the segment ac.