1 package org.lcsim.recon.tracking.spacegeom;
2
3
4
5
6
7
8
9 public class TwoD
10 {
11
12
13
14
15
16
17
18
19 public static double area2(TwoSpacePoint a, TwoSpacePoint b, TwoSpacePoint c)
20 {
21 double area=((c.x() - b.x())*(a.y() - b.y())) - ((a.x() - b.x())*(c.y() - b.y()));
22 return area;
23 }
24
25 public static int areaSign( TwoSpacePoint a, TwoSpacePoint b, TwoSpacePoint c )
26 {
27 double area2;
28
29 area2 = ( b.x() - a.x() ) * ( c.y() - a.y() ) -
30 ( c.x() - a.x() ) * ( b.y() - a.y() );
31
32
33
34 if ( area2 > 0.5 ) return 1;
35 else if ( area2 < -0.5 ) return -1;
36 else return 0;
37 }
38
39
40
41
42
43
44
45
46 public static boolean left( TwoSpacePoint a, TwoSpacePoint b, TwoSpacePoint c )
47 {
48 return areaSign( a, b, c ) > 0;
49 }
50
51
52
53
54
55
56
57
58 public static boolean leftOn( TwoSpacePoint a, TwoSpacePoint b , TwoSpacePoint c)
59 {
60 return areaSign( a, b, c) >= 0;
61 }
62
63
64
65
66
67
68
69
70 public static boolean collinear( TwoSpacePoint a, TwoSpacePoint b, TwoSpacePoint c)
71 {
72 return areaSign( a, b, c) == 0;
73 }
74
75
76
77
78
79
80
81
82 public static boolean between( TwoSpacePoint a, TwoSpacePoint b, TwoSpacePoint c)
83 {
84 TwoSpacePoint ba, ca;
85
86 if ( ! collinear( a, b, c) )
87 return false;
88
89
90 if ( a.x() != b.x() )
91 return ((a.x() <= c.x()) && (c.x() <= b.x())) ||
92 ((a.x() >= c.x()) && (c.x() >= b.x()));
93 else
94 return ((a.y() <= c.y()) && (c.y() <= b.y())) ||
95 ((a.y() >= c.y()) && (c.y() >= b.y()));
96 }
97
98
99
100
101
102
103
104
105
106 public static boolean intersect( TwoSpacePoint a, TwoSpacePoint b, TwoSpacePoint c, TwoSpacePoint d )
107 {
108 if ( intersectProp( a, b, c, d ) )
109 return true;
110
111 else if ( between( a, b, c)
112 || between( a, b, d )
113 || between( c, d, a )
114 || between( c, d, b ) )
115 return true;
116
117 else
118 return false;
119 }
120
121
122
123
124
125
126
127
128
129 public static boolean intersectProp( TwoSpacePoint a, TwoSpacePoint b, TwoSpacePoint c, TwoSpacePoint d )
130 {
131
132 if (
133 collinear(a,b,c) ||
134 collinear(a,b,d) ||
135 collinear(c,d,a) ||
136 collinear(c,d,b))
137 return false;
138
139 return
140 xOr( left(a,b,c), left(a,b,d) )
141 && xOr( left(c,d,a), left(c,d,b) );
142 }
143
144
145
146
147
148 public static boolean xOr( boolean x, boolean y )
149 {
150
151
152 return !x ^ !y;
153 }
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168 public char segSegInt( TwoSpacePoint a, TwoSpacePoint b, TwoSpacePoint c, TwoSpacePoint d, TwoSpacePoint p, TwoSpacePoint q )
169 {
170 double s, t;
171 double num, denom;
172 char code = '?';
173
174
175 denom = a.x() * ( d.y() - c.y() ) +
176 b.x() * ( c.y() - d.y() ) +
177 d.x() * ( b.y() - a.y() ) +
178 c.x() * ( a.y() - b.y() );
179
180
181 if (denom == 0.0)
182 return parallelInt(a, b, c, d, p, q);
183
184 num = a.x() * ( d.y() - c.y() ) +
185 c.x() * ( a.y() - d.y() ) +
186 d.x() * ( c.y() - a.y() );
187 if ( (num == 0.0) || (num == denom) ) code = 'v';
188 s = num / denom;
189 System.out.println("SegSegInt: num=" + num + ",denom=" + denom + ",s="+s);
190
191 num = -( a.x() * ( c.y() - b.y() ) +
192 b.x() * ( a.y() - c.y() ) +
193 c.x() * ( b.y() - a.y() ) );
194 if ( (num == 0.0) || (num == denom) ) code = 'v';
195 t = num / denom;
196 System.out.println("SegSegInt: num=" +num + ",denom=" + denom + ",t=" + t);
197
198 if ( (0.0 < s) && (s < 1.0) &&
199 (0.0 < t) && (t < 1.0) )
200 code = '1';
201 else if ( (0.0 > s) || (s > 1.0) ||
202 (0.0 > t) || (t > 1.0) )
203 code = '0';
204
205 p._x = a.x() + s * ( b.x() - a.x() );
206 p._y = a.y() + s * ( b.y() - a.y() );
207
208 return code;
209 }
210
211 public char parallelInt( TwoSpacePoint a, TwoSpacePoint b, TwoSpacePoint c, TwoSpacePoint d, TwoSpacePoint p, TwoSpacePoint q )
212 {
213 if ( !collinear( a, b, c) )
214 return '0';
215
216 if ( between1( a, b, c ) && between1( a, b, d ) )
217 {
218 assigndi( p, c );
219 assigndi( q, d );
220 return 'e';
221 }
222 if ( between1( c, d, a ) && between1( c, d, b ) )
223 {
224 assigndi( p, a );
225 assigndi( q, b );
226 return 'e';
227 }
228 if ( between1( a, b, c ) && between1( c, d, b ) )
229 {
230 assigndi( p, c );
231 assigndi( q, b );
232 return 'e';
233 }
234 if ( between1( a, b, c ) && between1( c, d, a ) )
235 {
236 assigndi( p, c );
237 assigndi( q, a );
238 return 'e';
239 }
240 if ( between1( a, b, d ) && between1( c, d, b ) )
241 {
242 assigndi( p, d );
243 assigndi( q, b );
244 return 'e';
245 }
246 if ( between1( a, b, d ) && between1( c, d, a ) )
247 {
248 assigndi( p, d );
249 assigndi( q, a );
250 return 'e';
251 }
252 return '0';
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272 }
273
274 public void assigndi( TwoSpacePoint p, TwoSpacePoint a )
275 {
276 p._x = a.x();
277 p._y = a.y();
278 }
279
280
281
282
283
284
285
286 public boolean between1( TwoSpacePoint a, TwoSpacePoint b, TwoSpacePoint c )
287 {
288 TwoSpacePoint ba, ca;
289
290
291 if ( a.x() != b.x() )
292 return ((a.x() <= c.x()) && (c.x() <= b.x())) ||
293 ((a.x() >= c.x()) && (c.x() >= b.x()));
294 else
295 return ((a.y() <= c.y()) && (c.y() <= b.y())) ||
296 ((a.y() >= c.y()) && (c.y() >= b.y()));
297 }
298 }