delaunay.c File Reference

delaunay triangulation More...

---

Detailed Description

delaunay triangulation

Usage: delaunay in.list [mask.pgm] out.list

Description: Reads a point list in file in.list under the following format:

  
    b <n>         n <n>    
    x1 y1         x1 y1 v1
    x2 y2   ou    x2 y2 v2
    ...           ...
    xn yn         xn yn vn

Computes a Delaunay triangulation and stores the resulting graph into file out.graph under the following format:

    G <n>
    x1 y1 v1 ec1 ns1 s11 s12 ... s1ns1
    x2 y2 v2 ec2 ns2 s21 s22 ... s1ns2
    ...
    xn yn vn ecn nsn sn1 sn2 ... s1nsn

where xi, yi are the coordinates of the ith vertex, vi is the associated value (if given in the input file), eci is a int32_t which indicates whether the vertex i belongs to the convex hull, nsi denotes the number of adjacent vertices, and si1 si2 ... sins1 is the list of the indexes of the adjacent vertices (counted from 0).

If the optional parameter mask.pgm is given, then it must be a binary byte image. Any edge of the triangulation which intersects the mask will be discarded.

Types supported: byte 2D

See also: drawtriangulation.c

Category: geo

Warning:

algorithm in O(n^2)

Author:

Michel Couprie, Laurent Mercier