libfprint/nbis/mindtct/util.c
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | /******************************************************************************* | ||
| 2 | |||
| 3 | License: | ||
| 4 | This software and/or related materials was developed at the National Institute | ||
| 5 | of Standards and Technology (NIST) by employees of the Federal Government | ||
| 6 | in the course of their official duties. Pursuant to title 17 Section 105 | ||
| 7 | of the United States Code, this software is not subject to copyright | ||
| 8 | protection and is in the public domain. | ||
| 9 | |||
| 10 | This software and/or related materials have been determined to be not subject | ||
| 11 | to the EAR (see Part 734.3 of the EAR for exact details) because it is | ||
| 12 | a publicly available technology and software, and is freely distributed | ||
| 13 | to any interested party with no licensing requirements. Therefore, it is | ||
| 14 | permissible to distribute this software as a free download from the internet. | ||
| 15 | |||
| 16 | Disclaimer: | ||
| 17 | This software and/or related materials was developed to promote biometric | ||
| 18 | standards and biometric technology testing for the Federal Government | ||
| 19 | in accordance with the USA PATRIOT Act and the Enhanced Border Security | ||
| 20 | and Visa Entry Reform Act. Specific hardware and software products identified | ||
| 21 | in this software were used in order to perform the software development. | ||
| 22 | In no case does such identification imply recommendation or endorsement | ||
| 23 | by the National Institute of Standards and Technology, nor does it imply that | ||
| 24 | the products and equipment identified are necessarily the best available | ||
| 25 | for the purpose. | ||
| 26 | |||
| 27 | This software and/or related materials are provided "AS-IS" without warranty | ||
| 28 | of any kind including NO WARRANTY OF PERFORMANCE, MERCHANTABILITY, | ||
| 29 | NO WARRANTY OF NON-INFRINGEMENT OF ANY 3RD PARTY INTELLECTUAL PROPERTY | ||
| 30 | or FITNESS FOR A PARTICULAR PURPOSE or for any purpose whatsoever, for the | ||
| 31 | licensed product, however used. In no event shall NIST be liable for any | ||
| 32 | damages and/or costs, including but not limited to incidental or consequential | ||
| 33 | damages of any kind, including economic damage or injury to property and lost | ||
| 34 | profits, regardless of whether NIST shall be advised, have reason to know, | ||
| 35 | or in fact shall know of the possibility. | ||
| 36 | |||
| 37 | By using this software, you agree to bear all risk relating to quality, | ||
| 38 | use and performance of the software and/or related materials. You agree | ||
| 39 | to hold the Government harmless from any claim arising from your use | ||
| 40 | of the software. | ||
| 41 | |||
| 42 | *******************************************************************************/ | ||
| 43 | |||
| 44 | |||
| 45 | /*********************************************************************** | ||
| 46 | LIBRARY: LFS - NIST Latent Fingerprint System | ||
| 47 | |||
| 48 | FILE: UTIL.C | ||
| 49 | AUTHOR: Michael D. Garris | ||
| 50 | DATE: 03/16/1999 | ||
| 51 | |||
| 52 | Contains general support routines required by the NIST | ||
| 53 | Latent Fingerprint System (LFS). | ||
| 54 | |||
| 55 | *********************************************************************** | ||
| 56 | ROUTINES: | ||
| 57 | maxv() | ||
| 58 | minv() | ||
| 59 | minmaxs() | ||
| 60 | distance() | ||
| 61 | squared_distance() | ||
| 62 | in_int_list() | ||
| 63 | remove_from_int_list() | ||
| 64 | find_incr_position_dbl() | ||
| 65 | angle2line() | ||
| 66 | line2direction() | ||
| 67 | closest_dir_dist() | ||
| 68 | ***********************************************************************/ | ||
| 69 | |||
| 70 | #include <stdio.h> | ||
| 71 | #include <lfs.h> | ||
| 72 | |||
| 73 | /************************************************************************* | ||
| 74 | ************************************************************************** | ||
| 75 | #cat: maxv - Determines the maximum value in the given list of integers. | ||
| 76 | #cat: NOTE, the list is assumed to be NOT empty! | ||
| 77 | |||
| 78 | Input: | ||
| 79 | list - non-empty list of integers to be searched | ||
| 80 | num - number of integers in the list | ||
| 81 | Return Code: | ||
| 82 | Maximum - maximum value in the list | ||
| 83 | **************************************************************************/ | ||
| 84 | 6156 | int maxv(const int *list, const int num) | |
| 85 | { | ||
| 86 | 6156 | int i; | |
| 87 | 6156 | int maxval; | |
| 88 | |||
| 89 | /* NOTE: The list is assumed to be NOT empty. */ | ||
| 90 | /* Initialize running maximum to first item in list. */ | ||
| 91 | 6156 | maxval = list[0]; | |
| 92 | |||
| 93 | /* Foreach subsequent item in the list... */ | ||
| 94 |
2/2✓ Branch 4 → 3 taken 78228 times.
✓ Branch 4 → 5 taken 6156 times.
|
84384 | for(i = 1; i < num; i++){ |
| 95 | /* If current item is larger than running maximum... */ | ||
| 96 | 78228 | if(list[i] > maxval) | |
| 97 | /* Set running maximum to the larger item. */ | ||
| 98 | maxval = list[i]; | ||
| 99 | /* Otherwise, skip to next item. */ | ||
| 100 | } | ||
| 101 | |||
| 102 | /* Return the resulting maximum. */ | ||
| 103 | 6156 | return(maxval); | |
| 104 | } | ||
| 105 | |||
| 106 | /************************************************************************* | ||
| 107 | ************************************************************************** | ||
| 108 | #cat: minv - Determines the minimum value in the given list of integers. | ||
| 109 | #cat: NOTE, the list is assumed to be NOT empty! | ||
| 110 | |||
| 111 | Input: | ||
| 112 | list - non-empty list of integers to be searched | ||
| 113 | num - number of integers in the list | ||
| 114 | Return Code: | ||
| 115 | Minimum - minimum value in the list | ||
| 116 | **************************************************************************/ | ||
| 117 | 6156 | int minv(const int *list, const int num) | |
| 118 | { | ||
| 119 | 6156 | int i; | |
| 120 | 6156 | int minval; | |
| 121 | |||
| 122 | /* NOTE: The list is assumed to be NOT empty. */ | ||
| 123 | /* Initialize running minimum to first item in list. */ | ||
| 124 | 6156 | minval = list[0]; | |
| 125 | |||
| 126 | /* Foreach subsequent item in the list... */ | ||
| 127 |
2/2✓ Branch 4 → 3 taken 78228 times.
✓ Branch 4 → 5 taken 6156 times.
|
84384 | for(i = 1; i < num; i++){ |
| 128 | /* If current item is smaller than running minimum... */ | ||
| 129 | 78228 | if(list[i] < minval) | |
| 130 | /* Set running minimum to the smaller item. */ | ||
| 131 | minval = list[i]; | ||
| 132 | /* Otherwise, skip to next item. */ | ||
| 133 | } | ||
| 134 | |||
| 135 | /* Return the resulting minimum. */ | ||
| 136 | 6156 | return(minval); | |
| 137 | } | ||
| 138 | |||
| 139 | /************************************************************************* | ||
| 140 | ************************************************************************** | ||
| 141 | #cat: minmaxs - Takes a list of integers and identifies points of relative | ||
| 142 | #cat: minima and maxima. The midpoint of flat plateaus and valleys | ||
| 143 | #cat: are selected when they are detected. | ||
| 144 | |||
| 145 | Input: | ||
| 146 | items - list of integers to be analyzed | ||
| 147 | num - number of items in the list | ||
| 148 | Output: | ||
| 149 | ominmax_val - value of the item at each minima or maxima | ||
| 150 | ominmax_type - identifies a minima as '-1' and maxima as '1' | ||
| 151 | ominmax_i - index of item's position in list | ||
| 152 | ominmax_alloc - number of allocated minima and/or maxima | ||
| 153 | ominmax_num - number of detected minima and/or maxima | ||
| 154 | Return Code: | ||
| 155 | Zero - successful completion | ||
| 156 | Negative - system error | ||
| 157 | **************************************************************************/ | ||
| 158 | 23692 | int minmaxs(int **ominmax_val, int **ominmax_type, int **ominmax_i, | |
| 159 | int *ominmax_alloc, int *ominmax_num, | ||
| 160 | const int *items, const int num) | ||
| 161 | { | ||
| 162 | 23692 | int i, diff, state, start, loc; | |
| 163 | 23692 | int *minmax_val, *minmax_type, *minmax_i, minmax_alloc, minmax_num; | |
| 164 | |||
| 165 | |||
| 166 | /* Determine maximum length for allocation of buffers. */ | ||
| 167 | /* If there are fewer than 3 items ... */ | ||
| 168 |
1/2✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 23692 times.
|
23692 | if(num < 3){ |
| 169 | /* Then no min/max is possible, so set allocated length */ | ||
| 170 | /* to 0 and return. */ | ||
| 171 | ✗ | *ominmax_alloc = 0; | |
| 172 | ✗ | *ominmax_num = 0; | |
| 173 | ✗ | return(0); | |
| 174 | } | ||
| 175 | /* Otherwise, set allocation length to number of items - 2 */ | ||
| 176 | /* (one for the first item in the list, and on for the last). */ | ||
| 177 | /* Every other intermediate point can potentially represent a */ | ||
| 178 | /* min or max. */ | ||
| 179 | 23692 | minmax_alloc = num - 2; | |
| 180 | /* Allocate the buffers. */ | ||
| 181 | 23692 | minmax_val = (int *)g_malloc(minmax_alloc * sizeof(int)); | |
| 182 | 23692 | minmax_type = (int *)g_malloc(minmax_alloc * sizeof(int)); | |
| 183 | 23692 | minmax_i = (int *)g_malloc(minmax_alloc * sizeof(int)); | |
| 184 | |||
| 185 | /* Initialize number of min/max to 0. */ | ||
| 186 | 23692 | minmax_num = 0; | |
| 187 | |||
| 188 | /* Start witht the first item in the list. */ | ||
| 189 | 23692 | i = 0; | |
| 190 | |||
| 191 | /* Get starting state between first pair of items. */ | ||
| 192 | 23692 | diff = items[1] - items[0]; | |
| 193 |
2/2✓ Branch 7 → 8 taken 16144 times.
✓ Branch 7 → 10 taken 7548 times.
|
23692 | if(diff > 0) |
| 194 | state = 1; | ||
| 195 |
2/2✓ Branch 8 → 9 taken 2429 times.
✓ Branch 8 → 10 taken 13715 times.
|
16144 | else if (diff < 0) |
| 196 | state = -1; | ||
| 197 | else | ||
| 198 | 2429 | state = 0; | |
| 199 | |||
| 200 | /* Set start location to first item in list. */ | ||
| 201 | 23692 | start = 0; | |
| 202 | |||
| 203 | /* Bump to next item in list. */ | ||
| 204 | 23692 | i++; | |
| 205 | |||
| 206 | /* While not at the last item in list. */ | ||
| 207 |
2/2✓ Branch 24 → 11 taken 307996 times.
✓ Branch 24 → 25 taken 23692 times.
|
331688 | while(i < num-1){ |
| 208 | |||
| 209 | /* Compute difference between next pair of items. */ | ||
| 210 | 307996 | diff = items[i+1] - items[i]; | |
| 211 | /* If items are increasing ... */ | ||
| 212 |
2/2✓ Branch 11 → 12 taken 146600 times.
✓ Branch 11 → 17 taken 161396 times.
|
307996 | if(diff > 0){ |
| 213 | /* If previously increasing ... */ | ||
| 214 |
2/2✓ Branch 12 → 13 taken 15090 times.
✓ Branch 12 → 23 taken 131510 times.
|
146600 | if(state == 1){ |
| 215 | /* Reset start to current location. */ | ||
| 216 | start = i; | ||
| 217 | } | ||
| 218 | /* If previously decreasing ... */ | ||
| 219 |
2/2✓ Branch 13 → 14 taken 14393 times.
✓ Branch 13 → 15 taken 697 times.
|
15090 | else if (state == -1){ |
| 220 | /* Then we have incurred a minima ... */ | ||
| 221 | /* Compute midpoint of minima. */ | ||
| 222 | 14393 | loc = (start + i)/2; | |
| 223 | /* Store value at minima midpoint. */ | ||
| 224 | 14393 | minmax_val[minmax_num] = items[loc]; | |
| 225 | /* Store type code for minima. */ | ||
| 226 | 14393 | minmax_type[minmax_num] = -1; | |
| 227 | /* Store location of minima midpoint. */ | ||
| 228 | 14393 | minmax_i[minmax_num++] = loc; | |
| 229 | /* Change state to increasing. */ | ||
| 230 | 14393 | state = 1; | |
| 231 | /* Reset start location. */ | ||
| 232 | 14393 | start = i; | |
| 233 | } | ||
| 234 | /* If previously level (this state only can occur at the */ | ||
| 235 | /* beginning of the list of items) ... */ | ||
| 236 | else { | ||
| 237 | /* If more than one level state in a row ... */ | ||
| 238 |
2/2✓ Branch 15 → 16 taken 145 times.
✓ Branch 15 → 23 taken 552 times.
|
697 | if(i-start > 1){ |
| 239 | /* Then consider a minima ... */ | ||
| 240 | /* Compute midpoint of minima. */ | ||
| 241 | 145 | loc = (start + i)/2; | |
| 242 | /* Store value at minima midpoint. */ | ||
| 243 | 145 | minmax_val[minmax_num] = items[loc]; | |
| 244 | /* Store type code for minima. */ | ||
| 245 | 145 | minmax_type[minmax_num] = -1; | |
| 246 | /* Store location of minima midpoint. */ | ||
| 247 | 145 | minmax_i[minmax_num++] = loc; | |
| 248 | /* Change state to increasing. */ | ||
| 249 | 145 | state = 1; | |
| 250 | /* Reset start location. */ | ||
| 251 | 145 | start = i; | |
| 252 | } | ||
| 253 | /* Otherwise, ignore single level state. */ | ||
| 254 | else{ | ||
| 255 | /* Change state to increasing. */ | ||
| 256 | state = 1; | ||
| 257 | /* Reset start location. */ | ||
| 258 | start = i; | ||
| 259 | } | ||
| 260 | } | ||
| 261 | } | ||
| 262 | /* If items are decreasing ... */ | ||
| 263 |
2/2✓ Branch 17 → 18 taken 118950 times.
✓ Branch 17 → 23 taken 42446 times.
|
161396 | else if(diff < 0){ |
| 264 | /* If previously decreasing ... */ | ||
| 265 |
2/2✓ Branch 18 → 19 taken 7676 times.
✓ Branch 18 → 23 taken 111274 times.
|
118950 | if(state == -1){ |
| 266 | /* Reset start to current location. */ | ||
| 267 | start = i; | ||
| 268 | } | ||
| 269 | /* If previously increasing ... */ | ||
| 270 |
2/2✓ Branch 19 → 20 taken 5944 times.
✓ Branch 19 → 21 taken 1732 times.
|
7676 | else if (state == 1){ |
| 271 | /* Then we have incurred a maxima ... */ | ||
| 272 | /* Compute midpoint of maxima. */ | ||
| 273 | 5944 | loc = (start + i)/2; | |
| 274 | /* Store value at maxima midpoint. */ | ||
| 275 | 5944 | minmax_val[minmax_num] = items[loc]; | |
| 276 | /* Store type code for maxima. */ | ||
| 277 | 5944 | minmax_type[minmax_num] = 1; | |
| 278 | /* Store location of maxima midpoint. */ | ||
| 279 | 5944 | minmax_i[minmax_num++] = loc; | |
| 280 | /* Change state to decreasing. */ | ||
| 281 | 5944 | state = -1; | |
| 282 | /* Reset start location. */ | ||
| 283 | 5944 | start = i; | |
| 284 | } | ||
| 285 | /* If previously level (this state only can occur at the */ | ||
| 286 | /* beginning of the list of items) ... */ | ||
| 287 | else { | ||
| 288 | /* If more than one level state in a row ... */ | ||
| 289 |
2/2✓ Branch 21 → 22 taken 306 times.
✓ Branch 21 → 23 taken 1426 times.
|
1732 | if(i-start > 1){ |
| 290 | /* Then consider a maxima ... */ | ||
| 291 | /* Compute midpoint of maxima. */ | ||
| 292 | 306 | loc = (start + i)/2; | |
| 293 | /* Store value at maxima midpoint. */ | ||
| 294 | 306 | minmax_val[minmax_num] = items[loc]; | |
| 295 | /* Store type code for maxima. */ | ||
| 296 | 306 | minmax_type[minmax_num] = 1; | |
| 297 | /* Store location of maxima midpoint. */ | ||
| 298 | 306 | minmax_i[minmax_num++] = loc; | |
| 299 | /* Change state to decreasing. */ | ||
| 300 | 306 | state = -1; | |
| 301 | /* Reset start location. */ | ||
| 302 | 306 | start = i; | |
| 303 | } | ||
| 304 | /* Otherwise, ignore single level state. */ | ||
| 305 | else{ | ||
| 306 | /* Change state to decreasing. */ | ||
| 307 | state = -1; | ||
| 308 | /* Reset start location. */ | ||
| 309 | start = i; | ||
| 310 | } | ||
| 311 | } | ||
| 312 | } | ||
| 313 | /* Otherwise, items are level, so continue to next item pair. */ | ||
| 314 | |||
| 315 | /* Advance to next item pair in list. */ | ||
| 316 | 307996 | i++; | |
| 317 | } | ||
| 318 | |||
| 319 | /* Set results to output pointers. */ | ||
| 320 | 23692 | *ominmax_val = minmax_val; | |
| 321 | 23692 | *ominmax_type = minmax_type; | |
| 322 | 23692 | *ominmax_i = minmax_i; | |
| 323 | 23692 | *ominmax_alloc = minmax_alloc; | |
| 324 | 23692 | *ominmax_num = minmax_num; | |
| 325 | |||
| 326 | /* Return normally. */ | ||
| 327 | 23692 | return(0); | |
| 328 | } | ||
| 329 | |||
| 330 | /************************************************************************* | ||
| 331 | ************************************************************************** | ||
| 332 | #cat: distance - Takes two coordinate points and computes the | ||
| 333 | #cat: Euclidean distance between the two points. | ||
| 334 | |||
| 335 | Input: | ||
| 336 | x1 - x-coord of first point | ||
| 337 | y1 - y-coord of first point | ||
| 338 | x2 - x-coord of second point | ||
| 339 | y2 - y-coord of second point | ||
| 340 | Return Code: | ||
| 341 | Distance - computed Euclidean distance | ||
| 342 | **************************************************************************/ | ||
| 343 | 916173 | double distance(const int x1, const int y1, const int x2, const int y2) | |
| 344 | { | ||
| 345 | 916173 | double dx, dy, dist; | |
| 346 | |||
| 347 | /* Compute delta x between points. */ | ||
| 348 | 916173 | dx = (double)(x1 - x2); | |
| 349 | /* Compute delta y between points. */ | ||
| 350 | 916173 | dy = (double)(y1 - y2); | |
| 351 | /* Compute the squared distance between points. */ | ||
| 352 | 916173 | dist = (dx*dx) + (dy*dy); | |
| 353 | /* Take square root of squared distance. */ | ||
| 354 | 916173 | dist = sqrt(dist); | |
| 355 | |||
| 356 | /* Return the squared distance. */ | ||
| 357 | 916173 | return(dist); | |
| 358 | } | ||
| 359 | |||
| 360 | /************************************************************************* | ||
| 361 | ************************************************************************** | ||
| 362 | #cat: squared_distance - Takes two coordinate points and computes the | ||
| 363 | #cat: squared distance between the two points. | ||
| 364 | |||
| 365 | Input: | ||
| 366 | x1 - x-coord of first point | ||
| 367 | y1 - y-coord of first point | ||
| 368 | x2 - x-coord of second point | ||
| 369 | y2 - y-coord of second point | ||
| 370 | Return Code: | ||
| 371 | Distance - computed squared distance | ||
| 372 | **************************************************************************/ | ||
| 373 | 59855 | double squared_distance(const int x1, const int y1, const int x2, const int y2) | |
| 374 | { | ||
| 375 | 59855 | double dx, dy, dist; | |
| 376 | |||
| 377 | /* Compute delta x between points. */ | ||
| 378 | 59855 | dx = (double)(x1 - x2); | |
| 379 | /* Compute delta y between points. */ | ||
| 380 | 59855 | dy = (double)(y1 - y2); | |
| 381 | /* Compute the squared distance between points. */ | ||
| 382 | 59855 | dist = (dx*dx) + (dy*dy); | |
| 383 | |||
| 384 | /* Return the squared distance. */ | ||
| 385 | 59855 | return(dist); | |
| 386 | } | ||
| 387 | |||
| 388 | /************************************************************************* | ||
| 389 | ************************************************************************** | ||
| 390 | #cat: in_int_list - Determines if a specified value is store in a list of | ||
| 391 | #cat: integers and returns its location if found. | ||
| 392 | |||
| 393 | Input: | ||
| 394 | item - value to search for in list | ||
| 395 | list - list of integers to be searched | ||
| 396 | len - number of integers in search list | ||
| 397 | Return Code: | ||
| 398 | Zero or greater - first location found equal to search value | ||
| 399 | Negative - search value not found in the list of integers | ||
| 400 | **************************************************************************/ | ||
| 401 | 42192 | int in_int_list(const int item, const int *list, const int len) | |
| 402 | { | ||
| 403 | 42192 | int i; | |
| 404 | |||
| 405 | /* Foreach item in list ... */ | ||
| 406 |
2/2✓ Branch 5 → 3 taken 72602 times.
✓ Branch 5 → 6 taken 42115 times.
|
114717 | for(i = 0; i < len; i++){ |
| 407 | /* If search item found in list ... */ | ||
| 408 |
2/2✓ Branch 3 → 4 taken 72525 times.
✓ Branch 3 → 6 taken 77 times.
|
72602 | if(list[i] == item) |
| 409 | /* Return the location in list where found. */ | ||
| 410 | return(i); | ||
| 411 | } | ||
| 412 | |||
| 413 | /* If we get here, then search item not found in list, */ | ||
| 414 | /* so return -1 ==> NOT FOUND. */ | ||
| 415 | return(-1); | ||
| 416 | } | ||
| 417 | |||
| 418 | /************************************************************************* | ||
| 419 | ************************************************************************** | ||
| 420 | #cat: remove_from_int_list - Takes a position index into an integer list and | ||
| 421 | #cat: removes the value from the list, collapsing the resulting | ||
| 422 | #cat: list. | ||
| 423 | |||
| 424 | Input: | ||
| 425 | index - position of value to be removed from list | ||
| 426 | list - input list of integers | ||
| 427 | num - number of integers in the list | ||
| 428 | Output: | ||
| 429 | list - list with specified integer removed | ||
| 430 | num - decremented number of integers in list | ||
| 431 | Return Code: | ||
| 432 | Zero - successful completion | ||
| 433 | Negative - system error | ||
| 434 | **************************************************************************/ | ||
| 435 | |||
| 436 | /************************************************************************* | ||
| 437 | ************************************************************************** | ||
| 438 | #cat: ind_incr_position_dbl - Takes a double value and a list of doubles and | ||
| 439 | #cat: determines where in the list the double may be inserted, | ||
| 440 | #cat: preserving the increasing sorted order of the list. | ||
| 441 | |||
| 442 | Input: | ||
| 443 | val - value to be inserted into the list | ||
| 444 | list - list of double in increasing sorted order | ||
| 445 | num - number of values in the list | ||
| 446 | Return Code: | ||
| 447 | Zero or Positive - insertion position in the list | ||
| 448 | **************************************************************************/ | ||
| 449 | 33956 | int find_incr_position_dbl(const double val, double *list, const int num) | |
| 450 | { | ||
| 451 | 33956 | int i; | |
| 452 | |||
| 453 | /* Foreach item in double list ... */ | ||
| 454 |
2/2✓ Branch 5 → 3 taken 83638 times.
✓ Branch 5 → 6 taken 7775 times.
|
91413 | for(i = 0; i < num; i++){ |
| 455 | /* If the value is smaller than the current item in list ... */ | ||
| 456 |
2/2✓ Branch 3 → 4 taken 57457 times.
✓ Branch 3 → 6 taken 26181 times.
|
83638 | if(val < list[i]) |
| 457 | /* Then we found were to insert the value in the list maintaining */ | ||
| 458 | /* an increasing sorted order. */ | ||
| 459 | return(i); | ||
| 460 | |||
| 461 | /* Otherwise, the value is still larger than current item, so */ | ||
| 462 | /* continue to next item in the list. */ | ||
| 463 | } | ||
| 464 | |||
| 465 | /* Otherwise, we never found a slot within the list to insert the */ | ||
| 466 | /* the value, so place at the end of the sorted list. */ | ||
| 467 | return(i); | ||
| 468 | } | ||
| 469 | |||
| 470 | /************************************************************************* | ||
| 471 | ************************************************************************** | ||
| 472 | #cat: angle2line - Takes two coordinate points and computes the angle | ||
| 473 | #cat: to the line formed by the two points. | ||
| 474 | |||
| 475 | Input: | ||
| 476 | fx - x-coord of first point | ||
| 477 | fy - y-coord of first point | ||
| 478 | tx - x-coord of second point | ||
| 479 | ty - y-coord of second point | ||
| 480 | Return Code: | ||
| 481 | Angle - angle to the specified line | ||
| 482 | **************************************************************************/ | ||
| 483 | 128065 | double angle2line(const int fx, const int fy, const int tx, const int ty) | |
| 484 | { | ||
| 485 | 128065 | double dx, dy, theta; | |
| 486 | |||
| 487 | /* Compute slope of line connecting the 2 specified points. */ | ||
| 488 | 128065 | dy = (double)(fy - ty); | |
| 489 | 128065 | dx = (double)(tx - fx); | |
| 490 | /* If delta's are sufficiently small ... */ | ||
| 491 |
4/4✓ Branch 2 → 3 taken 10838 times.
✓ Branch 2 → 4 taken 117227 times.
✓ Branch 3 → 4 taken 10817 times.
✓ Branch 3 → 5 taken 21 times.
|
128065 | if((fabs(dx) < MIN_SLOPE_DELTA) && (fabs(dy) < MIN_SLOPE_DELTA)) |
| 492 | theta = 0.0; | ||
| 493 | /* Otherwise, compute angle to the line. */ | ||
| 494 | else | ||
| 495 | 128044 | theta = atan2(dy, dx); | |
| 496 | |||
| 497 | /* Return the compute angle in radians. */ | ||
| 498 | 128065 | return(theta); | |
| 499 | } | ||
| 500 | |||
| 501 | /************************************************************************* | ||
| 502 | ************************************************************************** | ||
| 503 | #cat: line2direction - Takes two coordinate points and computes the | ||
| 504 | #cat: directon (on a full circle) in which the first points | ||
| 505 | #cat: to the second. | ||
| 506 | |||
| 507 | Input: | ||
| 508 | fx - x-coord of first point (pointing from) | ||
| 509 | fy - y-coord of first point (pointing from) | ||
| 510 | tx - x-coord of second point (pointing to) | ||
| 511 | ty - y-coord of second point (pointing to) | ||
| 512 | ndirs - number of IMAP directions (in semicircle) | ||
| 513 | Return Code: | ||
| 514 | Direction - determined direction on a "full" circle | ||
| 515 | **************************************************************************/ | ||
| 516 | 3157 | int line2direction(const int fx, const int fy, | |
| 517 | const int tx, const int ty, const int ndirs) | ||
| 518 | { | ||
| 519 | 3157 | double theta, pi_factor; | |
| 520 | 3157 | int idir, full_ndirs; | |
| 521 | 3157 | static double pi2 = M_PI*2.0; | |
| 522 | |||
| 523 | /* Compute angle to line connecting the 2 points. */ | ||
| 524 | /* Coordinates are swapped and order of points reversed to */ | ||
| 525 | /* account for 0 direction is vertical and positive direction */ | ||
| 526 | /* is clockwise. */ | ||
| 527 | 3157 | theta = angle2line(ty, tx, fy, fx); | |
| 528 | |||
| 529 | /* Make sure the angle is positive. */ | ||
| 530 | 3157 | theta += pi2; | |
| 531 | 3157 | theta = fmod(theta, pi2); | |
| 532 | /* Convert from radians to integer direction on range [0..(ndirsX2)]. */ | ||
| 533 | /* Multiply radians by units/radian ((ndirsX2)/(2PI)), and you get */ | ||
| 534 | /* angle in integer units. */ | ||
| 535 | /* Compute number of directions on full circle. */ | ||
| 536 | 3157 | full_ndirs = ndirs<<1; | |
| 537 | /* Compute the radians to integer direction conversion factor. */ | ||
| 538 | 3157 | pi_factor = (double)full_ndirs/pi2; | |
| 539 | /* Convert radian angle to integer direction on full circle. */ | ||
| 540 | 3157 | theta *= pi_factor; | |
| 541 | /* Need to truncate precision so that answers are consistent */ | ||
| 542 | /* on different computer architectures when rounding doubles. */ | ||
| 543 |
1/2✗ Branch 3 → 4 not taken.
✓ Branch 3 → 5 taken 3157 times.
|
3157 | theta = trunc_dbl_precision(theta, TRUNC_SCALE); |
| 544 |
1/2✗ Branch 6 → 7 not taken.
✓ Branch 6 → 8 taken 3157 times.
|
3157 | idir = sround(theta); |
| 545 | /* Make sure on range [0..(ndirsX2)]. */ | ||
| 546 | 3157 | idir %= full_ndirs; | |
| 547 | |||
| 548 | /* Return the integer direction. */ | ||
| 549 | 3157 | return(idir); | |
| 550 | } | ||
| 551 | |||
| 552 | /************************************************************************* | ||
| 553 | ************************************************************************** | ||
| 554 | #cat: closest_dir_dist - Takes to integer IMAP directions and determines the | ||
| 555 | #cat: closest distance between them accounting for | ||
| 556 | #cat: wrap-around either at the beginning or ending of | ||
| 557 | #cat: the range of directions. | ||
| 558 | |||
| 559 | Input: | ||
| 560 | dir1 - integer value of the first direction | ||
| 561 | dir2 - integer value of the second direction | ||
| 562 | ndirs - the number of possible directions | ||
| 563 | Return Code: | ||
| 564 | Non-negative - distance between the 2 directions | ||
| 565 | **************************************************************************/ | ||
| 566 | 425292 | int closest_dir_dist(const int dir1, const int dir2, const int ndirs) | |
| 567 | { | ||
| 568 | 425292 | int d1, d2, dist; | |
| 569 | |||
| 570 | /* Initialize distance to -1 = INVALID. */ | ||
| 571 | 425292 | dist = INVALID_DIR; | |
| 572 | |||
| 573 | /* Measure shortest distance between to directions. */ | ||
| 574 | /* If both neighbors are VALID ... */ | ||
| 575 |
2/2✓ Branch 2 → 3 taken 406120 times.
✓ Branch 2 → 4 taken 19172 times.
|
425292 | if((dir1 >= 0)&&(dir2 >= 0)){ |
| 576 | /* Compute inner and outer distances to account for distances */ | ||
| 577 | /* that wrap around the end of the range of directions, which */ | ||
| 578 | /* may in fact be closer. */ | ||
| 579 | 406120 | d1 = abs(dir2 - dir1); | |
| 580 | 406120 | d2 = ndirs - d1; | |
| 581 | 406120 | dist = min(d1, d2); | |
| 582 | } | ||
| 583 | /* Otherwise one or both directions are INVALID, so ignore */ | ||
| 584 | /* and return INVALID. */ | ||
| 585 | |||
| 586 | /* Return determined closest distance. */ | ||
| 587 | 425292 | return(dist); | |
| 588 | } | ||
| 589 | |||
| 590 |