pdelaunay

Builds the Delaunay graph from region map.

Synopsis

pdelaunay [-m mask] [rg_in|-] [gr_out|-]

Description

pdelaunay builds the Delaunay graph from the input region map rg_in. A Delaunay triangulation of a vertex set is a triangulation of the vertex set with the property that no vertex in the vertex set falls in the interior of the circumcircle (circle that passes through all three vertices) of any triangle in the triangulation.

Delaunay graph is the dual of the Voronoi diagram, where each element is connected to all elements that share a Voronoi edge. A Voronoī polygon associated to a site Pi is the region Vor(Pi) (each region Vor(Pi) is the set of point (x,y) nearest to the point of Vor(Pi) than any other regions) such as each point of P has Pi as the nearest site.

Seeds given in the region map rg_in are the site of the diagram to be built. There are the nodes of the output graph gr_out. A seed is a region defined by 1 pixel and with a unique label. If the seeds are not by a region with 1 pixel, pdelaunay returns an error.

Each edge weight is set with 1.0.

Inputs

rg_in: a region map that contains the seeds.

Outputs

gr_out: a graph.

Result

Returns SUCCESS or FAILURE.

Examples

Calculates the Delaunay graph from the centers of mass of tangram pieces:

   pbinarization 90 1e30 tangram.pan a.pan
   plabeling 8 a.pan r1.pan
   pcenterofmass r1.pan r2.pan
   pdelaunay r2.pan g.pan

C++ prototype

Errc PDelaunay( const Reg2d &rg_in, Graph2d &gr_out );

Version française

Construction du graphe de Delaunay discret.

Author: Sébastien Bougleux