geometry.h
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 */
34 
35 
36 #ifndef _GEOMETRY_H
37 #define _GEOMETRY_H
38 
39 #include "libavoid/geomtypes.h"
40 #include "libavoid/assertions.h"
41 
42 namespace Avoid {
43 
44 
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);
61 
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);
64 
65 
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);
82 
83  double area2 = ((b.x - a.x) * (c.y - a.y)) -
84  ((c.x - a.x) * (b.y - a.y));
85 
86  if (area2 < (-maybeZero))
87  {
88  return -1;
89  }
90  else if (area2 > maybeZero)
91  {
92  return 1;
93  }
94  return 0;
95 }
96 
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 }
111 
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);
122 extern double rotationalAngle(const Point& p);
123 
124 
125 }
126 
127 
128 #endif