| 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: LINE.C | ||
| 49 | AUTHOR: Michael D. Garris | ||
| 50 | DATE: 03/16/1999 | ||
| 51 | |||
| 52 | Contains routines that compute contiguous linear trajectories | ||
| 53 | between two coordinate points required by the NIST Latent | ||
| 54 | Fingerprint System (LFS). | ||
| 55 | |||
| 56 | *********************************************************************** | ||
| 57 | ROUTINES: | ||
| 58 | line_points() | ||
| 59 | ***********************************************************************/ | ||
| 60 | |||
| 61 | #include <stdio.h> | ||
| 62 | #include <lfs.h> | ||
| 63 | |||
| 64 | /************************************************************************* | ||
| 65 | ************************************************************************** | ||
| 66 | #cat: line_points - Returns the contiguous coordinates of a line connecting | ||
| 67 | #cat: 2 specified points. | ||
| 68 | |||
| 69 | Input: | ||
| 70 | x1 - x-coord of first point | ||
| 71 | y1 - y-coord of first point | ||
| 72 | x2 - x-coord of second point | ||
| 73 | y2 - y-coord of second point | ||
| 74 | Output: | ||
| 75 | ox_list - x-coords along line trajectory | ||
| 76 | oy_list - y-coords along line trajectory | ||
| 77 | onum - number of points along line trajectory | ||
| 78 | Return Code: | ||
| 79 | Zero - successful completion | ||
| 80 | Negative - system error | ||
| 81 | **************************************************************************/ | ||
| 82 | 22811 | int line_points(int **ox_list, int **oy_list, int *onum, | |
| 83 | const int x1, const int y1, const int x2, const int y2) | ||
| 84 | { | ||
| 85 | 22811 | int asize; | |
| 86 | 22811 | int dx, dy, adx, ady; | |
| 87 | 22811 | int x_incr, y_incr; | |
| 88 | 22811 | int i, inx, iny, intx, inty; | |
| 89 | 22811 | double x_factor, y_factor; | |
| 90 | 22811 | double rx, ry; | |
| 91 | 22811 | int ix, iy; | |
| 92 | 22811 | int *x_list, *y_list; | |
| 93 | |||
| 94 | /* Compute maximum number of points needed to hold line segment. */ | ||
| 95 |
2/2✓ Branch 0 (2→3) taken 9800 times.
✓ Branch 1 (2→4) taken 13011 times.
|
22811 | asize = max(abs(x2-x1)+2, abs(y2-y1)+2); |
| 96 | |||
| 97 | /* Allocate x and y-pixel coordinate lists to length 'asize'. */ | ||
| 98 | 22811 | x_list = (int *)g_malloc(asize * sizeof(int)); | |
| 99 | 22811 | y_list = (int *)g_malloc(asize * sizeof(int)); | |
| 100 | |||
| 101 | /* Compute delta x and y. */ | ||
| 102 | 22811 | dx = x2 - x1; | |
| 103 | 22811 | dy = y2 - y1; | |
| 104 | |||
| 105 | /* Set x and y increments. */ | ||
| 106 |
2/2✓ Branch 0 (7→8) taken 2829 times.
✓ Branch 1 (7→9) taken 19982 times.
|
22811 | if(dx >= 0) |
| 107 | x_incr = 1; | ||
| 108 | else | ||
| 109 | 2829 | x_incr = -1; | |
| 110 | |||
| 111 |
2/2✓ Branch 0 (9→10) taken 10820 times.
✓ Branch 1 (9→11) taken 11991 times.
|
22811 | if(dy >= 0) |
| 112 | y_incr = 1; | ||
| 113 | else | ||
| 114 | 10820 | y_incr = -1; | |
| 115 | |||
| 116 | /* Compute |DX| and |DY|. */ | ||
| 117 | 22811 | adx = abs(dx); | |
| 118 | 22811 | ady = abs(dy); | |
| 119 | |||
| 120 | /* Set x-orientation. */ | ||
| 121 |
2/2✓ Branch 0 (11→12) taken 13011 times.
✓ Branch 1 (11→13) taken 9800 times.
|
22811 | if(adx > ady) |
| 122 | inx = 1; | ||
| 123 | else | ||
| 124 | 13011 | inx = 0; | |
| 125 | |||
| 126 | /* Set y-orientation. */ | ||
| 127 |
2/2✓ Branch 0 (13→14) taken 10788 times.
✓ Branch 1 (13→15) taken 12023 times.
|
22811 | if(ady > adx) |
| 128 | iny = 1; | ||
| 129 | else | ||
| 130 | 10788 | iny = 0; | |
| 131 | |||
| 132 | /* CASE 1: |DX| > |DY| */ | ||
| 133 | /* Increment in X by +-1 */ | ||
| 134 | /* in Y by +-|DY|/|DX| */ | ||
| 135 | /* inx = 1 */ | ||
| 136 | /* iny = 0 */ | ||
| 137 | /* intx = 1 (inx) */ | ||
| 138 | /* inty = 0 (iny) */ | ||
| 139 | /* CASE 2: |DX| < |DY| */ | ||
| 140 | /* Increment in Y by +-1 */ | ||
| 141 | /* in X by +-|DX|/|DY| */ | ||
| 142 | /* inx = 0 */ | ||
| 143 | /* iny = 1 */ | ||
| 144 | /* intx = 0 (inx) */ | ||
| 145 | /* inty = 1 (iny) */ | ||
| 146 | /* CASE 3: |DX| == |DY| */ | ||
| 147 | /* inx = 0 */ | ||
| 148 | /* iny = 0 */ | ||
| 149 | /* intx = 1 */ | ||
| 150 | /* inty = 1 */ | ||
| 151 | 22811 | intx = 1 - iny; | |
| 152 | 22811 | inty = 1 - inx; | |
| 153 | |||
| 154 | /* DX */ | ||
| 155 | /* x_factor = (inx * +-1) + ( iny * ------------ ) */ | ||
| 156 | /* max(1, |DY|) */ | ||
| 157 | /* */ | ||
| 158 |
2/2✓ Branch 0 (15→16) taken 22212 times.
✓ Branch 1 (15→17) taken 599 times.
|
22811 | x_factor = (inx * x_incr) + (iny * ((double)dx/max(1, ady))); |
| 159 | |||
| 160 | /* DY */ | ||
| 161 | /* y_factor = (iny * +-1) + ( inx * ------------ ) */ | ||
| 162 | /* max(1, |DX|) */ | ||
| 163 | /* */ | ||
| 164 |
2/2✓ Branch 0 (17→18) taken 21954 times.
✓ Branch 1 (17→19) taken 857 times.
|
22811 | y_factor = (iny * y_incr) + (inx * ((double)dy/max(1, adx))); |
| 165 | |||
| 166 | /* Initialize integer coordinates. */ | ||
| 167 | 22811 | ix = x1; | |
| 168 | 22811 | iy = y1; | |
| 169 | /* Set floating point coordinates. */ | ||
| 170 | 22811 | rx = (double)x1; | |
| 171 | 22811 | ry = (double)y1; | |
| 172 | |||
| 173 | /* Initialize to first point in line segment. */ | ||
| 174 | 22811 | i = 0; | |
| 175 | |||
| 176 | /* Assign first point into coordinate list. */ | ||
| 177 | 22811 | x_list[i] = x1; | |
| 178 | 22811 | y_list[i++] = y1; | |
| 179 | |||
| 180 |
2/2✓ Branch 0 (32→20) taken 607148 times.
✓ Branch 1 (32→33) taken 22811 times.
|
629959 | while((ix != x2) || (iy != y2)){ |
| 181 | |||
| 182 |
1/2✗ Branch 0 (20→21) not taken.
✓ Branch 1 (20→25) taken 607148 times.
|
607148 | if(i >= asize){ |
| 183 | ✗ | fprintf(stderr, "ERROR : line_points : coord list overflow\n"); | |
| 184 | ✗ | g_free(x_list); | |
| 185 | ✗ | g_free(y_list); | |
| 186 | ✗ | return(-412); | |
| 187 | } | ||
| 188 | |||
| 189 | 607148 | rx += x_factor; | |
| 190 | 607148 | ry += y_factor; | |
| 191 | |||
| 192 | /* Need to truncate precision so that answers are consistent */ | ||
| 193 | /* on different computer architectures when truncating doubles. */ | ||
| 194 |
1/2✗ Branch 0 (25→26) not taken.
✓ Branch 1 (25→27) taken 607148 times.
|
607148 | rx = trunc_dbl_precision(rx, TRUNC_SCALE); |
| 195 |
1/2✗ Branch 0 (28→29) not taken.
✓ Branch 1 (28→30) taken 607148 times.
|
607148 | ry = trunc_dbl_precision(ry, TRUNC_SCALE); |
| 196 | |||
| 197 | /* Compute new x and y-pixel coords in floating point and */ | ||
| 198 | /* then round to the nearest integer. */ | ||
| 199 | 607148 | ix = (intx * (ix + x_incr)) + (iny * (int)(rx + 0.5)); | |
| 200 | 607148 | iy = (inty * (iy + y_incr)) + (inx * (int)(ry + 0.5)); | |
| 201 | |||
| 202 | /* Assign first point into coordinate list. */ | ||
| 203 | 607148 | x_list[i] = ix; | |
| 204 | 607148 | y_list[i++] = iy; | |
| 205 | } | ||
| 206 | |||
| 207 | /* Set output pointers. */ | ||
| 208 | 22811 | *ox_list = x_list; | |
| 209 | 22811 | *oy_list = y_list; | |
| 210 | 22811 | *onum = i; | |
| 211 | |||
| 212 | /* Return normally. */ | ||
| 213 | 22811 | return(0); | |
| 214 | } | ||
| 215 |