27 #include "../lib/csa/csa.h"
29 #include "../lib/csa/nan.h"
32 #include "../lib/nn/nn.h"
33 #ifdef HAS_LIBQHULL_INCLUDE
34 #include <libqhull/qhull_a.h>
36 #include <qhull/qhull_a.h>
80 #define KNN_MAX_ORDER 100
120 plfgriddata( x, y, z, npts, xg, nptsx, yg, nptsy,
plf2ops_c(), (
PLPointer) zg, type, data );
130 if ( npts < 1 || nptsx < 1 || nptsy < 1 )
132 plabort(
"plgriddata: Bad array dimensions" );
138 for ( i = 0; i < nptsx - 1; i++ )
140 if ( xg[i] >= xg[i + 1] )
142 plabort(
"plgriddata: xg array must be strictly increasing" );
146 for ( i = 0; i < nptsy - 1; i++ )
148 if ( yg[i] >= yg[i + 1] )
150 plabort(
"plgriddata: yg array must be strictly increasing" );
156 for ( i = 0; i < nptsx; i++ )
157 for ( j = 0; j < nptsy; j++ )
158 zops->
set( zgp, i, j, 0.0 );
165 grid_csa( x, y, z, npts, xg, nptsx, yg, nptsy, zops, zgp );
167 plwarn(
"plgriddata(): PLplot was configured to not use GRID_CSA.\n Reverting to GRID_NNAIDW." );
168 grid_nnaidw( x, y, z, npts, xg, nptsx, yg, nptsy, zops, zgp );
173 grid_nnidw( x, y, z, npts, xg, nptsx, yg, nptsy, zops, zgp, (
int) data );
177 grid_nnli( x, y, z, npts, xg, nptsx, yg, nptsy, zops, zgp, data );
181 grid_nnaidw( x, y, z, npts, xg, nptsx, yg, nptsy, zops, zgp );
186 grid_dtli( x, y, z, npts, xg, nptsx, yg, nptsy, zops, zgp );
188 plwarn(
"plgriddata(): you must have the Qhull library installed to use GRID_DTLI.\n Reverting to GRID_NNAIDW." );
189 grid_nnaidw( x, y, z, npts, xg, nptsx, yg, nptsy, zops, zgp );
195 grid_nni( x, y, z, npts, xg, nptsx, yg, nptsy, zops, zgp, data );
197 plwarn(
"plgriddata(): you must have the Qhull library installed to use GRID_NNI.\n Reverting to GRID_NNAIDW." );
198 grid_nnaidw( x, y, z, npts, xg, nptsx, yg, nptsy, zops, zgp );
203 plabort(
"plgriddata: unknown algorithm type" );
224 if ( ( pin = (
point *) malloc( (
size_t) npts *
sizeof (
point ) ) ) == NULL )
226 plexit(
"grid_csa: Insufficient memory" );
233 for ( i = 0; i < npts; i++ )
235 pt->
x = (double) *xt++;
236 pt->
y = (double) *yt++;
237 pt->
z = (double) *zt++;
241 nptsg = nptsx * nptsy;
242 if ( ( pgrid = (
point *) malloc( (
size_t) nptsg *
sizeof (
point ) ) ) == NULL )
244 plexit(
"grid_csa: Insufficient memory" );
249 for ( j = 0; j < nptsy; j++ )
252 for ( i = 0; i < nptsx; i++ )
254 pt->
x = (double) *xt++;
255 pt->
y = (double) *yt;
266 for ( i = 0; i < nptsx; i++ )
268 for ( j = 0; j < nptsy; j++ )
270 pt = &pgrid[j * nptsx + i];
299 plabort(
"plgriddata(): GRID_NNIDW: knn_order too big" );
303 if ( knn_order == 0 )
305 plwarn(
"plgriddata(): GRID_NNIDW: knn_order must be specified with 'data' arg. Using 15" );
309 for ( i = 0; i < nptsx; i++ )
311 for ( j = 0; j < nptsy; j++ )
313 dist1( xg[i], yg[j], x, y, npts, knn_order );
315 #ifdef GMS // alternative weight coeficients. I Don't like the results
318 for ( k = 1; k < knn_order; k++ )
319 if ( items[k].dist > md )
322 zops->
set( zgp, i, j, 0.0 );
325 for ( k = 0; k < knn_order; k++ )
327 if ( items[k].item == -1 )
330 wi = ( md - items[k].
dist ) / ( md * items[k].dist );
333 wi = 1. / ( items[k].
dist * items[k].
dist );
335 zops->
add( zgp, i, j, wi * z[items[k].item] );
339 zops->
div( zgp, i, j, nt );
341 zops->
set( zgp, i, j,
NaN );
357 PLFLT xx[4], yy[4], zz[4], t, A, B, C, D, d1, d2, d3, max_thick;
358 int i, j, ii, excl, cnt, excl_item;
360 if ( threshold == 0. )
362 plwarn(
"plgriddata(): GRID_NNLI: threshold must be specified with 'data' arg. Using 1.001" );
365 else if ( threshold > 2. || threshold < 1. )
367 plabort(
"plgriddata(): GRID_NNLI: 1. < threshold < 2." );
371 for ( i = 0; i < nptsx; i++ )
373 for ( j = 0; j < nptsy; j++ )
375 dist1( xg[i], yg[j], x, y, npts, 3 );
378 for ( ii = 0; ii < 3; ii++ )
380 xx[ii] = x[items[ii].
item];
381 yy[ii] = y[items[ii].item];
382 zz[ii] = z[items[ii].item];
385 d1 = sqrt( ( xx[1] - xx[0] ) * ( xx[1] - xx[0] ) + ( yy[1] - yy[0] ) * ( yy[1] - yy[0] ) );
386 d2 = sqrt( ( xx[2] - xx[1] ) * ( xx[2] - xx[1] ) + ( yy[2] - yy[1] ) * ( yy[2] - yy[1] ) );
387 d3 = sqrt( ( xx[0] - xx[2] ) * ( xx[0] - xx[2] ) + ( yy[0] - yy[2] ) * ( yy[0] - yy[2] ) );
389 if ( d1 == 0. || d2 == 0. || d3 == 0. )
391 zops->
set( zgp, i, j,
NaN );
398 t = d1; d1 = d2; d2 = t;
404 t = d2; d2 = d3; d3 = t;
407 if ( ( d1 + d2 ) / d3 < threshold )
409 zops->
set( zgp, i, j,
NaN );
414 A = yy[0] * ( zz[1] - zz[2] ) + yy[1] * ( zz[2] - zz[0] ) + yy[2] * ( zz[0] - zz[1] );
415 B = zz[0] * ( xx[1] - xx[2] ) + zz[1] * ( xx[2] - xx[0] ) + zz[2] * ( xx[0] - xx[1] );
416 C = xx[0] * ( yy[1] - yy[2] ) + xx[1] * ( yy[2] - yy[0] ) + xx[2] * ( yy[0] - yy[1] );
417 D = -A * xx[0] - B * yy[0] - C * zz[0];
420 zops->
set( zgp, i, j, -xg[i] * A / C - yg[j] * B / C - D / C );
435 for ( i = 0; i < nptsx; i++ )
437 for ( j = 0; j < nptsy; j++ )
439 if ( zops->
is_nan( zgp, i, j ) )
441 dist1( xg[i], yg[j], x, y, npts, 4 );
455 max_thick = 0.; excl_item = -1;
456 for ( excl = 0; excl < 4; excl++ )
460 for ( ii = 0; ii < 4; ii++ )
464 xx[cnt] = x[items[ii].
item];
465 yy[cnt] = y[items[ii].item];
470 d1 = sqrt( ( xx[1] - xx[0] ) * ( xx[1] - xx[0] ) + ( yy[1] - yy[0] ) * ( yy[1] - yy[0] ) );
471 d2 = sqrt( ( xx[2] - xx[1] ) * ( xx[2] - xx[1] ) + ( yy[2] - yy[1] ) * ( yy[2] - yy[1] ) );
472 d3 = sqrt( ( xx[0] - xx[2] ) * ( xx[0] - xx[2] ) + ( yy[0] - yy[2] ) * ( yy[0] - yy[2] ) );
473 if ( d1 == 0. || d2 == 0. || d3 == 0. )
479 t = d1; d1 = d2; d2 = t;
484 t = d2; d2 = d3; d3 = t;
487 t = ( d1 + d2 ) / d3;
495 if ( excl_item == -1 )
500 for ( ii = 0; ii < 4; ii++ )
502 if ( ii != excl_item )
504 xx[cnt] = x[items[ii].
item];
505 yy[cnt] = y[items[ii].item];
506 zz[cnt] = z[items[ii].item];
511 A = yy[0] * ( zz[1] - zz[2] ) + yy[1] * ( zz[2] - zz[0] ) + yy[2] * ( zz[0] - zz[1] );
512 B = zz[0] * ( xx[1] - xx[2] ) + zz[1] * ( xx[2] - xx[0] ) + zz[2] * ( xx[0] - xx[1] );
513 C = xx[0] * ( yy[1] - yy[2] ) + xx[1] * ( yy[2] - yy[0] ) + xx[2] * ( yy[0] - yy[1] );
514 D = -A * xx[0] - B * yy[0] - C * zz[0];
517 zops->
set( zgp, i, j, -xg[i] * A / C - yg[j] * B / C - D / C );
538 for ( i = 0; i < nptsx; i++ )
540 for ( j = 0; j < nptsy; j++ )
542 dist2( xg[i], yg[j], x, y, npts );
543 zops->
set( zgp, i, j, 0. );
545 for ( k = 0; k < 4; k++ )
547 if ( items[k].item != -1 )
549 d = 1. / ( items[k].
dist * items[k].
dist );
550 zops->
add( zgp, i, j, d * z[items[k].item] );
555 zops->
set( zgp, i, j,
NaN );
557 zops->
div( zgp, i, j, nt );
578 point *pin, *pgrid, *pt;
582 if (
sizeof ( realT ) !=
sizeof (
double ) )
584 plabort(
"plgridata: QHull was compiled for floats instead of doubles" );
588 if ( ( pin = (
point *) malloc( (
size_t) npts *
sizeof (
point ) ) ) == NULL )
590 plexit(
"grid_dtli: Insufficient memory" );
597 for ( i = 0; i < npts; i++ )
599 pt->
x = (double) *xt++;
600 pt->
y = (double) *yt++;
601 pt->
z = (double) *zt++;
605 nptsg = nptsx * nptsy;
607 if ( ( pgrid = (
point *) malloc( (
size_t) nptsg *
sizeof (
point ) ) ) == NULL )
609 plexit(
"grid_dtli: Insufficient memory" );
614 for ( j = 0; j < nptsy; j++ )
617 for ( i = 0; i < nptsx; i++ )
619 pt->
x = (double) *xt++;
620 pt->
y = (double) *yt;
627 for ( i = 0; i < nptsx; i++ )
629 for ( j = 0; j < nptsy; j++ )
631 pt = &pgrid[j * nptsx + i];
653 point *pin, *pgrid, *pt;
657 if (
sizeof ( realT ) !=
sizeof (
double ) )
659 plabort(
"plgridata: QHull was compiled for floats instead of doubles" );
665 plwarn(
"plgriddata(): GRID_NNI: wtmin must be specified with 'data' arg. Using -PLFLT_MAX" );
669 if ( ( pin = (
point *) malloc( (
size_t) npts *
sizeof (
point ) ) ) == NULL )
671 plexit(
"plgridata: Insufficient memory" );
678 for ( i = 0; i < npts; i++ )
680 pt->
x = (double) *xt++;
681 pt->
y = (double) *yt++;
682 pt->
z = (double) *zt++;
686 nptsg = nptsx * nptsy;
688 if ( ( pgrid = (
point *) malloc( (
size_t) nptsg *
sizeof (
point ) ) ) == NULL )
690 plexit(
"plgridata: Insufficient memory" );
695 for ( j = 0; j < nptsy; j++ )
698 for ( i = 0; i < nptsx; i++ )
700 pt->
x = (double) *xt++;
701 pt->
y = (double) *yt;
708 for ( i = 0; i < nptsx; i++ )
710 for ( j = 0; j < nptsy; j++ )
712 pt = &pgrid[j * nptsx + i];
720 #endif // PL_HAVE_QHULL
736 for ( i = 0; i < knn_order; i++ )
742 for ( i = 0; i < npts; i++ )
744 d = ( ( gx - x[i] ) * ( gx - x[i] ) + ( gy - y[i] ) * ( gy - y[i] ) );
752 items[max_slot].
dist = d;
753 items[max_slot].
item = i;
756 max_dist = items[0].
dist;
758 for ( j = 1; j < knn_order; j++ )
760 if ( items[j].dist > max_dist )
762 max_dist = items[j].
dist;
768 for ( j = 0; j < knn_order; j++ )
769 items[j].dist = sqrt( items[j].dist );
783 for ( i = 0; i < 4; i++ )
789 for ( i = 0; i < npts; i++ )
791 d = ( ( gx - x[i] ) * ( gx - x[i] ) + ( gy - y[i] ) * ( gy - y[i] ) );
797 quad = 2 * ( x[i] > gx ) + ( y[i] < gy );
803 if ( d < items[quad].dist )
805 items[quad].
dist = d;
806 items[quad].
item = i;
810 for ( i = 0; i < 4; i++ )
811 if ( items[i].item != -1 )
812 items[i].
dist = sqrt( items[i].dist );
816 #ifdef NONN // another DTLI, based only on QHULL, not nn
822 boolT ismalloc = False;
825 vertexT *vertex, **vertexp;
826 facetT *neighbor, **neighborp;
827 int curlong, totlong;
828 FILE *outfile = NULL;
829 FILE *errfile = stderr;
834 PLFLT xt[3], yt[3], zt[3];
840 int numfacets, numsimplicial, numridges;
841 int totneighbors, numcoplanars, numtricoplanars;
843 plwarn(
"plgriddata: GRID_DTLI, If you have QHull knowledge, FIXME." );
847 strcpy( flags,
"qhull d Qbb Qt", 250 );
849 if ( ( points = (coordT *) malloc( npts * ( dim + 1 ) *
sizeof ( coordT ) ) ) == NULL )
851 plexit(
"grid_adtli: Insufficient memory" );
854 for ( i = 0; i < npts; i++ )
856 points[i * dim] = x[i];
857 points[i * dim + 1] = y[i];
861 exitcode = qh_new_qhull( dim, npts, points, ismalloc,
862 flags, outfile, errfile );
864 qh_init_A( stdin, stdout, stderr, 0, NULL );
865 exitcode = setjmp( qh errexit );
868 qh_initflags( flags );
869 qh PROJECTdelaunay = True;
870 qh_init_B( points, npts, dim, ismalloc );
877 #if 0 // print the triangles vertices
878 printf(
"Triangles\n" );
880 if ( !facet->upperdelaunay )
882 FOREACHvertex_( facet->vertices )
883 printf( " %d", qh_pointid( vertex->point ) );
889 #if 0 // print each triangle neighbors
890 printf(
"Neigbors\n" );
892 qh_findgood_all( qh facet_list );
893 qh_countfacets( qh facet_list, NULL, !qh_ALL, &numfacets, &numsimplicial,
894 &totneighbors, &numridges, &numcoplanars, &numtricoplanars );
897 if ( !facet->upperdelaunay )
899 FOREACHneighbor_( facet )
900 printf( " %d", neighbor->visitid ? neighbor->visitid - 1 : -neighbor->
id );
907 exitcode = setjmp( qh errexit );
910 qh NOerrexit = False;
911 for ( i = 0; i < nptsx; i++ )
912 for ( j = 0; j < nptsy; j++ )
917 qh_setdelaunay( 3, 1, point );
923 facet = qh_findbestfacet( point, qh_ALL, &bestdist, &isoutside );
927 facet = qh_findbest( point, qh facet_list, qh_ALL,
930 &bestdist, &isoutside, &totpart );
934 vertex = qh_nearvertex( facet, point, &bestdist );
950 facet = qh_findfacet_all( point, &bestdist, &isoutside, &totpart );
952 if ( facet->upperdelaunay )
953 zops->
set( zgp, i, j,
NaN );
956 FOREACHvertex_( facet->vertices )
958 k = qh_pointid( vertex->point );
967 A = yt[0] * ( zt[1] - zt[2] ) + yt[1] * ( zt[2] - zt[0] ) + yt[2] * ( zt[0] - zt[1] );
968 B = zt[0] * ( xt[1] - xt[2] ) + zt[1] * ( xt[2] - xt[0] ) + zt[2] * ( xt[0] - xt[1] );
969 C = xt[0] * ( yt[1] - yt[2] ) + xt[1] * ( yt[2] - yt[0] ) + xt[2] * ( yt[0] - yt[1] );
970 D = -A * xt[0] - B * yt[0] - C * zt[0];
973 zops->
set( zgp, i, j, -xg[i] * A / C - yg[j] * B / C - D / C );
981 qh_freeqhull( !qh_ALL );
982 qh_memfreeshort( &curlong, &totlong );
983 if ( curlong || totlong )
985 "qhull: did not free %d bytes of long memory (%d pieces)\n",
void plexit(PLCHAR_VECTOR errormsg)
PLFLT(* div)(PLPointer p, PLINT ix, PLINT iy, PLFLT z)
void plabort(PLCHAR_VECTOR errormsg)
static PT items[KNN_MAX_ORDER]
void csa_calculatespline(csa *a)
void csa_addpoints(csa *a, int n, point points[])
static void grid_nnli(PLFLT_VECTOR x, PLFLT_VECTOR y, PLFLT_VECTOR z, int npts, PLFLT_VECTOR xg, int nptsx, PLFLT_VECTOR yg, int nptsy, PLF2OPS zops, PLPointer zgp, PLFLT threshold)
static void dist2(PLFLT gx, PLFLT gy, PLFLT_VECTOR x, PLFLT_VECTOR y, int npts)
PLFLT(* set)(PLPointer p, PLINT ix, PLINT iy, PLFLT z)
void lpi_interpolate_points(int nin, point pin[], int nout, point pout[])
void plfgriddata(PLFLT_VECTOR x, PLFLT_VECTOR y, PLFLT_VECTOR z, PLINT npts, PLFLT_VECTOR xg, PLINT nptsx, PLFLT_VECTOR yg, PLINT nptsy, PLF2OPS zops, PLPointer zgp, PLINT type, PLFLT data)
void c_plgriddata(PLFLT_VECTOR x, PLFLT_VECTOR y, PLFLT_VECTOR z, PLINT npts, PLFLT_VECTOR xg, PLINT nptsx, PLFLT_VECTOR yg, PLINT nptsy, PLFLT **zg, PLINT type, PLFLT data)
static void grid_nnidw(PLFLT_VECTOR x, PLFLT_VECTOR y, PLFLT_VECTOR z, int npts, PLFLT_VECTOR xg, int nptsx, PLFLT_VECTOR yg, int nptsy, PLF2OPS zops, PLPointer zgp, int knn_order)
PLFLT(* add)(PLPointer p, PLINT ix, PLINT iy, PLFLT z)
NNDLLIMPEXP void nnpi_interpolate_points(int nin, point pin[], double wmin, int nout, point pout[])
void csa_approximate_points(csa *a, int n, point *points)
PLINT(* is_nan)(PLPointer p, PLINT ix, PLINT iy)
static void grid_nnaidw(PLFLT_VECTOR x, PLFLT_VECTOR y, PLFLT_VECTOR z, int npts, PLFLT_VECTOR xg, int nptsx, PLFLT_VECTOR yg, int nptsy, PLF2OPS zops, PLPointer zgp)
static void dist1(PLFLT gx, PLFLT gy, PLFLT_VECTOR x, PLFLT_VECTOR y, int npts, int knn_order)
void plwarn(PLCHAR_VECTOR errormsg)
const PLFLT * PLFLT_VECTOR