src/libavoid/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
 123
 124 }
 125
 126
 127 #endif