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

## Example Delaunay Triangulation

The following program generates a ```list L``` of 25 `rat_points` in the square `(-100,-100,100,100)` and computes a (furthest site) Delaunay triangulation of `L` represented by the parametrized graph `G`. It also calls `Is_Delaunay_Triangulation()` to verify the result. Then it draws the points of `L` and edges of the triangulation in black. Finally it shows the convex hull by drawing the points and edges on the convex hull in red.
 On the right you see a screenshot of the program showing a Delaunay triangulation of a set of points in the plane, the points and edges on the convex hull are drawn in red. Clicking on the picture shows the `window` in original size. On the right you see a screenshot of the program showing a furthest site Delaunay triangulation of a set of points in the plane, the points and edges on the convex hull are drawn in red. For the furthest site Delaunay diagram all points need to lie on the convex hull. Clicking on the picture shows the `window` in original size.
```#include <LEDA/core/list.h>
#include <LEDA/geo/rat_point.h>
#include <LEDA/geo/random_rat_point.h>
#include <LEDA/graphics/window.h>
#include <LEDA/geo/geo_alg.h>

using namespace leda;

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

GRAPH<rat_point,int> G;

delaunay_voronoi_kind kind;

DELAUNAY_TRIANG(L,G);
kind=NEAREST;

//L=CONVEX_HULL(L);
//F_DELAUNAY_TRIANG(L,G);   //Furthest Point Delaunay Triangulation
//kind=FURTHEST;

if (Is_Delaunay_Triangulation(G,kind))
std::cout << "G is a Delaunay Triangulation" << std::endl;
else std::cout << "WARNING: G is no Delaunay Triangulation!" << std::endl;

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

rat_point p;  //draw points in L
forall(p,L) {W.draw_filled_node(p.to_point(),black);}

edge e;
forall_edges(e,G) { //Delaunay Triangulation
point p=G[G.source(e)].to_point();
point q=G[G.target(e)].to_point();
W.draw_edge(p,q);
}

W.set_line_width(2);
forall_edges(e,G) {  //convex hull
point p=G[G.source(e)].to_point();
point q=G[G.target(e)].to_point();
if (G[e]==2) W.draw_edge(p,q,red);
}

W.screenshot("delaunay_triangulation");

return 0;
}	    ```

Data Types for 2-D Geometry

Convex Hulls

Linear Lists

Windows and Panels

Parameterized Graphs

Verification of Geometric Structures

Geometry Algorithms

Geometry

GeoWin

### Manual Entries

Manual Page of Geometry Algorithms