37 #ifdef HAS_LIBQHULL_INCLUDE
38 #include <libqhull/qhull_a.h>
40 #include <qhull/qhull_a.h>
59 static void tio_init(
struct triangulateio* tio )
61 tio->pointlist = NULL;
62 tio->pointattributelist = NULL;
63 tio->pointmarkerlist = NULL;
64 tio->numberofpoints = 0;
65 tio->numberofpointattributes = 0;
66 tio->trianglelist = NULL;
67 tio->triangleattributelist = NULL;
68 tio->trianglearealist = NULL;
69 tio->neighborlist = NULL;
70 tio->numberoftriangles = 0;
71 tio->numberofcorners = 0;
72 tio->numberoftriangleattributes = 0;
74 tio->segmentmarkerlist = NULL;
75 tio->numberofsegments = 0;
77 tio->numberofholes = 0;
78 tio->regionlist = NULL;
79 tio->numberofregions = 0;
81 tio->edgemarkerlist = NULL;
83 tio->numberofedges = 0;
86 static void tio_destroy(
struct triangulateio* tio )
88 if ( tio->pointlist != NULL )
89 free( tio->pointlist );
90 if ( tio->pointattributelist != NULL )
91 free( tio->pointattributelist );
92 if ( tio->pointmarkerlist != NULL )
93 free( tio->pointmarkerlist );
94 if ( tio->trianglelist != NULL )
95 free( tio->trianglelist );
96 if ( tio->triangleattributelist != NULL )
97 free( tio->triangleattributelist );
98 if ( tio->trianglearealist != NULL )
99 free( tio->trianglearealist );
100 if ( tio->neighborlist != NULL )
101 free( tio->neighborlist );
102 if ( tio->segmentlist != NULL )
103 free( tio->segmentlist );
104 if ( tio->segmentmarkerlist != NULL )
105 free( tio->segmentmarkerlist );
106 if ( tio->holelist != NULL )
107 free( tio->holelist );
108 if ( tio->regionlist != NULL )
109 free( tio->regionlist );
110 if ( tio->edgelist != NULL )
111 free( tio->edgelist );
112 if ( tio->edgemarkerlist != NULL )
113 free( tio->edgemarkerlist );
114 if ( tio->normlist != NULL )
115 free( tio->normlist );
144 static void tio2delaunay(
struct triangulateio* tio_out,
delaunay* d )
154 assert( tio_out->numberofpoints == d->
npoints );
157 for ( i = 0, j = 0; i < d->
npoints; ++i )
161 if ( p->
x < d->
xmin )
163 if ( p->
x > d->
xmax )
165 if ( p->
y < d->
ymin )
167 if ( p->
y > d->
ymax )
172 fprintf( stderr,
"input:\n" );
173 for ( i = 0, j = 0; i < d->
npoints; ++i )
177 fprintf( stderr,
" %d: %15.7g %15.7g %15.7g\n", i, p->
x, p->
y, p->
z );
193 fprintf( stderr,
"triangles:\n" );
201 t->
vids[0] = tio_out->trianglelist[offset];
202 t->
vids[1] = tio_out->trianglelist[offset + 1];
203 t->
vids[2] = tio_out->trianglelist[offset + 2];
205 n->
tids[0] = tio_out->neighborlist[offset];
206 n->
tids[1] = tio_out->neighborlist[offset + 1];
207 n->
tids[2] = tio_out->neighborlist[offset + 2];
212 fprintf( stderr,
" %d: (%d,%d,%d)\n", i, t->
vids[0], t->
vids[1], t->
vids[2] );
219 for ( j = 0; j < 3; ++j )
224 for ( i = 0; i < d->
npoints; ++i )
237 for ( j = 0; j < 3; ++j )
239 int vid = t->
vids[j];
246 if ( tio_out->edgelist != NULL )
248 d->
nedges = tio_out->numberofedges;
249 d->
edges = malloc( d->
nedges * 2 * sizeof (
int ) );
250 memcpy( d->
edges, tio_out->edgelist, d->
nedges * 2 * sizeof (
int ) );
269 struct triangulateio tio_in;
270 struct triangulateio tio_out;
271 char cmd[64] =
"eznC";
274 assert(
sizeof ( REAL ) ==
sizeof (
double ) );
284 tio_in.pointlist = malloc( np * 2 *
sizeof (
double ) );
285 tio_in.numberofpoints = np;
286 for ( i = 0, j = 0; i < np; ++i )
288 tio_in.pointlist[j++] = points[i].
x;
289 tio_in.pointlist[j++] = points[i].
y;
294 tio_in.segmentlist = malloc( ns * 2 *
sizeof (
int ) );
295 tio_in.numberofsegments = ns;
296 memcpy( tio_in.segmentlist, segments, ns * 2 * sizeof (
int ) );
301 tio_in.holelist = malloc( nh * 2 *
sizeof (
double ) );
302 tio_in.numberofholes = nh;
303 memcpy( tio_in.holelist, holes, nh * 2 * sizeof (
double ) );
306 tio_init( &tio_out );
321 triangulate( cmd, &tio_in, &tio_out, NULL );
329 tio2delaunay( &tio_out, d );
331 tio_destroy( &tio_in );
332 tio_destroy( &tio_out );
341 boolT ismalloc = False;
342 char flags[64] =
"qhull d Qbb Qt";
343 facetT *facet, *neighbor, **neighborp;
344 vertexT *vertex, **vertexp;
346 int curlong, totlong;
347 FILE *outfile = stdout;
348 FILE *errfile = stderr;
353 int numfacets, numsimplicial, numridges, totneighbors, numcoplanars, numtricoplanars;
360 assert(
sizeof ( realT ) ==
sizeof (
double ) );
362 if ( np == 0 || ns > 0 || nh > 0 )
364 fprintf( stderr,
"segments=%d holes=%d\n, aborting Qhull implementation, use 'triangle' instead.\n", ns, nh );
369 qpoints = (coordT *) malloc( (
size_t) ( np * ( dim + 1 ) ) *
sizeof ( coordT ) );
371 for ( i = 0; i < np; i++ )
373 qpoints[i * dim] = points[i].
x;
374 qpoints[i * dim + 1] = points[i].
y;
380 strcat( flags,
" s" );
382 strcat( flags,
" Ts" );
391 exitcode = qh_new_qhull( dim, np, qpoints, ismalloc,
392 flags, outfile, errfile );
405 d->
points = malloc( (
size_t) np *
sizeof (
point ) );
406 for ( i = 0; i < np; ++i )
414 if ( p->
x < d->
xmin )
416 if ( p->
x > d->
xmax )
418 if ( p->
y < d->
ymin )
420 if ( p->
y > d->
ymax )
426 fprintf( stderr,
"input:\n" );
427 for ( i = 0; i < np; ++i )
431 fprintf( stderr,
" %d: %15.7g %15.7g %15.7g\n",
432 i, p->
x, p->
y, p->
z );
436 qh_findgood_all( qh facet_list );
437 qh_countfacets( qh facet_list, NULL, !qh_ALL, &numfacets,
438 &numsimplicial, &totneighbors, &numridges,
439 &numcoplanars, &numtricoplanars );
443 if ( !facet->upperdelaunay && facet->simplicial )
453 fprintf( stderr,
"triangles:\tneighbors:\n" );
457 if ( !facet->upperdelaunay && facet->simplicial )
464 FOREACHvertex_( facet->vertices )
465 t->vids[j++] = qh_pointid( vertex->
point );
468 FOREACHneighbor_( facet )
469 n->tids[j++] = ( neighbor->visitid > 0 ) ? (
int) neighbor->visitid - 1 : -1;
484 int tmp = t->vids[1];
485 t->vids[1] = t->vids[2];
497 fprintf( stderr,
" %d: (%d,%d,%d)\t(%d,%d,%d)\n",
512 for ( j = 0; j < 3; ++j )
516 for ( i = 0; i < d->
npoints; ++i )
528 for ( j = 0; j < 3; ++j )
530 int vid = t->
vids[j];
551 qh_freeqhull( !qh_ALL );
552 qh_memfreeshort( &curlong, &totlong );
553 if ( curlong || totlong )
555 "qhull: did not free %d bytes of long memory (%d pieces)\n",
568 return ( ( pb->
x - pa->
x ) * ( pc->
y - pa->
y ) <
569 ( pc->
x - pa->
x ) * ( pb->
y - pa->
y ) );
587 for ( i = 0; i < d->
npoints; ++i )
602 if ( d->
flags != NULL )
610 if ( d->
t_in != NULL )
612 if ( d->
t_out != NULL )
621 return ( p1->
x - p->
x ) * ( p0->
y - p->
y ) > ( p0->
x - p->
x ) * ( p1->
y - p->
y );
644 for ( i = 0; i < 3; ++i )
646 int i1 = ( i + 1 ) % 3;
685 if ( d->
t_in == NULL )
717 for ( i = 0; i < nn; ++i )
726 if ( tid < 0 || i == nn )
730 for ( tid = 0; tid < nt; ++tid )
756 while ( d->
t_in->
n > 0 )
764 for ( i = 0; i < 3; ++i )
766 int vid = t->
vids[i];
770 for ( j = 0; j < nt; ++j )
774 if ( d->
flags[ntid] == 0 )
int circle_build(circle *c, point *p0, point *p1, point *p2)
triangle_neighbours * neighbours
void istack_push(istack *s, int v)
static int on_right_side(point *p, point *p0, point *p1)
void delaunay_destroy(delaunay *d)
static int cw(delaunay *d, triangle *t)
delaunay * delaunay_build(int np, point points[], int ns, int segments[], int nh, double holes[])
void istack_destroy(istack *s)
int delaunay_xytoi(delaunay *d, point *p, int id)
void istack_reset(istack *s)
int circle_contains(circle *c, point *p)
int istack_pop(istack *s)
void delaunay_circles_find(delaunay *d, point *p, int *n, int **out)