1 #include <math.h>
2
3 #include "xtux.h"
4 #include "version.h"
5
6 float sin_lookup[DEGREES];
7 float cos_lookup[DEGREES];
8
calc_lookup_tables(int degrees)9 void calc_lookup_tables(int degrees)
10 {
11 int i;
12 int semicircle, quadrant;
13 float d;
14 float s, c; /* Degree's (RADIANS) */
15 float inc = M_PI /(degrees/2); /* Convert from Radians to our degrees */
16
17 /*
18 We only need to calculate 1/4 of the circle, because the ratios can
19 be determined for the rest of the circle by one quadrant. We use a
20 lookup table (1Kb) so we don't have to call cos() & sin() all the time
21 */
22
23 semicircle = degrees / 2;
24 quadrant = degrees / 4;
25
26 for( d=0.0, i=0 ; i <= quadrant ; d+=inc, i++ ) {
27 s = sin(d);
28 c = cos(d);
29
30 /* 1st quadrant */
31 sin_lookup[i] = s;
32 cos_lookup[i] = c;
33 /* 2nd quadrant */
34 sin_lookup[semicircle - i] = s;
35 cos_lookup[semicircle - i] = -c;
36 /* 3rd quadrant */
37 sin_lookup[semicircle + i] = -s;
38 cos_lookup[semicircle + i] = -c;
39 /* 4th quadrant */
40 if( i ) {
41 sin_lookup[degrees - i] = -s;
42 cos_lookup[degrees - i] = c;
43 }
44 }
45
46 /* Correct some floating point inaccuracies */
47 sin_lookup[ quadrant * 0 ] = 0.0;
48 cos_lookup[ quadrant * 1 ] = 0.0;
49 sin_lookup[ quadrant * 2 ] = 0.0;
50 cos_lookup[ quadrant * 3 ] = 0.0;
51
52 }
53
54
point_distance(point A,point B)55 int point_distance(point A, point B)
56 {
57 register int x, y;
58
59 x = B.x - A.x;
60 y = B.y - A.y;
61 return (int)sqrt( (double)(x * x + y * y) );
62
63 }
64
65
66 /* Return the angle (0.255) between U and V using dot product */
angle_between(vector_t U,vector_t V)67 byte angle_between(vector_t U, vector_t V)
68 {
69 float dot_product;
70 float deg = DEGREES/(M_PI*2); /* to convert from radians -> our degrees*/
71 float l_u, l_v; /* Vector lengths of U and V */
72 byte angle;
73
74 /*
75 u . v = ||u|| ||v|| cos theta
76 theta = cos-1 (u.v) / (||u|| ||v||)
77
78 u.v = u1v1 + u2v2
79
80 */
81
82 l_u = sqrt( U.x * U.x + U.y * U.y );
83 l_v = sqrt( V.x * V.x + V.y * V.y );
84
85 if( l_u == 0 || l_v == 0 )
86 return 0;
87
88 dot_product = U.x * V.x + U.y + V.y;
89 angle = deg * acos( dot_product / (l_u + l_v) );
90
91 if( V.x < U.x )
92 angle = DEGREES - angle;
93
94 return angle;
95
96 }
97
98
99
100 /* Originally from Graphic Gems 2
101 *
102 * This function computes whether two line segments,
103 * respectively joining the input points (x1,y1) -- (x2,y2)
104 * and the input points (x3,y3) -- (x4,y4) intersect.
105 * If the lines intersect, the output variables x, y are
106 * set to coordinates of the point of intersection.
107 *
108 * All values are in integers. The returned value is rounded
109 * to the nearest integer point.
110 *
111 * If non-integral grid points are relevant, the function
112 * can easily be transformed by substituting floating point
113 * calculations instead of integer calculations.
114 *
115 * Entry
116 * x1, y1, x2, y2 Coordinates of endpoints of one segment.
117 * x3, y3, x4, y4 Coordinates of endpoints of other segment.
118 *
119 * Exit
120 * x, y Coordinates of intersection point.
121 *
122 * The value returned by the function is one of:
123 *
124 * DONT_INTERSECT 0
125 * DO_INTERSECT 1
126 * COLLINEAR 2
127 *
128 * Error conditions:
129 *
130 * Depending upon the possible ranges, and particularly on 16-bit
131 * computers, care should be taken to protect from overflow.
132 *
133 * In the following code, 'long' values have been used for this
134 * purpose, instead of 'int'.
135 *
136 */
137
138 /**************************************************************
139 * *
140 * NOTE: The following macro to determine if two numbers *
141 * have the same sign, is for 2's complement number *
142 * representation. It will need to be modified for other *
143 * number systems. *
144 * *
145 **************************************************************/
146
147 #define SAME_SIGNS( a, b ) \
148 (((long) ((unsigned long) a ^ (unsigned long) b)) >=0 )
149
150
intersection_test(point A,point B,point C,point D,point * INTERSECTION)151 int intersection_test(point A, point B, point C, point D,
152 point *INTERSECTION)
153 {
154 long a1, b1, c1;
155 long a2, b2, c2;
156 long r1, r2, r3, r4;
157 long denom, offset, num;
158
159
160 /* Compute a1, b1, c1, where line joining points 1 and 2
161 * is "a1 x + b1 y + c1 = 0".
162 */
163
164 a1 = B.y - A.y;
165 b1 = A.x - B.x;
166 c1 = B.x * A.y - A.x * B.y;
167
168 /* Compute r3 and r4.
169 */
170 r3 = a1 * C.x + b1 * C.y + c1;
171 r4 = a1 * D.x + b1 * D.y + c1;
172
173 /* Check signs of r3 and r4. If both point 3 and point 4 lie on
174 * same side of line 1, the line segments do not intersect.
175 */
176
177 if ( r3 != 0 &&
178 r4 != 0 &&
179 SAME_SIGNS( r3, r4 ))
180 return 0;
181
182 /* Compute a2, b2, c2 */
183
184 a2 = D.y - C.y;
185 b2 = C.x - D.x;
186 c2 = D.x * C.y - C.x * D.y;
187
188 /* Compute r1 and r2 */
189
190 r1 = a2 * A.x + b2 * A.y + c2;
191 r2 = a2 * B.x + b2 * B.y + c2;
192
193 /* Check signs of r1 and r2. If both point 1 and point 2 lie
194 * on same side of second line segment, the line segments do
195 * not intersect.
196 */
197
198 if ( r1 != 0 &&
199 r2 != 0 &&
200 SAME_SIGNS( r1, r2 ))
201 return 0;
202
203 /* Line segments intersect: compute intersection point.
204 */
205
206 denom = a1 * b2 - a2 * b1;
207 if ( denom == 0 )
208 return 0;
209 offset = denom < 0 ? - denom / 2 : denom / 2;
210
211 /* The denom/2 is to get rounding instead of truncating. It
212 * is added or subtracted to the numerator, depending upon the
213 * sign of the numerator.
214 */
215
216 num = b1 * c2 - b2 * c1;
217 INTERSECTION->x = ( num < 0 ? num - offset : num + offset ) / denom;
218
219 num = a2 * c1 - a1 * c2;
220 INTERSECTION->y = ( num < 0 ? num - offset : num + offset ) / denom;
221
222 return 1;
223 }
224
225
226
227
228
229
230
231
232
233