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