![[tokkee]](http://tokkee.org/images/avatar.png){kind=avatar}
index 20f04523146280191eeaa14ff52b84dcf6a7e5e8..15840c3816a9c85f5061db8352ae8649c8fd78ba 100644 (file)
* and/or described in "Computational Geometry in C" (Second Edition),
* Copyright (C) 1998 Joseph O'Rourke <orourke@cs.smith.edu>
* --------------------------------------------------------------------
+ * The segmentIntersectPoint function is based on code published and
+ * described in Franklin Antonio, Faster Line Segment Intersection,
+ * Graphics Gems III, p. 199-202, code: p. 500-501.
+ * --------------------------------------------------------------------
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
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.
//
// Based on the code of 'Between'.
// 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'
+ // since, unlike them, our 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(bool IgnoreRegions, const Point& a0, const Point& a1,
const Point& a2, const Point& b)
{
+ // r is a0--a1
+ // s is a1--a2
+
int rSide = vecDir(b, a0, a1);
int sSide = vecDir(b, a1, a2);
- bool rOutOn = (rSide >= 0);
- bool sOutOn = (sSide >= 0);
+ bool rOutOn = (rSide <= 0);
+ bool sOutOn = (sSide <= 0);
- bool rOut = (rSide > 0);
- bool sOut = (sSide > 0);
+ bool rOut = (rSide < 0);
+ bool sOut = (sSide < 0);
if (vecDir(a0, a1, a2) > 0)
{
- // Concave at a1:
+ // Convex at a1:
//
// !rO rO
- // !sO !sO
+ // sO sO
//
- // +---s---
+ // ---s---+
// |
// !rO r rO
- // sO | sO
+ // !sO | !sO
//
//
- return (IgnoreRegions ? false : (rOutOn && sOutOn));
+ if (IgnoreRegions)
+ {
+ return (rOutOn && !sOut) || (!rOut && sOutOn);
+ }
+ return (rOutOn || sOutOn);
}
else
{
- // Convex at a1:
+ // Concave at a1:
//
// !rO rO
- // sO sO
+ // !sO !sO
//
- // ---s---+
+ // +---s---
// |
// !rO r rO
- // !sO | !sO
+ // sO | sO
//
//
- if (IgnoreRegions)
+ return (IgnoreRegions ? false : (rOutOn && sOutOn));
+ }
+}
+
+
+// Gives the side of a corner that a point lies on:
+// 1 anticlockwise
+// -1 clockwise
+// e.g. /|s2
+// /s3 -1 / |
+// / / |
+// 1 |s2 -1 / 1 | -1
+// | / |
+// |s1 s3/ |s1
+//
+int cornerSide(const Point &c1, const Point &c2, const Point &c3,
+ const Point& p)
+{
+ int s123 = vecDir(c1, c2, 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))
{
- return (rOutOn && !sOut) || (!rOut && sOutOn);
+ return 1;
}
- return (rOutOn || sOutOn);
+ return -1;
+ }
+ else if (s123 == -1)
+ {
+ if ((s12p == -1) && (s23p == -1))
+ {
+ return -1;
+ }
+ return 1;
}
+ // Case of c3 being somewhere on c1-c2.
+ return s12p;
}
return sqrt((xdiff * xdiff) + (ydiff * ydiff));
}
+// Returns the total length of all line segments in the polygon
+double totalLength(const Polygn& poly)
+{
+ double l = 0;
+ for (int i = 0; i < poly.pn-1; ++i) {
+ l += dist(poly.ps[i], poly.ps[i+1]);
+ }
+ return l;
+}
+
+// Uses the dot-product rule to find the angle (radians) between ab and bc
+double angle(const Point& a, const Point& b, const Point& c)
+{
+ double ux = b.x - a.x,
+ uy = b.y - a.y,
+ vx = c.x - b.x,
+ vy = c.y - b.y,
+ lu = sqrt(ux*ux+uy*uy),
+ lv = sqrt(vx*vx+vy*vy),
+ udotv = ux * vx + uy * vy,
+ costheta = udotv / (lu * lv);
+ return acos(costheta);
+}
+
+// Returns true iff the point q is inside (or on the edge of) the
+// polygon argpoly.
+//
+// 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)
+{
+ int n = poly.pn;
+ Point *P = poly.ps;
+ for (int 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)
+ {
+ return false;
+ }
+ }
+ return true;
+}
+
// 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)
+bool inPolyGen(const Polygn& argpoly, const Point& q)
{
// Numbers of right and left edge/ray crossings.
int Rcross = 0;
}
+
+// Line Segment Intersection
+// Original code by Franklin Antonio
+//
+// The SAME_SIGNS macro assumes arithmetic where the exclusive-or
+// operation will work on sign bits. This works for twos-complement,
+// and most other machine arithmetic.
+#define SAME_SIGNS( a, b ) \
+ (((long) ((unsigned long) a ^ (unsigned long) b)) >= 0 )
+//
+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 x1lo,x1hi,y1lo,y1hi;
+
+ Ax = a2.x - a1.x;
+ Bx = b1.x - b2.x;
+
+ // X bound box test:
+ if (Ax < 0)
+ {
+ x1lo = a2.x;
+ x1hi = a1.x;
+ }
+ else
+ {
+ x1hi = a2.x;
+ x1lo = a1.x;
+ }
+ if (Bx > 0)
+ {
+ if (x1hi < b2.x || b1.x < x1lo) return DONT_INTERSECT;
+ }
+ else
+ {
+ if (x1hi < b1.x || b2.x < x1lo) return DONT_INTERSECT;
+ }
+
+ Ay = a2.y - a1.y;
+ By = b1.y - b2.y;
+
+ // Y bound box test:
+ if (Ay < 0)
+ {
+ y1lo = a2.y;
+ y1hi = a1.y;
+ }
+ else
+ {
+ y1hi = a2.y;
+ y1lo = a1.y;
+ }
+ if (By > 0)
+ {
+ if (y1hi < b2.y || b1.y < y1lo) return DONT_INTERSECT;
+ }
+ else
+ {
+ 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:
+ if (f > 0)
+ {
+ if (d < 0 || d > f) return DONT_INTERSECT;
+ }
+ else
+ {
+ if (d > 0 || d < f) return DONT_INTERSECT;
+ }
+
+ // beta numerator:
+ e = Ax*Cy - Ay*Cx;
+ // beta tests:
+ if (f > 0)
+ {
+ if (e < 0 || e > f) return DONT_INTERSECT;
+ }
+ else
+ {
+ if (e > 0 || e < f) return DONT_INTERSECT;
+ }
+
+ // compute intersection coordinates:
+
+ if (f == 0) return PARALLEL;
+
+ // Numerator:
+ num = d*Ax;
+ // Round direction:
+ offset = SAME_SIGNS(num,f) ? f/2 : -f/2;
+ // Intersection X:
+ *x = a1.x + (num+offset) / f;
+
+ num = d*Ay;
+ offset = SAME_SIGNS(num,f) ? f/2 : -f/2;
+ // Intersection Y:
+ *y = a1.y + (num+offset) / f;
+
+ return DO_INTERSECT;
+}
+
+
}