From http://www.jwz.org/xscreensaver/xscreensaver-5.40.tar.gz
[xscreensaver] / hacks / delaunay.h
1 /* Triangulate
2    Efficient Triangulation Algorithm Suitable for Terrain Modelling
3    or
4    An Algorithm for Interpolating Irregularly-Spaced Data
5    with Applications in Terrain Modelling
6
7    Written by Paul Bourke
8    Presented at Pan Pacific Computer Conference, Beijing, China.
9    January 1989
10    Abstract
11
12    A discussion of a method that has been used with success in terrain
13    modelling to estimate the height at any point on the land surface
14    from irregularly distributed samples. The special requirements of
15    terrain modelling are discussed as well as a detailed description
16    of the algorithm and an example of its application.
17
18    http://paulbourke.net/papers/triangulate/
19    http://paulbourke.net/papers/triangulate/triangulate.c
20  */
21
22 #ifndef __DELAUNAY_H__
23 #define __DELAUNAY_H__
24
25 #ifdef HAVE_CONFIG_H
26 # include "config.h"
27 #endif /* HAVE_CONFIG_H */
28
29 typedef struct {
30    double x,y,z;
31 } XYZ;
32
33 typedef struct {
34    int p1,p2,p3;
35 } ITRIANGLE;
36
37 /*
38    Takes as input NV vertices in array pxyz
39    Returned is a list of ntri triangular faces in the array v
40    These triangles are arranged in a consistent clockwise order.
41    The triangle array 'v' should be malloced to 3 * nv
42    The vertex array pxyz must be big enough to hold 3 more points
43    The vertex array must be sorted in increasing x values
44  */
45 extern int delaunay (int nv, XYZ *pxyz, ITRIANGLE *v, int *ntri);
46
47 /* qsort(p,nv,sizeof(XYZ), delaunay_xyzcompare); */
48 extern int delaunay_xyzcompare (const void *v1, const void *v2);
49
50
51 #endif /* __DELAUNAY_H__ */
52