diff options
Diffstat (limited to 'src/libavoid/geometry.cpp')
| -rw-r--r-- | src/libavoid/geometry.cpp | 241 |
1 files changed, 151 insertions, 90 deletions
diff --git a/src/libavoid/geometry.cpp b/src/libavoid/geometry.cpp index 15840c381..2523375cf 100644 --- a/src/libavoid/geometry.cpp +++ b/src/libavoid/geometry.cpp @@ -2,7 +2,8 @@ * vim: ts=4 sw=4 et tw=0 wm=0 * * libavoid - Fast, Incremental, Object-avoiding Line Router - * Copyright (C) 2004-2006 Michael Wybrow <mjwybrow@users.sourceforge.net> + * + * Copyright (C) 2004-2009 Monash University * * -------------------------------------------------------------------- * Much of the code in this module is based on code published with @@ -18,70 +19,42 @@ * 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. + * See the file LICENSE.LGPL distributed with the library. + * + * Licensees holding a valid commercial license may use this file in + * accordance with the commercial license agreement provided with the + * library. * * 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 + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. * + * Author(s): Michael Wybrow <mjwybrow@users.sourceforge.net> */ + +#include <cmath> + #include "libavoid/graph.h" #include "libavoid/geometry.h" -#include "libavoid/polyutil.h" - -#include <math.h> +#include "libavoid/assertions.h" namespace Avoid { -Point::Point() -{ -} - - -Point::Point(const double xv, const double yv) - : x(xv) - , y(yv) -{ -} - - -bool Point::operator==(const Point& rhs) const -{ - if ((x == rhs.x) && (y == rhs.y)) - { - return true; - } - return false; -} - - -bool Point::operator!=(const Point& rhs) const -{ - if ((x != rhs.x) || (y != rhs.y)) - { - return true; - } - return false; -} - // Returns true iff the point c lies on the closed segment ab. +// To be used when the points are known to be collinear. // // Based on the code of 'Between'. // -static const bool inBetween(const Point& a, const Point& b, const Point& c) +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); + COLA_ASSERT(vecDir(a, b, c, 0.0001) == 0); - if (a.x != b.x) + if ((fabs(a.x - b.x) > 1) && (a.x != b.x)) { // not vertical return (((a.x < c.x) && (c.x < b.x)) || @@ -95,6 +68,15 @@ static const bool inBetween(const Point& a, const Point& b, const Point& c) } +// Returns true iff the point c lies on the closed segment ab. +// +bool pointOnLine(const Point& a, const Point& b, const Point& c, + const double tolerance) +{ + return (vecDir(a, b, c, tolerance) == 0) && inBetween(a, b, c); +} + + // Returns true if the segment cd intersects the segment ab, blocking // visibility. // @@ -104,15 +86,15 @@ 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)) + if (ab_c == 0) { - return true; + return false; } int ab_d = vecDir(a, b, d); - if ((ab_d == 0) && inBetween(a, b, d)) + if (ab_d == 0) { - return true; + return false; } // It's ok for either of the points a or b to be on the line cd, @@ -131,6 +113,37 @@ bool segmentIntersect(const Point& a, const Point& b, const Point& c, } +// Returns true if the segment e1-e2 intersects the shape boundary +// segment s1-s2, blocking visibility. +// +bool segmentShapeIntersect(const Point& e1, const Point& e2, const Point& s1, + const Point& s2, bool& seenIntersectionAtEndpoint) +{ + if (segmentIntersect(e1, e2, s1, s2)) + { + // Basic intersection of segments. + return true; + } + else if ( (((s2 == e1) || pointOnLine(s1, s2, e1)) && + (vecDir(s1, s2, e2) != 0)) + || + (((s2 == e2) || pointOnLine(s1, s2, e2)) && + (vecDir(s1, s2, e1) != 0)) ) + { + // Segments intersect at the endpoint of one of the segments. We + // allow this once, but the second one blocks visibility. Otherwise + // shapes butted up against each other could have visibility through + // shapes. + if (seenIntersectionAtEndpoint) + { + return true; + } + seenIntersectionAtEndpoint = true; + } + return false; +} + + // Returns true iff the point p in a valid region that can contain // shortest paths. a0, a1, a2 are ordered vertices of a shape. // @@ -205,20 +218,9 @@ int cornerSide(const Point &c1, const Point &c2, const Point &c3, int s12p = vecDir(c1, c2, p); int s23p = vecDir(c2, c3, p); - if (s12p == 0) - { - // Case of p being somewhere on c1-c2. - return s23p; - } - if (s23p == 0) - { - // Case of p being somewhere on c2-c3. - return s12p; - } - if (s123 == 1) { - if ((s12p == 1) && (s23p == 1)) + if ((s12p >= 0) && (s23p >= 0)) { return 1; } @@ -226,18 +228,37 @@ int cornerSide(const Point &c1, const Point &c2, const Point &c3, } else if (s123 == -1) { - if ((s12p == -1) && (s23p == -1)) + if ((s12p <= 0) && (s23p <= 0)) { return -1; } return 1; } - // Case of c3 being somewhere on c1-c2. + + // c1-c2-c3 are collinear, so just return vecDir from c1-c2 return s12p; } -// Returns the distance between points a and b. +// Returns the Euclidean distance between points a and b. +// +double euclideanDist(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 the Manhattan distance between points a and b. +// +double manhattanDist(const Point& a, const Point& b) +{ + return fabs(a.x - b.x) + fabs(a.y - b.y); +} + + +// Returns the Euclidean distance between points a and b. // double dist(const Point& a, const Point& b) { @@ -248,11 +269,12 @@ double dist(const Point& a, const Point& b) } // Returns the total length of all line segments in the polygon -double totalLength(const Polygn& poly) +double totalLength(const Polygon& poly) { double l = 0; - for (int i = 0; i < poly.pn-1; ++i) { - l += dist(poly.ps[i], poly.ps[i+1]); + for (size_t i = 1; i < poly.size(); ++i) + { + l += dist(poly.ps[i-1], poly.ps[i]); } return l; } @@ -277,18 +299,27 @@ double angle(const Point& a, const Point& b, const Point& c) // This is a fast version that only works for convex shapes. The // other version (inPolyGen) is more general. // -bool inPoly(const Polygn& poly, const Point& q) +bool inPoly(const Polygon& poly, const Point& q, bool countBorder) { - int n = poly.pn; - Point *P = poly.ps; - for (int i = 0; i < n; i++) + size_t n = poly.size(); + const std::vector<Point>& P = poly.ps; + bool onBorder = false; + for (size_t i = 0; i < n; i++) { // point index; i1 = i-1 mod n - int prev = (i + n - 1) % n; - if (vecDir(P[prev], P[i], q) == -1) + size_t prev = (i + n - 1) % n; + int dir = vecDir(P[prev], P[i], q); + if (dir == -1) { + // Point is outside return false; } + // Record if point was on a boundary. + onBorder |= (dir == 0); + } + if (!countBorder && onBorder) + { + return false; } return true; } @@ -299,37 +330,36 @@ bool inPoly(const Polygn& poly, const Point& q) // // Based on the code of 'InPoly'. // -bool inPolyGen(const Polygn& argpoly, const Point& q) +bool inPolyGen(const PolygonInterface& 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; + Polygon poly = argpoly; + std::vector<Point>& P = poly.ps; + size_t n = poly.size(); // Shift so that q is the origin. This is done for pedogical clarity. - for (int i = 0; i < n; ++i) + for (size_t 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) + for (size_t 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; + size_t i1 = ( i + n - 1 ) % n; // if e "straddles" the x-axis... // The commented-out statement is logically equivalent to the one @@ -367,7 +397,6 @@ bool inPolyGen(const Polygn& argpoly, const Point& q) } } } - freePoly(poly); // q on the edge if left and right cross are not the same parity. if ( (Rcross % 2) != (Lcross % 2) ) @@ -400,8 +429,7 @@ bool inPolyGen(const Polygn& argpoly, const Point& q) int segmentIntersectPoint(const Point& a1, const Point& a2, const Point& b1, const Point& b2, double *x, double *y) { - - double Ax,Bx,Cx,Ay,By,Cy,d,e,f,num,offset; + double Ax,Bx,Cx,Ay,By,Cy,d,e,f,num; double x1lo,x1hi,y1lo,y1hi; Ax = a2.x - a1.x; @@ -450,14 +478,13 @@ int segmentIntersectPoint(const Point& a1, const Point& a2, if (y1hi < b1.y || b2.y < y1lo) return DONT_INTERSECT; } - Cx = a1.x - b1.x; Cy = a1.y - b1.y; // alpha numerator: d = By*Cx - Bx*Cy; // Both denominator: f = Ay*Bx - Ax*By; - // aplha tests: + // alpha tests: if (f > 0) { if (d < 0 || d > f) return DONT_INTERSECT; @@ -485,15 +512,49 @@ int segmentIntersectPoint(const Point& a1, const Point& a2, // Numerator: num = d*Ax; - // Round direction: - offset = SAME_SIGNS(num,f) ? f/2 : -f/2; // Intersection X: - *x = a1.x + (num+offset) / f; + *x = a1.x + (num) / f; + + num = d*Ay; + // Intersection Y: + *y = a1.y + (num) / f; + + return DO_INTERSECT; +} + + +// Line Segment Intersection +// Original code by Franklin Antonio +// +int rayIntersectPoint(const Point& a1, const Point& a2, + const Point& b1, const Point& b2, double *x, double *y) +{ + double Ax,Bx,Cx,Ay,By,Cy,d,f,num; + + Ay = a2.y - a1.y; + By = b1.y - b2.y; + Ax = a2.x - a1.x; + Bx = b1.x - b2.x; + + Cx = a1.x - b1.x; + Cy = a1.y - b1.y; + // alpha numerator: + d = By*Cx - Bx*Cy; + // Both denominator: + f = Ay*Bx - Ax*By; + + // compute intersection coordinates: + + if (f == 0) return PARALLEL; + + // Numerator: + num = d*Ax; + // Intersection X: + *x = a1.x + (num) / f; num = d*Ay; - offset = SAME_SIGNS(num,f) ? f/2 : -f/2; // Intersection Y: - *y = a1.y + (num+offset) / f; + *y = a1.y + (num) / f; return DO_INTERSECT; } |