Graphviz  2.41.20170921.2350
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 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 
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 
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 
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
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 
209 static 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 
226 static 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 
236 point 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 
264 pointf 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 
292 point 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 
320 pointf 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 
348 inline 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 
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  */
390 double 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  */
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 
box flip_rec_box(box b, point p)
Definition: geom.c:348
pointf cwrotatepf(pointf p, int cwrot)
Definition: geom.c:264
boxf flip_rec_boxf(boxf b, pointf p)
Definition: geom.c:364
Definition: geom.h:28
#define PF2P(pf, p)
Definition: geom.h:72
#define P2PF(p, pf)
Definition: geom.h:71
point UR
Definition: geom.h:33
int x
Definition: geom.h:26
int lineToBox(pointf p, pointf q, boxf b)
Definition: geom.c:89
pointf ccwrotatepf(pointf p, int ccwrot)
Definition: geom.c:320
#define dot(v, w)
Definition: geom.c:400
double y
Definition: geom.h:28
point cwrotatep(point p, int cwrot)
Definition: geom.c:236
void rect2poly(pointf *p)
Definition: geom.c:201
point LL
Definition: geom.h:33
boxf mkboxf(pointf p, pointf q)
Definition: geom.c:46
#define SMALL
Definition: geom.c:385
Definition: geom.h:26
double x
Definition: geom.h:28
int line_intersect(pointf a, pointf b, pointf c, pointf d, pointf *p)
Definition: geom.c:407
pointf LL
Definition: geom.h:35
#define sincos(x, s, c)
Definition: arith.h:93
point ccwrotatep(point p, int ccwrot)
Definition: geom.c:292
void(* pf)(char *, void *)
Definition: xdot.c:501
#define M_PI
Definition: arith.h:77
box mkbox(point p, point q)
Definition: geom.c:25
int y
Definition: geom.h:26
pointf UR
Definition: geom.h:35
Definition: geom.h:35
double ptToLine2(pointf a, pointf b, pointf p)
Definition: geom.c:390
Definition: geom.h:33