git.hungrycats.org Git - xscreensaver/blob - 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