![[tokkee]](http://tokkee.org/images/avatar.png){kind=avatar}
index 15840c3816a9c85f5061db8352ae8649c8fd78ba..2523375cf2addacb63379ab5671bdbb6becd2c3c 100644 (file)
* 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
* 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)) ||
}
+// 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.
//
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,
}
+// 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.
//
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;
}
}
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)
{
}
// 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;
}
// 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;
}
//
// 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
}
}
}
- freePoly(poly);
// q on the edge if left and right cross are not the same parity.
if ( (Rcross % 2) != (Lcross % 2) )
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;
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;
// 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;
}