1 /*
2 * vim: ts=4 sw=4 et tw=0 wm=0
3 *
4 * libavoid - Fast, Incremental, Object-avoiding Line Router
5 * Copyright (C) 2004-2006 Michael Wybrow <mjwybrow@users.sourceforge.net>
6 *
7 * --------------------------------------------------------------------
8 * Much of the code in this module is based on code published with
9 * and/or described in "Computational Geometry in C" (Second Edition),
10 * Copyright (C) 1998 Joseph O'Rourke <orourke@cs.smith.edu>
11 * --------------------------------------------------------------------
12 * The segmentIntersectPoint function is based on code published and
13 * described in Franklin Antonio, Faster Line Segment Intersection,
14 * Graphics Gems III, p. 199-202, code: p. 500-501.
15 * --------------------------------------------------------------------
16 *
17 * This library is free software; you can redistribute it and/or
18 * modify it under the terms of the GNU Lesser General Public
19 * License as published by the Free Software Foundation; either
20 * version 2.1 of the License, or (at your option) any later version.
21 *
22 * This library is distributed in the hope that it will be useful,
23 * but WITHOUT ANY WARRANTY; without even the implied warranty of
24 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
25 * Lesser General Public License for more details.
26 *
27 * You should have received a copy of the GNU Lesser General Public
28 * License along with this library; if not, write to the Free Software
29 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
30 *
31 */
34 #ifndef _GEOMETRY_H
35 #define _GEOMETRY_H
37 #include "libavoid/geomtypes.h"
39 namespace Avoid {
42 extern double dist(const Point& a, const Point& b);
43 extern double totalLength(const Polygn& poly);
44 extern double angle(const Point& a, const Point& b, const Point& c);
45 extern bool segmentIntersect(const Point& a, const Point& b,
46 const Point& c, const Point& d);
47 extern bool inPoly(const Polygn& poly, const Point& q);
48 extern bool inPolyGen(const Polygn& poly, const Point& q);
49 extern bool inValidRegion(bool IgnoreRegions, const Point& a0,
50 const Point& a1, const Point& a2, const Point& b);
51 extern int cornerSide(const Point &c1, const Point &c2, const Point &c3,
52 const Point& p);
55 // Direction from vector.
56 // Looks at the position of point c from the directed segment ab and
57 // returns the following:
58 // 1 counterclockwise
59 // 0 collinear
60 // -1 clockwise
61 //
62 // Based on the code of 'AreaSign'.
63 //
64 static inline int vecDir(const Point& a, const Point& b, const Point& c)
65 {
66 double area2 = ((b.x - a.x) * (c.y - a.y)) -
67 ((c.x - a.x) * (b.y - a.y));
69 if (area2 < -0.001)
70 {
71 return -1;
72 }
73 else if (area2 > 0.001)
74 {
75 return 1;
76 }
77 return 0;
78 }
80 // Finds the projection point of (a,b) onto (a,c)
81 static inline Point projection(const Point& a, const Point& b, const Point& c)
82 {
83 double ux = c.x - a.x,
84 uy = c.y - a.y,
85 vx = b.x - a.x,
86 vy = b.y - a.y,
87 scalarProj = ux * vx + uy * vy;
88 scalarProj /= ux * ux + uy * uy;
89 Point p;
90 p.x = scalarProj * ux + a.x;
91 p.y = scalarProj * uy + a.y;
92 return p;
93 }
95 // Line Segment Intersection
96 // Original code by Franklin Antonio
97 //
98 static const int DONT_INTERSECT = 0;
99 static const int DO_INTERSECT = 1;
100 static const int PARALLEL = 3;
101 extern int segmentIntersectPoint(const Point& a1, const Point& a2,
102 const Point& b1, const Point& b2, double *x, double *y);
105 }
108 #endif