| 1 |
/**************************************************************************** |
| 2 |
* |
| 3 |
* MODULE: r.surf.idw |
| 4 |
* AUTHOR(S): Greg Koerper, Global Climate Research Project, US EPA |
| 5 |
* (original contributor) <koerper cs.orst.edu> |
| 6 |
* Markus Neteler <neteler itc.it>, |
| 7 |
* Bernhard Reiter <bernhard intevation.de>, |
| 8 |
* Brad Douglas <rez touchofmadness.com>, |
| 9 |
* Glynn Clements <glynn gclements.plus.com>, |
| 10 |
* Jachym Cepicky <jachym les-ejk.cz>, |
| 11 |
* Jan-Oliver Wagner <jan intevation.de>, |
| 12 |
* Radim Blazek <radim.blazek gmail.com> |
| 13 |
* PURPOSE: spatial interpolation based on distance squared weighting of |
| 14 |
* the values of nearest irregularly spaced data points |
| 15 |
* COPYRIGHT: (C) 1999-2008 by the GRASS Development Team |
| 16 |
* |
| 17 |
* This program is free software under the GNU General Public |
| 18 |
* License (>=v2). Read the file COPYING that comes with GRASS |
| 19 |
* for details. |
| 20 |
* |
| 21 |
*****************************************************************************/ |
| 22 |
|
| 23 |
/*************************************************************** |
| 24 |
|
| 25 |
910110 extended to latitude/longitude projection type |
| 26 |
910115 modified rowlist array to include only those rows with data |
| 27 |
910124 added -e flag option for output of error associated with |
| 28 |
interpolation of known cell values |
| 29 |
|
| 30 |
Further modifications tracked by CVS |
| 31 |
|
| 32 |
***************************************************************/ |
| 33 |
|
| 34 |
#include <stdlib.h> |
| 35 |
#include <math.h> |
| 36 |
#include <grass/gis.h> |
| 37 |
#include <grass/raster.h> |
| 38 |
#include <grass/glocale.h> |
| 39 |
#include "main.h" |
| 40 |
|
| 41 |
struct Cell_head window; |
| 42 |
CELL *cell, *mask; |
| 43 |
double *rowlook, *collook, *lat_diff, /* distances between latitudes */ |
| 44 |
ew2; |
| 45 |
|
| 46 |
int ll; /* TRUE if latitude-longitude projection */ |
| 47 |
|
| 48 |
/* function pointers for LL function substitutes */ |
| 49 |
|
| 50 |
int first_west(EW *, int); |
| 51 |
int first_west_LL(EW *, int); |
| 52 |
int (*init_row_search)(EW *, int); /* function pointer */ |
| 53 |
|
| 54 |
int completed_row(EW *); |
| 55 |
int completed_row_LL(EW *); |
| 56 |
|
| 57 |
/* function pointer */ |
| 58 |
int (*comp_row_search)(EW *); |
| 59 |
|
| 60 |
int find_neighbors(EW *, NEIGHBOR *, int, int, int, int *); |
| 61 |
int find_neighbors_LL(EW *, NEIGHBOR *, int, int, int, int *); |
| 62 |
|
| 63 |
/* function pointer */ |
| 64 |
int (*locate_neighbors)(EW *, NEIGHBOR *, int, int, int, int *); |
| 65 |
|
| 66 |
int exhaust_search(EW *, NEIGHBOR *, int, int); |
| 67 |
int exhaust_search_LL(EW *, NEIGHBOR *, int, int); |
| 68 |
|
| 69 |
/* function pointer */ |
| 70 |
int (*exhaust_row)(EW *, NEIGHBOR *, int, int); |
| 71 |
|
| 72 |
double offset_distance(int); |
| 73 |
double offset_distance_LL(int); |
| 74 |
double (*check_offset)(int); /* function pointer */ |
| 75 |
|
| 76 |
static int error_flag = 0; |
| 77 |
static char *input; |
| 78 |
static char *output; |
| 79 |
|
| 80 |
int main(int argc, char **argv) |
| 81 |
{ |
| 82 |
MELEMENT *rowlist; |
| 83 |
int nrows, ncols; |
| 84 |
int datarows; |
| 85 |
int npoints; |
| 86 |
struct GModule *module; |
| 87 |
struct History history; |
| 88 |
struct { |
| 89 |
struct Option *input, *output, *npoints; |
| 90 |
} parm; |
| 91 |
struct { |
| 92 |
struct Flag *e; |
| 93 |
} flag; |
| 94 |
int n, fd, maskfd; |
| 95 |
int cell_type; |
| 96 |
|
| 97 |
/* Initialize the GIS calls */ |
| 98 |
G_gisinit(argv[0]); |
| 99 |
|
| 100 |
module = G_define_module(); |
| 101 |
G_add_keyword(_("raster")); |
| 102 |
G_add_keyword(_("surface")); |
| 103 |
G_add_keyword(_("interpolation")); |
| 104 |
G_add_keyword(_("IDW")); |
| 105 |
module->description = _("Provides surface interpolation from raster point " |
| 106 |
"data by Inverse Distance Squared Weighting."); |
| 107 |
|
| 108 |
parm.input = G_define_standard_option(G_OPT_R_INPUT); |
| 109 |
|
| 110 |
parm.output = G_define_standard_option(G_OPT_R_OUTPUT); |
| 111 |
|
| 112 |
parm.npoints = G_define_option(); |
| 113 |
parm.npoints->key = "npoints"; |
| 114 |
parm.npoints->type = TYPE_INTEGER; |
| 115 |
parm.npoints->required = NO; |
| 116 |
parm.npoints->description = _("Number of interpolation points"); |
| 117 |
parm.npoints->answer = "12"; |
| 118 |
|
| 119 |
flag.e = G_define_flag(); |
| 120 |
flag.e->key = 'e'; |
| 121 |
flag.e->description = _("Output is the interpolation error"); |
| 122 |
|
| 123 |
if (G_parser(argc, argv)) |
| 124 |
exit(EXIT_FAILURE); |
| 125 |
|
| 126 |
if (sscanf(parm.npoints->answer, "%d", &n) != 1 || n <= 0) |
| 127 |
G_fatal_error(_("Illegal value for '%s' (%s)"), parm.npoints->key, |
| 128 |
parm.npoints->answer); |
| 129 |
|
| 130 |
npoints = n; |
| 131 |
error_flag = flag.e->answer; |
| 132 |
input = parm.input->answer; |
| 133 |
output = parm.output->answer; |
| 134 |
|
| 135 |
/* Get database window parameters */ |
| 136 |
G_get_window(&window); |
| 137 |
|
| 138 |
/* find number of rows and columns in window */ |
| 139 |
nrows = Rast_window_rows(); |
| 140 |
ncols = Rast_window_cols(); |
| 141 |
|
| 142 |
/* create distance squared or latitude lookup tables */ |
| 143 |
/* initialize function pointers */ |
| 144 |
lookup_and_function_ptrs(nrows, ncols); |
| 145 |
|
| 146 |
/* allocate buffers for row i/o */ |
| 147 |
cell = Rast_allocate_c_buf(); |
| 148 |
if ((maskfd = Rast_maskfd()) >= 0 || |
| 149 |
error_flag) { /* apply mask to output */ |
| 150 |
if (error_flag) /* use input as mask when -e option chosen */ |
| 151 |
maskfd = Rast_open_old(input, ""); |
| 152 |
mask = Rast_allocate_c_buf(); |
| 153 |
} |
| 154 |
else |
| 155 |
mask = NULL; |
| 156 |
|
| 157 |
/* Open input cell layer for reading */ |
| 158 |
fd = Rast_open_old(input, ""); |
| 159 |
|
| 160 |
cell_type = Rast_get_map_type(fd); |
| 161 |
if (cell_type != CELL_TYPE) |
| 162 |
G_fatal_error( |
| 163 |
_("This module currently only works for integer (CELL) maps")); |
| 164 |
|
| 165 |
/* Store input data in array-indexed doubly-linked lists and close input |
| 166 |
* file */ |
| 167 |
rowlist = row_lists(nrows, ncols, &datarows, &n, fd, cell); |
| 168 |
Rast_close(fd); |
| 169 |
if (npoints > n) |
| 170 |
npoints = n; |
| 171 |
|
| 172 |
/* open cell layer for writing output */ |
| 173 |
fd = Rast_open_c_new(output); |
| 174 |
|
| 175 |
/* call the interpolation function */ |
| 176 |
interpolate(rowlist, nrows, ncols, datarows, npoints, fd, maskfd); |
| 177 |
|
| 178 |
/* free allocated memory */ |
| 179 |
free_row_lists(rowlist, nrows); |
| 180 |
G_free(rowlook); |
| 181 |
G_free(collook); |
| 182 |
if (ll) |
| 183 |
free_dist_params(); |
| 184 |
Rast_close(fd); |
| 185 |
/* writing history file */ |
| 186 |
Rast_short_history(output, "raster", &history); |
| 187 |
Rast_command_history(&history); |
| 188 |
Rast_write_history(output, &history); |
| 189 |
|
| 190 |
G_done_msg(" "); |
| 191 |
|
| 192 |
exit(EXIT_SUCCESS); |
| 193 |
} |
| 194 |
|
| 195 |
/******************* END OF MAIN PROGRAM ************************/ |
| 196 |
|
| 197 |
/****************************************************************/ |
| 198 |
/* The content of lookup tables created for distance */ |
| 199 |
/* calculations depends on the projection type; function */ |
| 200 |
/* pointers are set dependent on projection type */ |
| 201 |
|
| 202 |
int lookup_and_function_ptrs(int nrows, int ncols) |
| 203 |
{ |
| 204 |
double a, e2; /* used to control geodetic distance calculations */ |
| 205 |
|
| 206 |
if ((ll = (G_projection() == PROJECTION_LL))) { |
| 207 |
/* equivalent to G_begin_distance_calculations () */ |
| 208 |
G_get_ellipsoid_parameters(&a, &e2); |
| 209 |
G_begin_geodesic_distance_l(nrows, a, e2); |
| 210 |
|
| 211 |
LL_lookup_tables(nrows, ncols); |
| 212 |
init_row_search = first_west_LL; |
| 213 |
comp_row_search = completed_row_LL; |
| 214 |
locate_neighbors = find_neighbors_LL; |
| 215 |
check_offset = offset_distance_LL; |
| 216 |
exhaust_row = exhaust_search_LL; |
| 217 |
} |
| 218 |
else { |
| 219 |
lookup_tables(nrows, ncols); |
| 220 |
init_row_search = first_west; |
| 221 |
comp_row_search = completed_row; |
| 222 |
locate_neighbors = find_neighbors; |
| 223 |
check_offset = offset_distance; |
| 224 |
exhaust_row = exhaust_search; |
| 225 |
} |
| 226 |
|
| 227 |
return 0; |
| 228 |
} |
| 229 |
|
| 230 |
/****************************************************************/ |
| 231 |
/* This function fills in the values of all elements in */ |
| 232 |
/* a matrix by interpolating from a given set of */ |
| 233 |
/* irregularly spaced data points */ |
| 234 |
|
| 235 |
int interpolate(MELEMENT rowlist[], int nrows, int ncols, int datarows, |
| 236 |
int npoints, int out_fd, int maskfd) |
| 237 |
{ |
| 238 |
extern CELL *cell; |
| 239 |
|
| 240 |
MELEMENT *Rptr; |
| 241 |
EW *search, *ewptr, *current_row, /* start row for north/south search */ |
| 242 |
*lastrow; /* last element in search array */ |
| 243 |
int row, col; |
| 244 |
NEIGHBOR *nbr_head, *Nptr; |
| 245 |
double sum1, sum2; |
| 246 |
|
| 247 |
/* initialize search array and neighbors array */ |
| 248 |
current_row = search = (EW *)G_calloc(datarows, sizeof(EW)); |
| 249 |
lastrow = search + datarows - 1; |
| 250 |
nbr_head = (NEIGHBOR *)G_calloc(npoints + 1, sizeof(NEIGHBOR)); |
| 251 |
#if 0 |
| 252 |
nbr_head->distance = maxdist; |
| 253 |
nbr_head->searchptr = &(nbr_head->Mptr); /* see replace_neighbor */ |
| 254 |
#endif |
| 255 |
|
| 256 |
G_message(n_("Interpolating raster map <%s> (%d row)...", |
| 257 |
"Interpolating raster map <%s> (%d rows)...", nrows), |
| 258 |
output, nrows); |
| 259 |
|
| 260 |
for (row = 0; row < nrows; row++) { /* loop over rows */ |
| 261 |
G_percent(row + 1, nrows, 2); |
| 262 |
|
| 263 |
/* if mask occurs, read current row of the mask */ |
| 264 |
if (mask) |
| 265 |
Rast_get_c_row(maskfd, mask, row); |
| 266 |
|
| 267 |
/* prepare search array for next row of interpolations */ |
| 268 |
for (ewptr = search, Rptr = rowlist; ewptr <= lastrow; Rptr++, ewptr++) |
| 269 |
ewptr->start = Rptr->next; /* start at first item in row */ |
| 270 |
|
| 271 |
for (col = 0; col < ncols; col++) { /* loop over columns */ |
| 272 |
|
| 273 |
/* if (row != 279 && col != 209) continue; */ |
| 274 |
|
| 275 |
/* don't interpolate outside of the mask */ |
| 276 |
if (mask && mask[col] == 0) { |
| 277 |
cell[col] = 0; |
| 278 |
continue; |
| 279 |
} |
| 280 |
|
| 281 |
/* make a list of npoints neighboring data pts */ |
| 282 |
nbr_head->next = NULL; |
| 283 |
if (make_neighbors_list( |
| 284 |
search, lastrow, current_row, row, col, nbr_head, |
| 285 |
npoints)) { /* otherwise, known data value assigned */ |
| 286 |
|
| 287 |
/* calculate value to be set for the cell from the data values |
| 288 |
* of npoints closest neighboring points */ |
| 289 |
sum1 = sum2 = 0.0; |
| 290 |
Nptr = nbr_head->next; |
| 291 |
|
| 292 |
do { |
| 293 |
sum1 += Nptr->Mptr->value / Nptr->distance; |
| 294 |
sum2 += 1.0 / Nptr->distance; |
| 295 |
Nptr = Nptr->next; |
| 296 |
} while (Nptr); /* to end of list */ |
| 297 |
|
| 298 |
cell[col] = (CELL)(sum1 / sum2 + .5); |
| 299 |
/* fprintf (stdout,"%d,%d = %d\n", col, row, cell[col]); */ |
| 300 |
|
| 301 |
if (error_flag) /* output interpolation error for this cell */ |
| 302 |
cell[col] -= mask[col]; |
| 303 |
} |
| 304 |
} /* end of loop over columns */ |
| 305 |
|
| 306 |
Rast_put_row(out_fd, cell, CELL_TYPE); |
| 307 |
|
| 308 |
/* advance current row pointer if necessary */ |
| 309 |
if (current_row->start->y == row && current_row != lastrow) |
| 310 |
++current_row; |
| 311 |
} /* end of loop over rows */ |
| 312 |
|
| 313 |
G_free(search); |
| 314 |
G_free(nbr_head); |
| 315 |
|
| 316 |
return 0; |
| 317 |
} |
| 318 |
|
| 319 |
/************** END OF FUNCTION "INTERPOLATE" *******************/ |
| 320 |
|
| 321 |
/****************************************************************/ |
| 322 |
/* */ |
| 323 |
/* This function makes a list of neighboring pts that fall */ |
| 324 |
/* inside the search radius around a cell whose value is */ |
| 325 |
/* to be interpolated using data value of its neighbors */ |
| 326 |
|
| 327 |
int make_neighbors_list( |
| 328 |
EW *firstrow, EW *lastrow, EW *curr_row, int row, int col, |
| 329 |
NEIGHBOR *head, /* head points to dummy plus npoints neighbors */ |
| 330 |
int npoints) |
| 331 |
{ |
| 332 |
extern CELL *cell; |
| 333 |
|
| 334 |
int neighbors = 0, /* number of neighbors in current list */ |
| 335 |
nsearch = 1, ssearch = 1; /* expand search north and south */ |
| 336 |
EW *north, *south; |
| 337 |
|
| 338 |
/* begin north search in the row of the point to be interpolated */ |
| 339 |
north = curr_row; |
| 340 |
(*init_row_search)(north, col); |
| 341 |
north->next = NULL; |
| 342 |
|
| 343 |
/* curtail interpolation if this cell has a value and not -e option */ |
| 344 |
if (north->east && north->east->x == col && north->east->y == row) { |
| 345 |
if (error_flag) { /* ignore value and interpolate */ |
| 346 |
if (ll) |
| 347 |
extend_east(north); |
| 348 |
else |
| 349 |
north->east = north->east->next; |
| 350 |
} |
| 351 |
else { /* no interpolation required */ |
| 352 |
cell[col] = north->east->value; |
| 353 |
return (0); |
| 354 |
} |
| 355 |
} |
| 356 |
/* initialize south search routine */ |
| 357 |
if (north == lastrow) |
| 358 |
south = NULL; |
| 359 |
else { |
| 360 |
south = north + 1; |
| 361 |
(*init_row_search)(south, col); |
| 362 |
south->next = NULL; |
| 363 |
} |
| 364 |
|
| 365 |
/* initialize search cycle pattern */ |
| 366 |
(*locate_neighbors)(north, head, row, col, npoints, &neighbors); |
| 367 |
search(&north, head, row, col, npoints, &neighbors, firstrow, -1); |
| 368 |
if (south) |
| 369 |
(*locate_neighbors)(south, head, row, col, npoints, &neighbors); |
| 370 |
|
| 371 |
/* expand row search north and south until all nearest neighbors must occur |
| 372 |
* within the current search boundaries, then exhaust search region */ |
| 373 |
do { |
| 374 |
if (north) { |
| 375 |
if (nsearch) |
| 376 |
nsearch = search(&north, head, row, col, npoints, &neighbors, |
| 377 |
firstrow, -1); |
| 378 |
else |
| 379 |
exhaust(&north, head, row, col); |
| 380 |
} |
| 381 |
if (south) { |
| 382 |
if (ssearch) |
| 383 |
ssearch = search(&south, head, row, col, npoints, &neighbors, |
| 384 |
lastrow, 1); |
| 385 |
else |
| 386 |
exhaust(&south, head, row, col); |
| 387 |
} |
| 388 |
} while (north || south); |
| 389 |
|
| 390 |
return (1); |
| 391 |
} |
| 392 |
|
| 393 |
/******* END OF FUNCTION "MAKE_NEIGHBORS_LIST" ******************/ |
| 394 |
|
| 395 |
int search(EW **ewptr, /* double-indirection !! */ |
| 396 |
NEIGHBOR *head, int row, int col, int npoints, int *neighbors, |
| 397 |
EW *boundary, int south /* search proceeds southward if == 1 */ |
| 398 |
) |
| 399 |
{ |
| 400 |
int new = 0; /* no prior search in first row in list */ |
| 401 |
EW *current, *prior; |
| 402 |
|
| 403 |
/* reset ewptr if row it points to has been thoroughly searched */ |
| 404 |
while (!new && (*comp_row_search)(*ewptr)) { |
| 405 |
*ewptr = next_row(*ewptr, boundary, &new, south); |
| 406 |
if (!*ewptr) |
| 407 |
return (0); /* search in this direction is completed */ |
| 408 |
} |
| 409 |
current = *ewptr; |
| 410 |
prior = NULL; |
| 411 |
|
| 412 |
/* process rows where search has already been initiated */ |
| 413 |
while (!new && current) { |
| 414 |
(*locate_neighbors)(current, head, row, col, npoints, neighbors); |
| 415 |
prior = current; |
| 416 |
current = next_row(current, boundary, &new, south); |
| 417 |
prior->next = current; |
| 418 |
} |
| 419 |
|
| 420 |
/* bound search path if no new rows available */ |
| 421 |
if (!new) { |
| 422 |
prior->next = prior; |
| 423 |
return (0); /* exhaust search region in this direction */ |
| 424 |
} |
| 425 |
|
| 426 |
/* check if new row could contain a nearest neighbor */ |
| 427 |
if ((*check_offset)(abs((int)(row - current->start->y))) >= |
| 428 |
head->next->distance) { |
| 429 |
if (prior && current != *ewptr) |
| 430 |
/* latter condition to assure prior set in this call to search */ |
| 431 |
prior->next = prior; |
| 432 |
current = NULL; |
| 433 |
return (0); /* exhaust search region in this direction */ |
| 434 |
} |
| 435 |
|
| 436 |
/* initiate search in next available row */ |
| 437 |
(*init_row_search)(current, col); |
| 438 |
current->next = NULL; |
| 439 |
(*locate_neighbors)(current, head, row, col, npoints, neighbors); |
| 440 |
|
| 441 |
return (1); /* search expansion continues in this direction */ |
| 442 |
} |
| 443 |
|
| 444 |
int exhaust(EW **ewptr, /* double-indirection !! */ |
| 445 |
NEIGHBOR *head, int row, int col) |
| 446 |
{ |
| 447 |
EW *current; |
| 448 |
|
| 449 |
/* check if further searching in this direction is necessary */ |
| 450 |
if ((*check_offset)(abs((int)(row - (*ewptr)->start->y))) >= |
| 451 |
head->next->distance) { |
| 452 |
*ewptr = NULL; |
| 453 |
return 0; |
| 454 |
} |
| 455 |
|
| 456 |
/* process row where search has already been initiated */ |
| 457 |
(*exhaust_row)(*ewptr, head, row, col); |
| 458 |
|
| 459 |
/* reset ewptr to point to a row that has not been thoroughly searched */ |
| 460 |
do { |
| 461 |
current = *ewptr; |
| 462 |
*ewptr = (*ewptr)->next; |
| 463 |
if (*ewptr == current) |
| 464 |
*ewptr = NULL; |
| 465 |
if (!*ewptr) |
| 466 |
return 0; |
| 467 |
} while ((*comp_row_search)(*ewptr)); |
| 468 |
|
| 469 |
return 0; |
| 470 |
} |
| 471 |
|
| 472 |
double offset_distance(int offset) |
| 473 |
{ |
| 474 |
return (offset * offset); /* compare squared distances in this case */ |
| 475 |
} |
| 476 |
|
| 477 |
/************************************************************************/ |
| 478 |
/* Return TRUE if search is exhausted both west and east in a row */ |
| 479 |
|
| 480 |
int completed_row(EW *ewptr) |
| 481 |
{ |
| 482 |
return (!ewptr->west && !ewptr->east); |
| 483 |
} |
| 484 |
|
| 485 |
EW *next_row(EW *ewptr, |
| 486 |
EW *boundary, /* row boundary of map in search direction */ |
| 487 |
int *new, int south /* search proceeds southward if == 1 */ |
| 488 |
) |
| 489 |
{ |
| 490 |
if (ewptr->next) |
| 491 |
if (ewptr->next == ewptr) /* signals end of this search */ |
| 492 |
return (NULL); |
| 493 |
else |
| 494 |
return (ewptr->next); |
| 495 |
else if (ewptr != boundary) { |
| 496 |
*new = 1; /* call first_west before finding neighbors */ |
| 497 |
return (ewptr += south); |
| 498 |
} |
| 499 |
else |
| 500 |
return (NULL); |
| 501 |
} |
| 502 |
|
| 503 |
/************************************************************************/ |
| 504 |
/* This function initializes the search for nearest neighbors */ |
| 505 |
/* by locating the two data closest to the specified column in */ |
| 506 |
/* a linked list of row data */ |
| 507 |
|
| 508 |
int first_west(EW *ewptr, int col) |
| 509 |
{ |
| 510 |
if (ewptr->start == NULL) { /* no data in this row */ |
| 511 |
ewptr->west = ewptr->east = NULL; |
| 512 |
return 0; |
| 513 |
} |
| 514 |
|
| 515 |
/* not at end of list and west of interpolation point */ |
| 516 |
while (ewptr->start->next && col > ewptr->start->x) |
| 517 |
ewptr->start = ewptr->start->next; |
| 518 |
|
| 519 |
ewptr->east = ewptr->start; |
| 520 |
ewptr->west = ewptr->start->prior; |
| 521 |
return 0; |
| 522 |
} |
| 523 |
|
| 524 |
/************************************************************************/ |
| 525 |
/* This function evaluates nearest neighbor status for a given */ |
| 526 |
/* datum and resets the row search pointer based on the result */ |
| 527 |
|
| 528 |
int find_neighbors(EW *ewptr, NEIGHBOR *nbr_head, int row, int col, int npoints, |
| 529 |
int *neighbors) |
| 530 |
{ |
| 531 |
MELEMENT **Mptr; /* double indirection !! */ |
| 532 |
int westward = 1; /* 1 if west of interpolation point */ |
| 533 |
double distance; |
| 534 |
|
| 535 |
Mptr = &ewptr->west; /* process search west first, then east */ |
| 536 |
do { |
| 537 |
if (*Mptr) { /* not NULL */ |
| 538 |
distance = triangulate(*Mptr, row, col); |
| 539 |
|
| 540 |
if (*neighbors < npoints) |
| 541 |
add_neighbor(Mptr, nbr_head, distance, ++(*neighbors)); |
| 542 |
else if (!replace_neighbor(Mptr, nbr_head, distance)) |
| 543 |
*Mptr = NULL; /* curtail search in this direction */ |
| 544 |
|
| 545 |
if (*Mptr) { |
| 546 |
if (westward) |
| 547 |
*Mptr = (*Mptr)->prior; |
| 548 |
else |
| 549 |
*Mptr = (*Mptr)->next; |
| 550 |
} |
| 551 |
} |
| 552 |
|
| 553 |
Mptr = &ewptr->east; |
| 554 |
} while (westward--); /* repeat loop for east and quit */ |
| 555 |
return 0; |
| 556 |
} |
| 557 |
|
| 558 |
/************************************************************************/ |
| 559 |
/* This function exhausts all possible nearest neighhbors */ |
| 560 |
/* within the row indexed by the ew search pointer */ |
| 561 |
|
| 562 |
int exhaust_search(EW *ewptr, NEIGHBOR *nbr_head, int row, int col) |
| 563 |
{ |
| 564 |
double distance; |
| 565 |
|
| 566 |
while (ewptr->west) { /* not NULL */ |
| 567 |
distance = triangulate(ewptr->west, row, col); |
| 568 |
|
| 569 |
if (!replace_neighbor(&ewptr->west, nbr_head, distance)) |
| 570 |
break; /* curtail search in this direction */ |
| 571 |
else |
| 572 |
ewptr->west = ewptr->west->prior; |
| 573 |
} |
| 574 |
|
| 575 |
while (ewptr->east) { /* not NULL */ |
| 576 |
distance = triangulate(ewptr->east, row, col); |
| 577 |
|
| 578 |
if (!replace_neighbor(&ewptr->east, nbr_head, distance)) |
| 579 |
break; /* curtail search in this direction */ |
| 580 |
else |
| 581 |
ewptr->east = ewptr->east->next; |
| 582 |
} |
| 583 |
return 0; |
| 584 |
} |
| 585 |
|
| 586 |
/************************************************************************/ |
| 587 |
/* triangulate returns the square of the hypoteneuse */ |
| 588 |
|
| 589 |
double triangulate(MELEMENT *Mptr, int row, int col) |
| 590 |
{ |
| 591 |
extern double *rowlook, *collook; |
| 592 |
int rowoff, coloff; |
| 593 |
|
| 594 |
rowoff = abs(row - Mptr->y); |
| 595 |
coloff = abs(col - Mptr->x); |
| 596 |
return (*(rowlook + rowoff) + *(collook + coloff)); |
| 597 |
} |
| 598 |
|
| 599 |
int add_neighbor(MELEMENT **Mptr, /* double-indirection!! */ |
| 600 |
NEIGHBOR *nptr, double distance, int neighbors) |
| 601 |
{ |
| 602 |
NEIGHBOR *new; |
| 603 |
|
| 604 |
new = nptr + neighbors; /* offset from base of neighbors array */ |
| 605 |
new->distance = distance; |
| 606 |
new->Mptr = *Mptr; /* points to row_list element */ |
| 607 |
new->searchptr = Mptr; /* points to east or west field of an EW */ |
| 608 |
|
| 609 |
while (nptr->next && nptr->next->distance > distance) |
| 610 |
nptr = nptr->next; |
| 611 |
new->next = nptr->next; |
| 612 |
nptr->next = new; |
| 613 |
return 0; |
| 614 |
} |
| 615 |
|
| 616 |
int replace_neighbor(MELEMENT **Mptr, /* double-indirection!! */ |
| 617 |
NEIGHBOR *nbr_head, double distance) |
| 618 |
{ |
| 619 |
NEIGHBOR *furthest; |
| 620 |
|
| 621 |
furthest = nbr_head->next; |
| 622 |
if (distance < furthest->distance) { /* replace furthest neighbor */ |
| 623 |
/* this slight efficiency is not available to LL */ |
| 624 |
if (!ll) /* all other data in this direction are more distant */ |
| 625 |
*(furthest->searchptr) = NULL; |
| 626 |
|
| 627 |
furthest->distance = distance; |
| 628 |
furthest->Mptr = *Mptr; /* points to row_list element */ |
| 629 |
furthest->searchptr = Mptr; /* points to east or west field of an EW */ |
| 630 |
|
| 631 |
/* keep neighbors list in descending order of distance */ |
| 632 |
if (furthest->next && (furthest->distance < furthest->next->distance)) |
| 633 |
sort_neighbors(nbr_head, distance); |
| 634 |
return (1); |
| 635 |
} |
| 636 |
else |
| 637 |
return (0); |
| 638 |
} |
| 639 |
|
| 640 |
int sort_neighbors(NEIGHBOR *nbr_head, double distance) |
| 641 |
{ |
| 642 |
NEIGHBOR *nptr, *new; |
| 643 |
|
| 644 |
new = nbr_head->next; |
| 645 |
nptr = nbr_head->next->next; |
| 646 |
|
| 647 |
while (nptr->next && nptr->next->distance > distance) |
| 648 |
nptr = nptr->next; |
| 649 |
nbr_head->next = new->next; |
| 650 |
new->next = nptr->next; |
| 651 |
nptr->next = new; |
| 652 |
return 0; |
| 653 |
} |
| 654 |
|
| 655 |
int free_row_lists(/* frees indexed row lists of data */ |
| 656 |
MELEMENT *rowlist, int nrows) |
| 657 |
{ |
| 658 |
int i; |
| 659 |
MELEMENT *Mptr, *prev; |
| 660 |
|
| 661 |
for (i = 0; i < nrows; i++) { |
| 662 |
Mptr = (rowlist + i)->next; |
| 663 |
if (ll && Mptr) |
| 664 |
Mptr->prior->next = NULL; |
| 665 |
while ((prev = Mptr)) { |
| 666 |
Mptr = Mptr->next; |
| 667 |
G_free(prev); |
| 668 |
} |
| 669 |
} |
| 670 |
G_free(rowlist); |
| 671 |
return 0; |
| 672 |
} |
| 673 |
|
| 674 |
MELEMENT *row_lists( |
| 675 |
/* Search and make array-indexed doubly-linked lists of original data points |
| 676 |
*/ |
| 677 |
int rows, int cols, /* total rows and columns in window */ |
| 678 |
int *datarows, /* number of rows with non-zero input data */ |
| 679 |
int *npts, /* number of data points available */ |
| 680 |
int fd, /* file descriptor, input */ |
| 681 |
CELL *cell /* array of data for a single row */ |
| 682 |
) |
| 683 |
{ |
| 684 |
int row, col; /* row and column indices */ |
| 685 |
MELEMENT *rowlist, /* root of rowlist data structure index array */ |
| 686 |
*endlist, *Mptr, /* pointer to a rowlist element */ |
| 687 |
*Rptr; /* pointer to a row list dummy */ |
| 688 |
|
| 689 |
/* initialize row array (allocated memory set to zero), |
| 690 |
* each dummy points to itself as last element entered in matrix */ |
| 691 |
rowlist = (MELEMENT *)G_calloc(rows, sizeof(MELEMENT)); |
| 692 |
for (row = 0, Rptr = rowlist; row < rows; row++, Rptr++) |
| 693 |
Rptr->prior = Rptr; |
| 694 |
|
| 695 |
/* enter data by allocation of individual matrix elements */ |
| 696 |
*npts = 0; |
| 697 |
G_message(_("Reading raster map <%s>..."), input); |
| 698 |
|
| 699 |
for (row = 0, Rptr = rowlist; row < rows; row++) { |
| 700 |
G_percent(row + 1, rows, 2); |
| 701 |
Rast_get_c_row_nomask(fd, cell, row); |
| 702 |
|
| 703 |
for (col = 0; col < cols; col++) { |
| 704 |
if (!Rast_is_c_null_value(&cell[col])) { |
| 705 |
++(*npts); |
| 706 |
Mptr = (MELEMENT *)G_malloc(sizeof(MELEMENT)); |
| 707 |
Mptr->x = col; |
| 708 |
Mptr->y = row; |
| 709 |
Mptr->value = cell[col]; |
| 710 |
|
| 711 |
/* doubly link new element to rowlist */ |
| 712 |
Mptr->prior = Rptr->prior; |
| 713 |
Rptr->prior = (Rptr->prior->next = Mptr); |
| 714 |
} |
| 715 |
} /* loop over cols */ |
| 716 |
|
| 717 |
if (Rptr->prior != Rptr) /* non-zero input data in this row */ |
| 718 |
Rptr++->y = row; |
| 719 |
} /* loop over rows */ |
| 720 |
|
| 721 |
endlist = Rptr; /* point to element after last valid row list dummy */ |
| 722 |
|
| 723 |
/* add final link to complete doubly-linked lists */ |
| 724 |
for (Rptr = rowlist; Rptr != endlist; Rptr++) |
| 725 |
if (ll) { /* make the list circular */ |
| 726 |
Rptr->next->prior = Rptr->prior; |
| 727 |
Rptr->prior->next = Rptr->next; |
| 728 |
} |
| 729 |
else /* place NULL sentinel at each end of list */ |
| 730 |
Rptr->next->prior = Rptr->prior->next = NULL; |
| 731 |
|
| 732 |
*datarows = endlist - rowlist; /* number of non-zero input data rows */ |
| 733 |
return (rowlist); |
| 734 |
} |
| 735 |
|
| 736 |
/************************************************************************/ |
| 737 |
/* Lookup tables containing distance squared (in units of ns.res) */ |
| 738 |
/* are created for later use in selecting nearest neighbors */ |
| 739 |
|
| 740 |
int lookup_tables(int nrows, int ncols) |
| 741 |
{ |
| 742 |
extern double *rowlook, *collook, ew2; |
| 743 |
extern struct Cell_head window; |
| 744 |
double *nextrow, *nextcol; |
| 745 |
int i; |
| 746 |
|
| 747 |
/* calculate square of resolution ratio ew : ns */ |
| 748 |
ew2 = window.ew_res / window.ns_res * window.ew_res / window.ns_res; |
| 749 |
|
| 750 |
nextrow = rowlook = (double *)G_calloc(nrows, sizeof(double)); |
| 751 |
for (i = 0; i < nrows; i++, nextrow++) |
| 752 |
*nextrow = (double)i * i; |
| 753 |
|
| 754 |
nextcol = collook = (double *)G_calloc(ncols, sizeof(double)); |
| 755 |
for (i = 0; i < ncols; i++, nextcol++) |
| 756 |
*nextcol = (double)i * i * ew2; |
| 757 |
|
| 758 |
return 0; |
| 759 |
} |