1 /*
2 * vim: ts=4 sw=4 et tw=0 wm=0
3 *
4 * libavoid - Fast, Incremental, Object-avoiding Line Router
5 *
6 * Copyright (C) 2004-2009 Monash University
7 *
8 * --------------------------------------------------------------------
9 * Much of the code in this module is based on code published with
10 * and/or described in "Computational Geometry in C" (Second Edition),
11 * Copyright (C) 1998 Joseph O'Rourke <orourke@cs.smith.edu>
12 * --------------------------------------------------------------------
13 * The segmentIntersectPoint function is based on code published and
14 * described in Franklin Antonio, Faster Line Segment Intersection,
15 * Graphics Gems III, p. 199-202, code: p. 500-501.
16 * --------------------------------------------------------------------
17 *
18 * This library is free software; you can redistribute it and/or
19 * modify it under the terms of the GNU Lesser General Public
20 * License as published by the Free Software Foundation; either
21 * version 2.1 of the License, or (at your option) any later version.
22 * See the file LICENSE.LGPL distributed with the library.
23 *
24 * Licensees holding a valid commercial license may use this file in
25 * accordance with the commercial license agreement provided with the
26 * library.
27 *
28 * This library is distributed in the hope that it will be useful,
29 * but WITHOUT ANY WARRANTY; without even the implied warranty of
30 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
31 *
32 * Author(s): Michael Wybrow <mjwybrow@users.sourceforge.net>
33 */
36 #ifndef _GEOMETRY_H
37 #define _GEOMETRY_H
39 #include "libavoid/geomtypes.h"
40 #include "libavoid/assertions.h"
42 namespace Avoid {
45 extern double euclideanDist(const Point& a, const Point& b);
46 extern double manhattanDist(const Point& a, const Point& b);
47 extern double totalLength(const Polygon& poly);
48 extern double angle(const Point& a, const Point& b, const Point& c);
49 extern bool segmentIntersect(const Point& a, const Point& b,
50 const Point& c, const Point& d);
51 extern bool segmentShapeIntersect(const Point& e1, const Point& e2,
52 const Point& s1, const Point& s2, bool& seenIntersectionAtEndpoint);
53 extern bool inPoly(const Polygon& poly, const Point& q, bool countBorder = true);
54 extern bool inPolyGen(const PolygonInterface& poly, const Point& q);
55 extern bool inValidRegion(bool IgnoreRegions, const Point& a0,
56 const Point& a1, const Point& a2, const Point& b);
57 extern int cornerSide(const Point &c1, const Point &c2, const Point &c3,
58 const Point& p);
59 extern bool pointOnLine(const Point& a, const Point& b, const Point& c,
60 const double tolerance = 0.0);
62 // To be used only when the points are known to be colinear.
63 extern bool inBetween(const Point& a, const Point& b, const Point& c);
66 // Direction from vector.
67 // Looks at the position of point c from the directed segment ab and
68 // returns the following:
69 // 1 counterclockwise
70 // 0 collinear
71 // -1 clockwise
72 //
73 // Based on the code of 'AreaSign'.
74 //
75 // The 'maybeZero' argument can be used to adjust the tolerance of the
76 // function. It will be most accurate when 'maybeZero' == 0.0, the default.
77 //
78 static inline int vecDir(const Point& a, const Point& b, const Point& c,
79 const double maybeZero = 0.0)
80 {
81 COLA_ASSERT(maybeZero >= 0);
83 double area2 = ((b.x - a.x) * (c.y - a.y)) -
84 ((c.x - a.x) * (b.y - a.y));
86 if (area2 < (-maybeZero))
87 {
88 return -1;
89 }
90 else if (area2 > maybeZero)
91 {
92 return 1;
93 }
94 return 0;
95 }
97 // Finds the projection point of (a,b) onto (a,c)
98 static inline Point projection(const Point& a, const Point& b, const Point& c)
99 {
100 double ux = c.x - a.x,
101 uy = c.y - a.y,
102 vx = b.x - a.x,
103 vy = b.y - a.y,
104 scalarProj = ux * vx + uy * vy;
105 scalarProj /= ux * ux + uy * uy;
106 Point p;
107 p.x = scalarProj * ux + a.x;
108 p.y = scalarProj * uy + a.y;
109 return p;
110 }
112 // Line Segment Intersection
113 // Original code by Franklin Antonio
114 //
115 static const int DONT_INTERSECT = 0;
116 static const int DO_INTERSECT = 1;
117 static const int PARALLEL = 3;
118 extern int segmentIntersectPoint(const Point& a1, const Point& a2,
119 const Point& b1, const Point& b2, double *x, double *y);
120 extern int rayIntersectPoint(const Point& a1, const Point& a2,
121 const Point& b1, const Point& b2, double *x, double *y);
124 }
127 #endif