Algorithmic Solutions > LEDA > LEDA Guide > Geometry Algorithms > Delaunay Diagrams > Example

Example Delaunay Diagram

 The following program generates a list `L` of 50 `rat_points` at the corners of square `(-100,-100,100,100)` and computes a (furthest site) Voronoi diagram of `L` represented by the parameterized graph `G`. It also calls `Is_Voronoi_Diagram()` to verify the result. Then it draws the points of `L` and edges of the diagram. The drawing loop needs to distinguish between proper nodes and nodes at infinity. On the right you see a screenshot of the program showing the Delaunay diagram. Clicking on the picture shows the `window` in original size.
```#include <LEDA/core/list.h>
#include <LEDA/geo/rat_point.h>
#include <LEDA/geo/rat_circle.h>
#include <LEDA/geo/random_rat_point.h>
#include <LEDA/graphics/window.h>
#include <LEDA/geo/geo_alg.h>
#include <LEDA/graph/edge_array.h>

using namespace leda;

int main()
{
list<rat_point> L;
random_points_in_square(50,100,L);

GRAPH<rat_circle,rat_point> G;

delaunay_voronoi_kind kind;

VORONOI(L,G);
kind=NEAREST;

//F_VORONOI(L,G);   //Furthest Point Voronoi Diagram
//kind=FURTHEST;

if (Is_Voronoi_Diagram(G,kind))
std::cout << "G is a Voronoi Diagram" << std::endl;
else std::cout << "WARNING: G is no Voronoi Diagram!" << std::endl;

window W;
W.init(-110,110,-110);
W.open(); W.display();
W.set_node_width(2);
W.set_line_width(2);

std::cout << "Nodes of Voronoi diagram" << std::endl;
edge e;
forall_edges(e,G) {
point p=G[e].to_point();W.draw_filled_node(p);
}

std::cout << "Edges of Voronoi diagram" << std::endl;
edge_array<bool> drawn(G,false);
forall_edges(e,G) {
if (drawn[e]) continue;

drawn[G.reversal(e)] = drawn[e] = true;

node v = source(e); node w = target(e);

if (G.outdeg(v) == 1 && G.outdeg(w) == 1) {
//special case: exactly two sites
rat_line l = p_bisector(G[v].point1(),G[v].point3());
W.draw_line(l.to_line(),red);
}

else if (G.outdeg(v) == 1) { //v at infinity
rat_point  cw  = G[w].center();
rat_vector vec = G[v].point3() - G[v].point1();
rat_point  cv  = cw + vec.rotate90();
W.draw_ray(cw.to_point(),cv.to_point(),red);
}

else if (G.outdeg(w) == 1) { //w at infinity
rat_point  cv  = G[v].center();
rat_vector vec = G[w].point3() - G[w].point1();
rat_point  cw  = cv + vec.rotate90();
W.draw_ray(cv.to_point(),cw.to_point(),red);
}

else  { //both v and w proper nodes
rat_point  cv  = G[v].center();
rat_point  cw  = G[w].center();
W.draw_segment(cv.to_point(),cw.to_point(),red);
}
}

W.screenshot("voronoi_diagram");

return 0;
}	     ```

Data Types for 2-D Geometry

Linear Lists

Windows and Panels

Parameterized Graphs

Verification of Geometric Structures

Geometry Algorithms

Geometry

GeoWin

Manual Entries

Manual Page of Geometry Algorithms