1 package org.lcsim.spacegeom;
2 /**
3 * A class to handle operations in a 2D plane.
4 *
5 *@author Norman A. Graf
6 *@version $Id: TwoD.java,v 1.1.1.1 2010/12/01 00:15:57 jeremy Exp $
7 *
8 */
9 public class TwoD
10 {
11
12 /**
13 * Twice the signed area of the triangle determined by a,b,c; positive if counterclockwise, negative if clockwisew
14 * @param a First point on the triangle.
15 * @param b Second point on the triangle.
16 * @param c Third point on the triangle.
17 * @return the are of the traingle, positive if counterclockwise, negative if clockwisew
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 /* The area sign should be an integer. */
34 if ( area2 > 0.5 ) return 1;
35 else if ( area2 < -0.5 ) return -1;
36 else return 0;
37 }
38
39 /**
40 * Determines whether a point is to the left of a line segment define by its endpoints.
41 * @param a The first point on the segment.
42 * @param b The second point on the segment.
43 * @param c The point to check.
44 * @return true if and only if the point c is to the left of the directed line through a and b.
45 */
46 public static boolean left( TwoSpacePoint a, TwoSpacePoint b, TwoSpacePoint c )
47 {
48 return areaSign( a, b, c ) > 0;
49 }
50
51 /**
52 * Determines whether a point is to the left or on a line segment define by its endpoints.
53 * @param a The first point on the segment.
54 * @param b The second point on the segment.
55 * @param c The point to check.
56 * @return true if and only if the point c is to the left or on the directed line through a and b.
57 */
58 public static boolean leftOn( TwoSpacePoint a, TwoSpacePoint b , TwoSpacePoint c)
59 {
60 return areaSign( a, b, c) >= 0;
61 }
62
63 /**
64 * Determines whether a point is on or collinear with a line segment define by its endpoints.
65 * @param a The first point on the segment.
66 * @param b The second point on the segment.
67 * @param c The point to check.
68 * @return true if and only if the point c is on or collinear with the directed line through a and b.
69 */
70 public static boolean collinear( TwoSpacePoint a, TwoSpacePoint b, TwoSpacePoint c)
71 {
72 return areaSign( a, b, c) == 0;
73 }
74
75 /**
76 * Determines whether a point is on a line segment define by its endpoints.
77 * @param a The first point on the segment.
78 * @param b The second point on the segment.
79 * @param c The point to check.
80 * @return true if and only if the point c is on the closed line segment through a and b.
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 /* If ab not vertical, check betweenness on x; else on y. */
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 * Determines whether two lines defined by their segments intersect.
100 * @param a The first point on the first line segment.
101 * @param b The second point on the first line segment.
102 * @param c The first point on the second line segment.
103 * @param d The second point on the second line segment.
104 * @return true if and only if the segments ab and cd intersect, properly or improperly.
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 * Determines whether two line segments intersect.
123 * @param a The first point on the first line segment.
124 * @param b The second point on the first line segment.
125 * @param c The first point on the second line segment.
126 * @param d The second point on the second line segment.
127 * @return true if and only if the segments ab and cd intersect properly.
128 */
129 public static boolean intersectProp( TwoSpacePoint a, TwoSpacePoint b, TwoSpacePoint c, TwoSpacePoint d )
130 {
131 /* Eliminate improper cases. */
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 *Exclusive or: true iff exactly one argument is true.
146 */
147
148 public static boolean xOr( boolean x, boolean y )
149 {
150 /* The arguments are negated to ensure that they are 0/1 values. */
151 /* (Idea due to Michael Baldwin.) */
152 return !x ^ !y;
153 }
154
155 /*---------------------------------------------------------------------
156 segSegInt: Finds the point of intersection p between two closed
157 segments ab and cd. Returns p and a char with the following meaning:
158 'e': The segments collinearly overlap, sharing a point.
159 'v': An endpoint (vertex) of one segment is on the other segment,
160 but 'e' doesn't hold.
161 '1': The segments intersect properly (i.e., they share a point and
162 neither 'v' nor 'e' holds).
163 '0': The segments do not intersect (i.e., they share no points).
164 Note that two collinear segments that share just one point, an endpoint
165 of each, returns 'e' rather than 'v' as one might expect.
166 ---------------------------------------------------------------------*/
167
168 public char segSegInt( TwoSpacePoint a, TwoSpacePoint b, TwoSpacePoint c, TwoSpacePoint d, TwoSpacePoint p, TwoSpacePoint q )
169 {
170 double s, t; /* The two parameters of the parametric eqns. */
171 double num, denom; /* Numerator and denoninator of equations. */
172 char code = '?'; /* Return char characterizing intersection. */
173 // p.x() = p.y() = 100.0; /* For testing purposes only... */
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 /* If denom is zero, then segments are parallel: handle separately. */
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 if ( Between1( a, b, c ) ) {
255 Assigndi( p, c );
256 return 'e';
257 }
258 if ( Between1( a, b, d ) ) {
259 Assigndi( p, d );
260 return 'e';
261 }
262 if ( Between1( c, d, a ) ) {
263 Assigndi( p, a );
264 return 'e';
265 }
266 if ( Between1( c, d, b ) ) {
267 Assigndi( p, b );
268 return 'e';
269 }
270 return '0';
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 Returns TRUE iff point c lies on the closed segement ab.
282 Assumes it is already known that abc are collinear.
283 (This is the only difference with Between().)
284 ---------------------------------------------------------------------*/
285
286 public boolean between1( TwoSpacePoint a, TwoSpacePoint b, TwoSpacePoint c )
287 {
288 TwoSpacePoint ba, ca;
289
290 /* If ab not vertical, check betweenness on x; else on y. */
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 }