1 /*******************************************************************************
2
3 License:
4 This software was developed at the National Institute of Standards and
5 Technology (NIST) by employees of the Federal Government in the course
6 of their official duties. Pursuant to title 17 Section 105 of the
7 United States Code, this software is not subject to copyright protection
8 and is in the public domain. NIST assumes no responsibility whatsoever for
9 its use by other parties, and makes no guarantees, expressed or implied,
10 about its quality, reliability, or any other characteristic.
11
12 Disclaimer:
13 This software was developed to promote biometric standards and biometric
14 technology testing for the Federal Government in accordance with the USA
15 PATRIOT Act and the Enhanced Border Security and Visa Entry Reform Act.
16 Specific hardware and software products identified in this software were used
17 in order to perform the software development. In no case does such
18 identification imply recommendation or endorsement by the National Institute
19 of Standards and Technology, nor does it imply that the products and equipment
20 identified are necessarily the best available for the purpose.
21
22 *******************************************************************************/
23
24 /***********************************************************************
25 LIBRARY: LFS - NIST Latent Fingerprint System
26
27 FILE: LINE.C
28 AUTHOR: Michael D. Garris
29 DATE: 03/16/1999
30
31 Contains routines that compute contiguous linear trajectories
32 between two coordinate points required by the NIST Latent
33 Fingerprint System (LFS).
34
35 ***********************************************************************
36 ROUTINES:
37 line_points()
38 ***********************************************************************/
39
40 #include <stdio.h>
41 #include <stdlib.h>
42 #include <lfs.h>
43
44 /*************************************************************************
45 **************************************************************************
46 #cat: line_points - Returns the contiguous coordinates of a line connecting
47 #cat: 2 specified points.
48
49 Input:
50 x1 - x-coord of first point
51 y1 - y-coord of first point
52 x2 - x-coord of second point
53 y2 - y-coord of second point
54 Output:
55 ox_list - x-coords along line trajectory
56 oy_list - y-coords along line trajectory
57 onum - number of points along line trajectory
58 Return Code:
59 Zero - successful completion
60 Negative - system error
61 **************************************************************************/
line_points(int ** ox_list,int ** oy_list,int * onum,const int x1,const int y1,const int x2,const int y2)62 int line_points(int **ox_list, int **oy_list, int *onum,
63 const int x1, const int y1, const int x2, const int y2)
64 {
65 int asize;
66 int dx, dy, adx, ady;
67 int x_incr, y_incr;
68 int i, inx, iny, intx, inty;
69 double x_factor, y_factor;
70 double rx, ry;
71 int ix, iy;
72 int *x_list, *y_list;
73
74 /* Compute maximum number of points needed to hold line segment. */
75 asize = max(abs(x2-x1)+2, abs(y2-y1)+2);
76
77 /* Allocate x and y-pixel coordinate lists to length 'asize'. */
78 x_list = (int *)malloc(asize*sizeof(int));
79 if(x_list == (int *)NULL){
80 fprintf(stderr, "ERROR : line_points : malloc : x_list\n");
81 return(-410);
82 }
83 y_list = (int *)malloc(asize*sizeof(int));
84 if(y_list == (int *)NULL){
85 free(x_list);
86 fprintf(stderr, "ERROR : line_points : malloc : y_list\n");
87 return(-411);
88 }
89
90 /* Compute delta x and y. */
91 dx = x2 - x1;
92 dy = y2 - y1;
93
94 /* Set x and y increments. */
95 if(dx >= 0)
96 x_incr = 1;
97 else
98 x_incr = -1;
99
100 if(dy >= 0)
101 y_incr = 1;
102 else
103 y_incr = -1;
104
105 /* Compute |DX| and |DY|. */
106 adx = abs(dx);
107 ady = abs(dy);
108
109 /* Set x-orientation. */
110 if(adx > ady)
111 inx = 1;
112 else
113 inx = 0;
114
115 /* Set y-orientation. */
116 if(ady > adx)
117 iny = 1;
118 else
119 iny = 0;
120
121 /* CASE 1: |DX| > |DY| */
122 /* Increment in X by +-1 */
123 /* in Y by +-|DY|/|DX| */
124 /* inx = 1 */
125 /* iny = 0 */
126 /* intx = 1 (inx) */
127 /* inty = 0 (iny) */
128 /* CASE 2: |DX| < |DY| */
129 /* Increment in Y by +-1 */
130 /* in X by +-|DX|/|DY| */
131 /* inx = 0 */
132 /* iny = 1 */
133 /* intx = 0 (inx) */
134 /* inty = 1 (iny) */
135 /* CASE 3: |DX| == |DY| */
136 /* inx = 0 */
137 /* iny = 0 */
138 /* intx = 1 */
139 /* inty = 1 */
140 intx = 1 - iny;
141 inty = 1 - inx;
142
143 /* DX */
144 /* x_factor = (inx * +-1) + ( iny * ------------ ) */
145 /* max(1, |DY|) */
146 /* */
147 x_factor = (inx * x_incr) + (iny * ((double)dx/max(1, ady)));
148
149 /* DY */
150 /* y_factor = (iny * +-1) + ( inx * ------------ ) */
151 /* max(1, |DX|) */
152 /* */
153 y_factor = (iny * y_incr) + (inx * ((double)dy/max(1, adx)));
154
155 /* Initialize integer coordinates. */
156 ix = x1;
157 iy = y1;
158 /* Set floating point coordinates. */
159 rx = (double)x1;
160 ry = (double)y1;
161
162 /* Initialize to first point in line segment. */
163 i = 0;
164
165 /* Assign first point into coordinate list. */
166 x_list[i] = x1;
167 y_list[i++] = y1;
168
169 while((ix != x2) || (iy != y2)){
170
171 if(i >= asize){
172 fprintf(stderr, "ERROR : line_points : coord list overflow\n");
173 free(x_list);
174 free(y_list);
175 return(-412);
176 }
177
178 rx += x_factor;
179 ry += y_factor;
180
181 /* Need to truncate precision so that answers are consistent */
182 /* on different computer architectures when truncating doubles. */
183 rx = trunc_dbl_precision(rx, TRUNC_SCALE);
184 ry = trunc_dbl_precision(ry, TRUNC_SCALE);
185
186 /* Compute new x and y-pixel coords in floating point and */
187 /* then round to the nearest integer. */
188 ix = (intx * (ix + x_incr)) + (iny * (int)(rx + 0.5));
189 iy = (inty * (iy + y_incr)) + (inx * (int)(ry + 0.5));
190
191 /* Assign first point into coordinate list. */
192 x_list[i] = ix;
193 y_list[i++] = iy;
194 }
195
196 /* Set output pointers. */
197 *ox_list = x_list;
198 *oy_list = y_list;
199 *onum = i;
200
201 /* Return normally. */
202 return(0);
203 }
204