diff options
Diffstat (limited to 'src/libavoid/geometry.cpp')
| -rw-r--r-- | src/libavoid/geometry.cpp | 260 |
1 files changed, 260 insertions, 0 deletions
diff --git a/src/libavoid/geometry.cpp b/src/libavoid/geometry.cpp new file mode 100644 index 000000000..d720693ac --- /dev/null +++ b/src/libavoid/geometry.cpp @@ -0,0 +1,260 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libavoid - Fast, Incremental, Object-avoiding Line Router + * Copyright (C) 2004-2005 Michael Wybrow <mjwybrow@users.sourceforge.net> + * + * -------------------------------------------------------------------- + * Much of the code in this module is based on code published with + * and/or described in "Computational Geometry in C" (Second Edition), + * Copyright (C) 1998 Joseph O'Rourke <orourke@cs.smith.edu> + * -------------------------------------------------------------------- + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * +*/ + +#include "libavoid/graph.h" +#include "libavoid/polyutil.h" + +#include <math.h> + +namespace Avoid { + + +// Returns true iff the point c lies on the closed segment ab. +// +// Based on the code of 'Between'. +// +static const bool inBetween(const Point& a, const Point& b, const Point& c) +{ + // We only call this when we know the points are collinear, + // otherwise we should be checking this here. + assert(vecDir(a, b, c) == 0); + + if (a.x != b.x) + { + // not vertical + return (((a.x < c.x) && (c.x < b.x)) || + ((b.x < c.x) && (c.x < a.x))); + } + else + { + return (((a.y < c.y) && (c.y < b.y)) || + ((b.y < c.y) && (c.y < a.y))); + } +} + + +// Returns true if the segment cd intersects the segment ab, blocking +// visibility. +// +// Based on the code of 'IntersectProp' and 'Intersect'. +// +bool segmentIntersect(const Point& a, const Point& b, const Point& c, + const Point& d) +{ + int ab_c = vecDir(a, b, c); + if ((ab_c == 0) && inBetween(a, b, c)) + { + return true; + } + + int ab_d = vecDir(a, b, d); + if ((ab_d == 0) && inBetween(a, b, d)) + { + return true; + } + + // It's ok for either of the points a or b to be on the line cd, + // so we don't have to check the other two cases. + + int cd_a = vecDir(c, d, a); + int cd_b = vecDir(c, d, b); + + // Is an intersection if a and b are on opposite sides of cd, + // and c and d are on opposite sides of the line ab. + // + // Note: this is safe even though the textbook warns about it + // since, unlike them, out vecDir is equivilent to 'AreaSign' + // rather than 'Area2'. + return (((ab_c * ab_d) < 0) && ((cd_a * cd_b) < 0)); +} + + +// Returns true iff the point p in a valid region that can contain +// shortest paths. a0, a1, a2 are ordered vertices of a shape. +// This function may seem 'backwards' to the user due to some of +// the code being reversed due to screen cooridinated being the +// opposite of graph paper coords. +// TODO: Rewrite this after checking whether it works for Inkscape. +// +// Based on the code of 'InCone'. +// +bool inValidRegion(const Point& a0, const Point& a1, const Point& a2, + const Point& b) +{ + int rSide = vecDir(b, a0, a1); + int sSide = vecDir(b, a1, a2); + + bool rOutOn = (rSide >= 0); + bool sOutOn = (sSide >= 0); + + bool rOut = (rSide > 0); + bool sOut = (sSide > 0); + + if (vecDir(a0, a1, a2) > 0) + { + // Concave at a1: + // + // !rO rO + // !sO !sO + // + // +---s--- + // | + // !rO r rO + // sO | sO + // + // + return (IgnoreRegions ? false : (rOutOn && sOutOn)); + } + else + { + // Convex at a1: + // + // !rO rO + // sO sO + // + // ---s---+ + // | + // !rO r rO + // !sO | !sO + // + // + if (IgnoreRegions) + { + return (rOutOn && !sOut) || (!rOut && sOutOn); + } + return (rOutOn || sOutOn); + } +} + + +// Returns the distance between points a and b. +// +double dist(const Point& a, const Point& b) +{ + double xdiff = a.x - b.x; + double ydiff = a.y - b.y; + + return sqrt((xdiff * xdiff) + (ydiff * ydiff)); +} + + +// Returns true iff the point q is inside (or on the edge of) the +// polygon argpoly. +// +// Based on the code of 'InPoly'. +// +bool inPoly(const Polygn& argpoly, const Point& q) +{ + // Numbers of right and left edge/ray crossings. + int Rcross = 0; + int Lcross = 0; + + // Copy the argument polygon + Polygn poly = copyPoly(argpoly); + Point *P = poly.ps; + int n = poly.pn; + + // Shift so that q is the origin. This is done for pedogical clarity. + for (int i = 0; i < n; ++i) + { + P[i].x = P[i].x - q.x; + P[i].y = P[i].y - q.y; + } + + // For each edge e=(i-1,i), see if crosses ray. + for (int i = 0; i < n; ++i) + { + // First see if q=(0,0) is a vertex. + if ((P[i].x == 0) && (P[i].y == 0)) + { + // We count a vertex as inside. + freePoly(poly); + return true; + } + + // point index; i1 = i-1 mod n + int i1 = ( i + n - 1 ) % n; + + // if e "straddles" the x-axis... + // The commented-out statement is logically equivalent to the one + // following. + // if( ((P[i].y > 0) && (P[i1].y <= 0)) || + // ((P[i1].y > 0) && (P[i].y <= 0)) ) + + if ((P[i].y > 0) != (P[i1].y > 0)) + { + // e straddles ray, so compute intersection with ray. + double x = (P[i].x * P[i1].y - P[i1].x * P[i].y) + / (P[i1].y - P[i].y); + + // crosses ray if strictly positive intersection. + if (x > 0) + { + Rcross++; + } + } + + // if e straddles the x-axis when reversed... + // if( ((P[i].y < 0) && (P[i1].y >= 0)) || + // ((P[i1].y < 0) && (P[i].y >= 0)) ) + + if ((P[i].y < 0) != (P[i1].y < 0)) + { + // e straddles ray, so compute intersection with ray. + double x = (P[i].x * P[i1].y - P[i1].x * P[i].y) + / (P[i1].y - P[i].y); + + // crosses ray if strictly positive intersection. + if (x < 0) + { + Lcross++; + } + } + } + freePoly(poly); + + // q on the edge if left and right cross are not the same parity. + if ( (Rcross % 2) != (Lcross % 2) ) + { + // We count the edge as inside. + return true; + } + + // Inside iff an odd number of crossings. + if ((Rcross % 2) == 1) + { + return true; + } + + // Outside. + return false; +} + + +} + |