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

Example Delaunay Diagram

The following program generates a list L of four rat_points at the corners of square (-75,-75,75,75) and computes a (furthest site) Delaunay diagram of L represented by the parameterized graph G. It also calls Is_Delaunay_Diagram() to verify the result. Then it draws the points of L and edges of the diagram.

On the right you see a screenshot of the program showing the Delaunay diagram. Clicking on the picture shows the window in original size.

Picture of Delaunay Diagram
#include <LEDA/core/list.h>
#include <LEDA/geo/rat_point.h>
#include <LEDA/graphics/window.h>
#include <LEDA/geo/geo_alg.h>

using namespace leda;

int main()
{
  list<rat_point> L;

  L.append(rat_point(-75,-75));
  L.append(rat_point(-75,75));
  L.append(rat_point(75,-75));
  L.append(rat_point(75,75));

  GRAPH<rat_point,int> G;

  delaunay_voronoi_kind kind;

  DELAUNAY_DIAGRAM(L,G);
  kind=NEAREST;

  //F_DELAUNAY_DIAGRAM(L,G);   //Furthest Point Delaunay Diagram
  //kind=FURTHEST;
  
  if (Is_Delaunay_Diagram(G,kind)) 
	  std::cout << "G is a Delaunay Diagram" << std::endl;
  else std::cout << "WARNING: G is no Delaunay Diagram!" << std::endl;

  window W;
  W.init(-100,100,-100);
  W.open(); W.display();
  W.set_line_width(3);
  
  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 Diagram
    point p=G[G.source(e)].to_point();
    point q=G[G.target(e)].to_point();
    W.draw_edge(p,q,red);
  }
  W.read_mouse();

  W.screenshot("delaunay_diagram");

  return 0;
}	 

See also:

Data Types for 2-D Geometry

Linear Lists

Windows and Panels

Parameterized Graphs

Verification of Geometric Structures


Delaunay Diagrams

Geometry Algorithms

Geometry

Graphs

GeoWin


Manual Entries

Manual Page of Geometry Algorithms




Please send any suggestions, comments or questions to leda@algorithmic-solutions.com
© Copyright 2001-2003, Algorithmic Solutions Software GmbH