delaunay.h (2418B)
1 #ifndef DELAUNAY_H 2 #define DELAUNAY_H 3 4 /* 5 ** delaunay.c : compute 2D delaunay triangulation in the plane. 6 ** Copyright (C) 2005 Wael El Oraiby <wael.eloraiby@gmail.com> 7 ** 8 ** 9 ** This program is free software: you can redistribute it and/or modify 10 ** it under the terms of the GNU Affero General Public License as 11 ** published by the Free Software Foundation, either version 3 of the 12 ** License, or (at your option) any later version. 13 ** 14 ** This program is distributed in the hope that it will be useful, 15 ** but WITHOUT ANY WARRANTY; without even the implied warranty of 16 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 17 ** GNU Affero General Public License for more details. 18 ** 19 ** You should have received a copy of the GNU Affero General Public License 20 ** along with this program. If not, see <http://www.gnu.org/licenses/>. 21 */ 22 23 24 typedef double real; 25 26 typedef struct { 27 real x, y; 28 } del_point2d_t; 29 30 typedef struct { 31 /** input points count */ 32 unsigned int num_points; 33 34 /** the input points */ 35 del_point2d_t* points; 36 37 /** number of returned faces */ 38 unsigned int num_faces; 39 40 /** the faces are given as a sequence: num verts, verts indices, num verts, verts indices... 41 * the first face is the external face */ 42 unsigned int* faces; 43 } delaunay2d_t; 44 45 /* 46 * build the 2D Delaunay triangulation given a set of points of at least 3 points 47 * 48 * @points: point set given as a sequence of tuple x0, y0, x1, y1, .... 49 * @num_points: number of given point 50 * @preds: the incircle predicate 51 * @faces: the triangles given as a sequence: num verts, verts indices, num verts, verts indices. 52 * Note that the first face is the external face 53 * @return: the created topology 54 */ 55 delaunay2d_t* delaunay2d_from(del_point2d_t *points, unsigned int num_points); 56 57 /* 58 * release a delaunay2d object 59 */ 60 void delaunay2d_release(delaunay2d_t* del); 61 62 63 typedef struct { 64 /** input points count */ 65 unsigned int num_points; 66 67 /** input points */ 68 del_point2d_t* points; 69 70 /** number of triangles */ 71 unsigned int num_triangles; 72 73 /** the triangles indices v0,v1,v2, v0,v1,v2 .... */ 74 unsigned int* tris; 75 } tri_delaunay2d_t; 76 77 /** 78 * build a tri_delaunay2d_t out of a delaunay2d_t object 79 */ 80 tri_delaunay2d_t* tri_delaunay2d_from(delaunay2d_t* del); 81 82 /** 83 * release a tri_delaunay2d_t object 84 */ 85 void tri_delaunay2d_release(tri_delaunay2d_t* tdel); 86 87 #ifdef __cplusplus 88 } 89 #endif 90 91 #endif // DELAUNAY_H