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