src/libavoid/geometry.cpp

   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  *
  13  * This library is free software; you can redistribute it and/or
  14  * modify it under the terms of the GNU Lesser General Public
  15  * License as published by the Free Software Foundation; either
  16  * version 2.1 of the License, or (at your option) any later version.
  17  *
  18  * This library is distributed in the hope that it will be useful,
  19  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  20  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  21  * Lesser General Public License for more details.
  22  *
  23  * You should have received a copy of the GNU Lesser General Public
  24  * License along with this library; if not, write to the Free Software
  25  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  26  *
  27 */
  28
  29 #include "libavoid/graph.h"
  30 #include "libavoid/geometry.h"
  31 #include "libavoid/polyutil.h"
  32
  33 #include <math.h>
  34
  35 namespace Avoid {
  36
  37
  38 // Returns true iff the point c lies on the closed segment ab.
  39 //
  40 // Based on the code of 'Between'.
  41 //
  42 static const bool inBetween(const Point& a, const Point& b, const Point& c)
  43 {
  44     // We only call this when we know the points are collinear,
  45     // otherwise we should be checking this here.
  46     assert(vecDir(a, b, c) == 0);
  47
  48     if (a.x != b.x)
  49     {
  50         // not vertical
  51         return (((a.x < c.x) && (c.x < b.x)) ||
  52                 ((b.x < c.x) && (c.x < a.x)));
  53     }
  54     else
  55     {
  56         return (((a.y < c.y) && (c.y < b.y)) ||
  57                 ((b.y < c.y) && (c.y < a.y)));
  58     }
  59 }
  60
  61
  62 // Returns true if the segment cd intersects the segment ab, blocking
  63 // visibility.
  64 //
  65 // Based on the code of 'IntersectProp' and 'Intersect'.
  66 //
  67 bool segmentIntersect(const Point& a, const Point& b, const Point& c,
  68         const Point& d)
  69 {
  70     int ab_c = vecDir(a, b, c);
  71     if ((ab_c == 0) && inBetween(a, b, c))
  72     {
  73         return true;
  74     }
  75
  76     int ab_d = vecDir(a, b, d);
  77     if ((ab_d == 0) && inBetween(a, b, d))
  78     {
  79         return true;
  80     }
  81
  82     // It's ok for either of the points a or b to be on the line cd,
  83     // so we don't have to check the other two cases.
  84
  85     int cd_a = vecDir(c, d, a);
  86     int cd_b = vecDir(c, d, b);
  87
  88     // Is an intersection if a and b are on opposite sides of cd,
  89     // and c and d are on opposite sides of the line ab.
  90     //
  91     // Note: this is safe even though the textbook warns about it
  92     // since, unlike them, out vecDir is equivilent to 'AreaSign'
  93     // rather than 'Area2'.
  94     return (((ab_c * ab_d) < 0) && ((cd_a * cd_b) < 0));
  95 }
  96
  97
  98 // Returns true iff the point p in a valid region that can contain
  99 // shortest paths.  a0, a1, a2 are ordered vertices of a shape.
 100 // This function may seem 'backwards' to the user due to some of
 101 // the code being reversed due to screen cooridinated being the
 102 // opposite of graph paper coords.
 103 // TODO: Rewrite this after checking whether it works for Inkscape.
 104 //
 105 // Based on the code of 'InCone'.
 106 //
 107 bool inValidRegion(bool IgnoreRegions, const Point& a0, const Point& a1,
 108         const Point& a2, const Point& b)
 109 {
 110     int rSide = vecDir(b, a0, a1);
 111     int sSide = vecDir(b, a1, a2);
 112
 113     bool rOutOn = (rSide >= 0);
 114     bool sOutOn = (sSide >= 0);
 115
 116     bool rOut = (rSide > 0);
 117     bool sOut = (sSide > 0);
 118
 119     if (vecDir(a0, a1, a2) > 0)
 120     {
 121         // Concave at a1:
 122         //
 123         //   !rO      rO
 124         //   !sO     !sO
 125         //
 126         //        +---s---
 127         //        |
 128         //   !rO  r   rO
 129         //    sO  |   sO
 130         //
 131         //
 132         return (IgnoreRegions ? false : (rOutOn && sOutOn));
 133     }
 134     else
 135     {
 136         // Convex at a1:
 137         //
 138         //   !rO      rO
 139         //    sO      sO
 140         //
 141         // ---s---+
 142         //        |
 143         //   !rO  r   rO
 144         //   !sO  |  !sO
 145         //
 146         //
 147         if (IgnoreRegions)
 148         {
 149             return (rOutOn && !sOut) || (!rOut && sOutOn);
 150         }
 151         return (rOutOn || sOutOn);
 152     }
 153 }
 154
 155
 156 // Returns the distance between points a and b.
 157 //
 158 double dist(const Point& a, const Point& b)
 159 {
 160     double xdiff = a.x - b.x;
 161     double ydiff = a.y - b.y;
 162
 163     return sqrt((xdiff * xdiff) + (ydiff * ydiff));
 164 }
 165
 166
 167 // Returns true iff the point q is inside (or on the edge of) the
 168 // polygon argpoly.
 169 //
 170 // Based on the code of 'InPoly'.
 171 //
 172 bool inPoly(const Polygn& argpoly, const Point& q)
 173 {
 174     // Numbers of right and left edge/ray crossings.
 175     int Rcross = 0;
 176     int Lcross = 0;
 177
 178     // Copy the argument polygon
 179     Polygn poly = copyPoly(argpoly);
 180     Point *P = poly.ps;
 181     int    n = poly.pn;
 182
 183     // Shift so that q is the origin. This is done for pedogical clarity.
 184     for (int i = 0; i < n; ++i)
 185     {
 186         P[i].x = P[i].x - q.x;
 187         P[i].y = P[i].y - q.y;
 188     }
 189
 190     // For each edge e=(i-1,i), see if crosses ray.
 191     for (int i = 0; i < n; ++i)
 192     {
 193         // First see if q=(0,0) is a vertex.
 194         if ((P[i].x == 0) && (P[i].y == 0))
 195         {
 196             // We count a vertex as inside.
 197             freePoly(poly);
 198             return true;
 199         }
 200
 201         // point index; i1 = i-1 mod n
 202         int i1 = ( i + n - 1 ) % n;
 203
 204         // if e "straddles" the x-axis...
 205         // The commented-out statement is logically equivalent to the one
 206         // following.
 207         // if( ((P[i].y > 0) && (P[i1].y <= 0)) ||
 208         //         ((P[i1].y > 0) && (P[i].y <= 0)) )
 209
 210         if ((P[i].y > 0) != (P[i1].y > 0))
 211         {
 212             // e straddles ray, so compute intersection with ray.
 213             double x = (P[i].x * P[i1].y - P[i1].x * P[i].y)
 214                     / (P[i1].y - P[i].y);
 215
 216             // crosses ray if strictly positive intersection.
 217             if (x > 0)
 218             {
 219                 Rcross++;
 220             }
 221         }
 222
 223         // if e straddles the x-axis when reversed...
 224         // if( ((P[i].y < 0) && (P[i1].y >= 0)) ||
 225         //         ((P[i1].y < 0) && (P[i].y >= 0)) )
 226
 227         if ((P[i].y < 0) != (P[i1].y < 0))
 228         {
 229             // e straddles ray, so compute intersection with ray.
 230             double x = (P[i].x * P[i1].y - P[i1].x * P[i].y)
 231                     / (P[i1].y - P[i].y);
 232
 233             // crosses ray if strictly positive intersection.
 234             if (x < 0)
 235             {
 236                 Lcross++;
 237             }
 238         }
 239     }
 240     freePoly(poly);
 241
 242     // q on the edge if left and right cross are not the same parity.
 243     if ( (Rcross % 2) != (Lcross % 2) )
 244     {
 245         // We count the edge as inside.
 246         return true;
 247     }
 248
 249     // Inside iff an odd number of crossings.
 250     if ((Rcross % 2) == 1)
 251     {
 252         return true;
 253     }
 254
 255     // Outside.
 256     return false;
 257 }
 258
 259
 260 }
 261