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  * 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 */
  32
  33
  34 #ifndef _GEOMETRY_H
  35 #define _GEOMETRY_H
  36
  37 #include "libavoid/geomtypes.h"
  38
  39 namespace Avoid {
  40
  41
  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);
  53
  54
  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));
  68
  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 }
  79
  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 }
  94
  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);
 103
 104
 105 }
 106
 107
 108 #endif