1/* $Id$ $Revision$ */
2/* vim:set shiftwidth=4 ts=8: */
3
4/*************************************************************************
5 * Copyright (c) 2011 AT&T Intellectual Property
6 * All rights reserved. This program and the accompanying materials
7 * are made available under the terms of the Eclipse Public License v1.0
8 * which accompanies this distribution, and is available at
9 * http://www.eclipse.org/legal/epl-v10.html
10 *
11 * Contributors: See CVS logs. Details at http://www.graphviz.org/
12 *************************************************************************/
13
14/* geometric functions (e.g. on points and boxes) with application to, but
15 * no specific dependence on graphs */
16
17#include "config.h"
18
19#include "geom.h"
20#include "geomprocs.h"
21#ifdef _WIN32
22#define inline
23#endif
24
25box mkbox(point p, point q)
26{
27 box r;
28
29 if (p.x < q.x) {
30 r.LL.x = p.x;
31 r.UR.x = q.x;
32 } else {
33 r.LL.x = q.x;
34 r.UR.x = p.x;
35 }
36 if (p.y < q.y) {
37 r.LL.y = p.y;
38 r.UR.y = q.y;
39 } else {
40 r.LL.y = q.y;
41 r.UR.y = p.y;
42 }
43 return r;
44}
45
46boxf mkboxf(pointf p, pointf q)
47{
48 boxf r;
49
50 if (p.x < q.x) {
51 r.LL.x = p.x;
52 r.UR.x = q.x;
53 } else {
54 r.LL.x = q.x;
55 r.UR.x = p.x;
56 }
57 if (p.y < q.y) {
58 r.LL.y = p.y;
59 r.UR.y = q.y;
60 } else {
61 r.LL.y = q.y;
62 r.UR.y = p.y;
63 }
64 return r;
65}
66
67/*
68 *--------------------------------------------------------------
69 *
70 * lineToBox --
71 *
72 * Determine whether a line lies entirely inside, entirely
73 * outside, or overlapping a given rectangular area.
74 *
75 * Results:
76 * -1 is returned if the line given by p and q
77 * is entirely outside the rectangle given by b.
78 * 0 is returned if the polygon overlaps the rectangle, and
79 * 1 is returned if the polygon is entirely inside the rectangle.
80 *
81 * Side effects:
82 * None.
83 *
84 *--------------------------------------------------------------
85 */
86
87/* This code steals liberally from algorithms in tk/generic/tkTrig.c -- jce */
88
89int lineToBox(pointf p, pointf q, boxf b)
90{
91 int inside1, inside2;
92
93 /*
94 * First check the two points individually to see whether they
95 * are inside the rectangle or not.
96 */
97
98 inside1 = (p.x >= b.LL.x) && (p.x <= b.UR.x)
99 && (p.y >= b.LL.y) && (p.y <= b.UR.y);
100 inside2 = (q.x >= b.LL.x) && (q.x <= b.UR.x)
101 && (q.y >= b.LL.y) && (q.y <= b.UR.y);
102 if (inside1 != inside2) {
103 return 0;
104 }
105 if (inside1 & inside2) {
106 return 1;
107 }
108
109 /*
110 * Both points are outside the rectangle, but still need to check
111 * for intersections between the line and the rectangle. Horizontal
112 * and vertical lines are particularly easy, so handle them
113 * separately.
114 */
115
116 if (p.x == q.x) {
117 /*
118 * Vertical line.
119 */
120
121 if (((p.y >= b.LL.y) ^ (q.y >= b.LL.y))
122 && (p.x >= b.LL.x)
123 && (p.x <= b.UR.x)) {
124 return 0;
125 }
126 } else if (p.y == q.y) {
127 /*
128 * Horizontal line.
129 */
130 if (((p.x >= b.LL.x) ^ (q.x >= b.LL.x))
131 && (p.y >= b.LL.y)
132 && (p.y <= b.UR.y)) {
133 return 0;
134 }
135 } else {
136 double m, x, y, low, high;
137
138 /*
139 * Diagonal line. Compute slope of line and use
140 * for intersection checks against each of the
141 * sides of the rectangle: left, right, bottom, top.
142 */
143
144 m = (q.y - p.y)/(q.x - p.x);
145 if (p.x < q.x) {
146 low = p.x; high = q.x;
147 } else {
148 low = q.x; high = p.x;
149 }
150
151 /*
152 * Left edge.
153 */
154
155 y = p.y + (b.LL.x - p.x)*m;
156 if ((b.LL.x >= low) && (b.LL.x <= high)
157 && (y >= b.LL.y) && (y <= b.UR.y)) {
158 return 0;
159 }
160
161 /*
162 * Right edge.
163 */
164
165 y += (b.UR.x - b.LL.x)*m;
166 if ((y >= b.LL.y) && (y <= b.UR.y)
167 && (b.UR.x >= low) && (b.UR.x <= high)) {
168 return 0;
169 }
170
171 /*
172 * Bottom edge.
173 */
174
175 if (p.y < q.y) {
176 low = p.y; high = q.y;
177 } else {
178 low = q.y; high = p.y;
179 }
180 x = p.x + (b.LL.y - p.y)/m;
181 if ((x >= b.LL.x) && (x <= b.UR.x)
182 && (b.LL.y >= low) && (b.LL.y <= high)) {
183 return 0;
184 }
185
186 /*
187 * Top edge.
188 */
189
190 x += (b.UR.y - b.LL.y)/m;
191 if ((x >= b.LL.x) && (x <= b.UR.x)
192 && (b.UR.y >= low) && (b.UR.y <= high)) {
193 return 0;
194 }
195 }
196 return -1;
197}
198#ifdef WIN32_STATIC
199#define inline
200#endif
201void rect2poly(pointf *p)
202{
203 p[3].x = p[2].x = p[1].x;
204 p[2].y = p[1].y;
205 p[3].y = p[0].y;
206 p[1].x = p[0].x;
207}
208
209static pointf rotatepf(pointf p, int cwrot)
210{
211 static double sina, cosa;
212 static int last_cwrot;
213 pointf P;
214
215 /* cosa is initially wrong for a cwrot of 0
216 * this caching only works because we are never called for 0 rotations */
217 if (cwrot != last_cwrot) {
218 sincos(cwrot / (2 * M_PI), &sina, &cosa);
219 last_cwrot = cwrot;
220 }
221 P.x = p.x * cosa - p.y * sina;
222 P.y = p.y * cosa + p.x * sina;
223 return P;
224}
225
226static point rotatep(point p, int cwrot)
227{
228 pointf pf;
229
230 P2PF(p, pf);
231 pf = rotatepf(pf, cwrot);
232 PF2P(pf, p);
233 return p;
234}
235
236point cwrotatep(point p, int cwrot)
237{
238 int x = p.x, y = p.y;
239 switch (cwrot) {
240 case 0:
241 break;
242 case 90:
243 p.x = y;
244 p.y = -x;
245 break;
246 case 180:
247 p.x = x;
248 p.y = -y;
249 break;
250 case 270:
251 p.x = y;
252 p.y = x;
253 break;
254 default:
255 if (cwrot < 0)
256 return ccwrotatep(p, -cwrot);
257 if (cwrot > 360)
258 return cwrotatep(p, cwrot%360);
259 return rotatep(p, cwrot);
260 }
261 return p;
262}
263
264pointf cwrotatepf(pointf p, int cwrot)
265{
266 double x = p.x, y = p.y;
267 switch (cwrot) {
268 case 0:
269 break;
270 case 90:
271 p.x = y;
272 p.y = -x;
273 break;
274 case 180:
275 p.x = x;
276 p.y = -y;
277 break;
278 case 270:
279 p.x = y;
280 p.y = x;
281 break;
282 default:
283 if (cwrot < 0)
284 return ccwrotatepf(p, -cwrot);
285 if (cwrot > 360)
286 return cwrotatepf(p, cwrot%360);
287 return rotatepf(p, cwrot);
288 }
289 return p;
290}
291
292point ccwrotatep(point p, int ccwrot)
293{
294 int x = p.x, y = p.y;
295 switch (ccwrot) {
296 case 0:
297 break;
298 case 90:
299 p.x = -y;
300 p.y = x;
301 break;
302 case 180:
303 p.x = x;
304 p.y = -y;
305 break;
306 case 270:
307 p.x = y;
308 p.y = x;
309 break;
310 default:
311 if (ccwrot < 0)
312 return cwrotatep(p, -ccwrot);
313 if (ccwrot > 360)
314 return ccwrotatep(p, ccwrot%360);
315 return rotatep(p, 360-ccwrot);
316 }
317 return p;
318}
319
320pointf ccwrotatepf(pointf p, int ccwrot)
321{
322 double x = p.x, y = p.y;
323 switch (ccwrot) {
324 case 0:
325 break;
326 case 90:
327 p.x = -y;
328 p.y = x;
329 break;
330 case 180:
331 p.x = x;
332 p.y = -y;
333 break;
334 case 270:
335 p.x = y;
336 p.y = x;
337 break;
338 default:
339 if (ccwrot < 0)
340 return cwrotatepf(p, -ccwrot);
341 if (ccwrot > 360)
342 return ccwrotatepf(p, ccwrot%360);
343 return rotatepf(p, 360-ccwrot);
344 }
345 return p;
346}
347
348inline box flip_rec_box(box b, point p)
349{
350 box r;
351 /* flip box */
352 r.UR.x = b.UR.y;
353 r.UR.y = b.UR.x;
354 r.LL.x = b.LL.y;
355 r.LL.y = b.LL.x;
356 /* move box */
357 r.LL.x += p.x;
358 r.LL.y += p.y;
359 r.UR.x += p.x;
360 r.UR.y += p.y;
361 return r;
362}
363
364boxf flip_rec_boxf(boxf b, pointf p)
365{
366 boxf r;
367 /* flip box */
368 r.UR.x = b.UR.y;
369 r.UR.y = b.UR.x;
370 r.LL.x = b.LL.y;
371 r.LL.y = b.LL.x;
372 /* move box */
373 r.LL.x += p.x;
374 r.LL.y += p.y;
375 r.UR.x += p.x;
376 r.UR.y += p.y;
377 return r;
378}
379
380#ifdef WIN32_STATIC
381#undef inline
382#endif
383
384
385#define SMALL 0.0000000001
386
387/* ptToLine2:
388 * Return distance from point p to line a-b squared.
389 */
390double ptToLine2 (pointf a, pointf b, pointf p)
391{
392 double dx = b.x-a.x;
393 double dy = b.y-a.y;
394 double a2 = (p.y-a.y)*dx - (p.x-a.x)*dy;
395 a2 *= a2; /* square - ensures that it is positive */
396 if (a2 < SMALL) return 0.; /* avoid 0/0 problems */
397 return a2 / (dx*dx + dy*dy);
398}
399
400#define dot(v,w) (v.x*w.x+v.y*w.y)
401
402/* line_intersect:
403 * Computes intersection of lines a-b and c-d, returning intersection
404 * point in *p.
405 * Returns 0 if no intersection (lines parallel), 1 otherwise.
406 */
407int line_intersect (pointf a, pointf b, pointf c, pointf d, pointf* p)
408{
409
410 pointf mv = sub_pointf(b,a);
411 pointf lv = sub_pointf(d,c);
412 pointf ln = perp (lv);
413 double lc = -dot(ln,c);
414 double dt = dot(ln,mv);
415
416 if (fabs(dt) < SMALL) return 0;
417
418 *p = sub_pointf(a,scale((dot(ln,a)+lc)/dt,mv));
419 return 1;
420}
421
422