// Interpretation: given a line in the form x = a + tu, where u is the
// unit vector of the line, a is the tail and t is a parameter which
// describes the line, the distance of a point p to the line is given by:
- // || (a - p) - ((a - p) . u) u ||
+ // || (a - p) - ((a - p) • u) u ||
// We go an extra step: we set the sign to reflect which side of the line
// it's on (+ == to the left if head points away from you, - == to the
// right)
double rxs = (r.x * s.y) - (s.x * r.y);
double t, u;
+ // The angle is zero, so the lines probably overlap, or are parallel. Either way, there is either INFINITE intersections, or zero. Either way, the result is useless to us. It does present a bit of an inconsistency though: lines connected at their endpoints that aren't at a zero angle will show as overlapping (the only case this could even REMOTELY be useful is when the angle between is 180°--not zero, as zero is the degenerate case). :-P
if (rxs == 0)
{
- double qpxr = (v1.x * r.y) - (r.x * v1.y);
+// WHY would you do this??? The lines overlap at an INFINITE number of points!
+// The assumption is that the angle is 180°, not 0°.
+ // If we want to detect the degenerate case, we can check the parameter of the endpoints of the one line to the other. If any of the parameters are in (0, 1), then it's the degenerate case (we would check the endpoints of the shorter segment against the longer).
+/* double qpxr = (v1.x * r.y) - (r.x * v1.y);
- // Lines are parallel, so no intersection...
+ // Line segments are parallel, so no intersection...
if (qpxr != 0)
return;
+ // Otherwise, the segments are colinear. Need to check for the 0° (degenerate) vs the 180° (OK) case.
+ Object * larger = l1;
+ Object * smaller = l2;
+
+ if (r->Magnitude() < s->Magnitude())
+ {
+ larger = l2;
+ smaller = l1;
+ }
+
+ double param1 = ParameterOfLineAndPoint(larger->p[0], larger->p[1], smaller->p[0]);
+ double param2 = ParameterOfLineAndPoint(larger->p[0], larger->p[1], smaller->p[1]);
+
+ // Check for the degenerate case, and return if found
+ if ((param1 > 0 && param1 < 1.0) || (param2 > 0 && param2 < 1.0))
+ return;
+
+//// or just use AngleBetween: Nah, won't work...
+
// Check to see which endpoints are connected... Four possibilities:
if (l1->p[0] == l2->p[0])
t = 0, u = 0;
t = 1.0, u = 0;
else if (l1->p[1] == l2->p[1])
t = 1.0, u = 1.0;
- else
+ else*/
return;
}
else
u = ((v1.x * r.y) - (r.x * v1.y)) / rxs;
}
+ // Check that the parameters are above the epsilon, otherwise clamp them to
+ // zero or one, as the case may be
+ if (fabs(t) < EPSILON)
+ t = 0;
+ else if (fabs(1.0 - t) < EPSILON)
+ t = 1.0;
+
+ if (fabs(u) < EPSILON)
+ u = 0;
+ else if (fabs(1.0 - u) < EPSILON)
+ u = 1.0;
+
Global::intersectParam[0] = t;
Global::intersectParam[1] = u;
// If the parameters are in range, we have overlap!
if ((t >= 0) && (t <= 1.0) && (u >= 0) && (u <= 1.0))
- Global::numIntersectParams = 1;
+ Global::numIntersectParams = 2;
}
void Geometry::CheckCircleToCircleIntersection(Object * c1, Object * c2)
return (l1 < l2 ? p1 : p2);
}
+
+Vector Geometry::GetNormalOfPointAndLine(Point p, Line * l)
+{
+ Vector normal = Vector::Normal(l->p[0], l->p[1]);
+ normal.Unit();
+ double dir = Vector::Dot(p - l->p[0], normal);
+
+ if (dir < 0)
+ normal = -normal;
+
+ return normal;
+}
+
+Circle Geometry::FindCircleForThreePoints(Point p1, Point p2, Point p3)
+{
+ // We use matrices and determinants to find the center and radius of the
+ // circle, given the three points passed in:
+ //
+ // [(x^2 + y^2) x y 1 ]
+ // [(x1^2 + y1^2) x1 y1 1 ]
+ // [(x2^2 + y2^2) x2 y2 1 ]
+ // [(x3^2 + y3^2) x3 y3 1 ]
+ //
+ // Then, center <x0, y0> is found by:
+ //
+ // x0 = 1/2 • M12/M11, y0 = -1/2 • M13/M11
+ //
+ // The radius can be found with the center and any of the points via
+ // Pythagoras, or with:
+ //
+ // r^2 = x0^2 + y0^2 + M14/M11
+ //
+ // If M11 = 0, then the three points are colinear and there is no circle.
+ // (M## is the minor determinant of the 4x4 matrix, where a 3x3 matrix is
+ // created by deleting the row and column of the 4x4 with the indices
+ // given.)
+
+ Circle c;
+ double m[3][4];
+
+ m[0][0] = (p1.x * p1.x) + (p1.y * p1.y);
+ m[0][1] = p1.x;
+ m[0][2] = p1.y;
+ m[0][3] = 1.0;
+ m[1][0] = (p2.x * p2.x) + (p2.y * p2.y);
+ m[1][1] = p2.x;
+ m[1][2] = p2.y;
+ m[1][3] = 1.0;
+ m[2][0] = (p3.x * p3.x) + (p3.y * p3.y);
+ m[2][1] = p3.x;
+ m[2][2] = p3.y;
+ m[2][3] = 1.0;
+
+ double minor11 = Determinant3x3(m[0][1], m[0][2], m[0][3], m[1][1], m[1][2], m[1][3], m[2][1], m[2][2], m[2][3]);
+
+ // Sanity check: if M11 is zero, the points are colinear.
+ if (minor11 == 0)
+ return c;
+
+ double minor12 = Determinant3x3(m[0][0], m[0][2], m[0][3], m[1][0], m[1][2], m[1][3], m[2][0], m[2][2], m[2][3]);
+ double minor13 = Determinant3x3(m[0][0], m[0][1], m[0][3], m[1][0], m[1][1], m[1][3], m[2][0], m[2][1], m[2][3]);
+ double minor14 = Determinant3x3(m[0][0], m[0][1], m[0][2], m[1][0], m[1][1], m[1][2], m[2][0], m[2][1], m[2][2]);
+
+ c.p[0].x = 0.5 * (minor12 / minor11);
+ c.p[0].y = -0.5 * (minor13 / minor11);
+ c.radius[0] = sqrt((c.p[0].x * c.p[0].x) + (c.p[0].y * c.p[0].y) + (minor14 / minor11));
+
+ return c;
+}
+
+double Geometry::Determinant3x3(double a11, double a12, double a13, double a21, double a22, double a23, double a31, double a32, double a33)
+{
+ return (a11 * ((a22 * a33) - (a32 * a23)))
+ - (a12 * ((a21 * a33) - (a31 * a23)))
+ + (a13 * ((a21 * a32) - (a31 * a22)));
+}
+
+Arc Geometry::Unpack(Point tail, Point head, double bump)
+{
+ double length = Vector::Magnitude(tail, head) / 2.0;
+ double bumpLen = length * fabs(bump);
+ Point midpoint = (tail + head) / 2.0;
+ Vector mpNormal = Vector::Normal(tail, head); // Normal points to the left
+
+ // Flip the normal if the bump is pointing left
+ if (bump < 0)
+ mpNormal = -mpNormal;
+
+ // N.B.: The radius can also be found with r = (a² + h²) / 2h where a is
+ // the 1/2 length of the line segment and h is the bump length.
+// double radius = (length + (1.0 / length)) / 2.0;
+ double radius = 0.5 * (((length * length) + (bumpLen * bumpLen)) / bumpLen);
+ Vector ctrVec = mpNormal * (radius - bumpLen);
+ Point center = midpoint + ctrVec;
+
+ // Find arc endpoints...
+ double angle1 = Vector::Angle(center, tail);
+ double angle2 = Vector::Angle(center, head);
+ double span = angle2 - angle1;
+
+ // Fix span depending on which way the arc is being drawn...
+ if (bump > 0 && span < 0)
+ span += TAU;
+
+ if (bump < 0 && span > 0)
+ span -= TAU;
+
+ return Arc(center, radius, angle1, span);
+}
projects / architektonas / blobdiff