44 #ifndef GEO_ALGORITHMS_HH 45 #define GEO_ALGORITHMS_HH 51 #include <ACG/Math/VectorT.hh> 55 #include "../Math/Matrix3x3T.hh" 67 template<
typename Scalar>
77 template<
typename Scalar>
85 return circumCenter(_v0, _v1, _v2, _v3, cc) ? (cc-_v0).sqrnorm() : FLT_MAX;
90 template<
typename Scalar>
112 template<
typename Scalar>
133 template<
typename Scalar>
139 bool _degree =
true);
150 template <
typename Scalar>
171 template<
typename Vec>
178 typename Vec::value_type& _t,
179 typename Vec::value_type& _u,
180 typename Vec::value_type& _v );
195 template<
typename Vec>
201 typename Vec::value_type& _t0,
202 typename Vec::value_type& _t1 );
208 template<
typename Scalar>
215 return (d1[0]*d2[1]-d1[1]*d2[0]);
220 template<
typename Scalar>
231 template<
typename Scalar>
242 template<
typename Scalar>
267 typename Vec::value_type
287 typename Vec::value_type
297 typename Vec::value_type
298 distPointTriangleSquared(
const Vec& _p,
302 Vec& _nearestPoint );
316 typename Vec::value_type
321 Vec& _nearestPoint );
325 typename Vec::value_type
331 {
return sqrt(distPointTriangleSquared(_p, _v0, _v1, _v2, _nearestPoint)); }
344 typename Vec::value_type
360 template <
typename VectorT ,
typename ValueT >
376 template<
typename Scalar>
384 bool _fastApprox=
false );
388 template<
typename Scalar>
416 template <
typename VectorT >
428 template <
typename VectorT >
446 template<
typename Scalar>
457 template<
typename Scalar>
466 return ((bary[0]>0.0) && (bary[1]>0.0) && (bary[2]>0.0));
468 std::cerr <<
"point in triangle error\n";
473 template<
typename Scalar>
489 template<
typename Scalar>
499 template<
typename Scalar>
509 template<
typename Scalar>
517 template<
typename Scalar>
528 template<
typename Scalar>
537 template<
typename Scalar>
545 template<
typename Scalar>
561 template<
class VectorT>
581 typename Vec::value_type
594 typename Vec::value_type
609 template <
typename Scalar,
int N>
621 template <
typename Scalar,
int N>
629 template<
typename Vector>
631 const auto delta = ((p2-p1)|(x-p1)) / (p2-p1).
sqrnorm();
636 }
else if (delta >= 1) {
639 }
else if (delta != delta) {
641 return (x-p1).
sqrnorm() < (x-p2).sqrnorm() ? p1 : p2;
644 return (1 - delta) * p1 + delta * p2;
648 template<
typename Vector>
650 constexpr
double thresh = 1e-8;
652 const auto n = ((b - a) % (c - a));
654 if ((b-a).sqrnorm() < thresh || (c-a).sqrnorm() < thresh || n.sqrnorm() < thresh) {
657 std::array<ACG::Vec3d, 2> max_segment = {a, b};
658 double max_len = (b-a).sqrnorm();
659 if ((c-a).sqrnorm() > max_len)
660 max_segment = {a, c};
661 if ((c-b).sqrnorm() > max_len)
662 max_segment = {b, c};
665 return closestPointLineSegment(p, max_segment[0], max_segment[1]);
668 const auto abd = Matrix3x3d::fromColumns(a-c, b-c, n).inverse() * (p - c);
669 const bool alpha = (abd[0] >= 0.0),
670 beta = (abd[1] >= 0.0),
671 gamma = (1.0-abd[0]-abd[1] >= 0.0);
673 if (alpha && beta && gamma) {
676 return abd[0] * a + abd[1] * b + (1.0 - abd[0] - abd[1]) * c;
680 return closestPointLineSegment(p, b, c);
684 return closestPointLineSegment(p, a, c);
688 return closestPointLineSegment(p, a, b);
690 throw std::logic_error(
"This cannot happen.");
698 #if defined(INCLUDE_TEMPLATES) && !defined(GEO_ALGORITHMS_C) 699 #define GEO_ALGORITHMS_TEMPLATES 700 #include "Algorithms.cc" 703 #endif // GEO_ALGORITHMS_HH defined Namespace providing different geometric functions concerning angles.
bool isCCW(const VectorT< Scalar, 2 > &_v0, const VectorT< Scalar, 2 > &_v1, const VectorT< Scalar, 2 > &_v2)
are 3 vertices in counterclockwise order? in 2D
VectorT projectToEdge(const VectorT &_start, const VectorT &_end, const VectorT &_point)
decltype(std::declval< S >() *std::declval< S >()) sqrnorm() const
compute squared euclidean norm
ValueT distPointPlane(const VectorT &_porigin, const VectorT &_pnormal, const VectorT &_point)
Checks the distance from a point to a plane.
Scalar distLineLineSquared(const VectorT< Scalar, 3 > &_v00, const VectorT< Scalar, 3 > &_v01, const VectorT< Scalar, 3 > &_v10, const VectorT< Scalar, 3 > &_v11, VectorT< Scalar, 3 > *_min_v0, VectorT< Scalar, 3 > *_min_v1, bool _fastApprox)
squared distance of lines (_v00, _v01) and (_v10, _v11)
Scalar roundness(const VectorT< Scalar, N > &_v0, const VectorT< Scalar, N > &_v1, const VectorT< Scalar, N > &_v2)
return roundness of triangle: 1=equilateral, 0=colinear
bool isInTriangle(const VectorT< Scalar, 2 > &_p, const VectorT< Scalar, 2 > &_u, const VectorT< Scalar, 2 > &_v, const VectorT< Scalar, 2 > &_w)
is point _p in triangle (_v0,_v1,_v2) in 2D
int isObtuse(const VectorT &_p0, const VectorT &_p1, const VectorT &_p2)
Vec::value_type triangleAreaSquared(const Vec &_v0, const Vec &_v1, const Vec &_v2)
return squared area of triangle (_v0, _v1, _v2)
Vec::value_type triangleArea(const Vec &_v0, const Vec &_v1, const Vec &_v2)
return area of triangle (_v0, _v1, _v2)
bool circumCenter(const VectorT< Scalar, 3 > &_v0, const VectorT< Scalar, 3 > &_v1, const VectorT< Scalar, 3 > &_v2, VectorT< Scalar, 3 > &_result)
return circumcenter of triangle (_v0,_v1,_v2)
Scalar pointLineOrientation(const VectorT< Scalar, 2 > &_p, const VectorT< Scalar, 2 > &_v0, const VectorT< Scalar, 2 > &_v1)
orientation of point _p w.r.t. line through _v0,_v1 in 2D
bool edgeConvexPolygonIntersection(std::vector< VectorT< Scalar, 3 > > _polygon_points, VectorT< Scalar, 3 > _v0, VectorT< Scalar, 3 > _v1, VectorT< Scalar, 3 > &_result)
Get intersection point of a ray and a convex polygon.
VectorT projectToPlane(const VectorT &_porigin, const VectorT &_pnormal, const VectorT &_point)
projects a point to a plane
Scalar distLineLine(const VectorT< Scalar, 3 > &_v00, const VectorT< Scalar, 3 > &_v01, const VectorT< Scalar, 3 > &_v10, const VectorT< Scalar, 3 > &_v11, VectorT< Scalar, 3 > *_min_v0=0, VectorT< Scalar, 3 > *_min_v1=0)
distance of lines (_v00, _v01) and (_v10, _v11)
Vec::value_type distPointTriangleSquaredStable(const Vec &_p, const Vec &_v0, const Vec &_v1, const Vec &_v2, Vec &_nearestPoint)
squared distance from point _p to triangle (_v0, _v1, _v2)
Vec::value_type distPointLineSquared(const Vec &_p, const Vec &_v0, const Vec &_v1, Vec *_min_v)
squared distance from point _p to line segment (_v0,_v1)
Scalar aspectRatio(const VectorT< Scalar, N > &_v0, const VectorT< Scalar, N > &_v1, const VectorT< Scalar, N > &_v2)
return aspect ratio (length/height) of triangle
Scalar minRadius(const VectorT< Scalar, 3 > &_v0, const VectorT< Scalar, 3 > &_v1, const VectorT< Scalar, 3 > &_v2)
return radius of min. enclosing circle of triangle (_v0,_v1,_v2)
VectorT< Scalar, 3 > perpendicular(const VectorT< Scalar, 3 > &v)
find a vector that's perpendicular to _v
Vec::value_type distPointLine(const Vec &_p, const Vec &_v0, const Vec &_v1, Vec *_min_v=0)
Compute distance from point to line segment.
bool rotationOfTwoVectors(const VectorT< Scalar, 3 > &_v0, const VectorT< Scalar, 3 > &_v1, VectorT< Scalar, 3 > &_axis, Scalar &_angle, bool _degree)
Get rotation axis and signed angle of rotation between two vectors.
Vec::value_type distPointTriangleStable(const Vec &_p, const Vec &_v0, const Vec &_v1, const Vec &_v2, Vec &_nearestPoint)
distance from point _p to triangle (_v0, _v1, _v2)
bool axisAlignedBBIntersection(const Vec &_o, const Vec &_dir, const Vec &_bbmin, const Vec &_bbmax, typename Vec::value_type &tmin, typename Vec::value_type &tmax)
Intersect a ray and an axis aligned bounding box.
Scalar circumRadius(const VectorT< Scalar, 3 > &_v0, const VectorT< Scalar, 3 > &_v1, const VectorT< Scalar, 3 > &_v2, const VectorT< Scalar, 3 > &_v3)
return radius of circumcircle of tetrahedron (_v0,_v1,_v2,_v3)
Vec::value_type distPointTriangle(const Vec &_p, const Vec &_v0, const Vec &_v1, const Vec &_v2, Vec &_nearestPoint)
distance from point _p to triangle (_v0, _v1, _v2)
bool minSphere(const VectorT< Scalar, 3 > &_v0, const VectorT< Scalar, 3 > &_v1, const VectorT< Scalar, 3 > &_v2, VectorT< Scalar, 3 > &_center, Scalar &_radius)
construct min. enclosing sphere
Scalar circumRadiusSquared(const VectorT< Scalar, 3 > &_v0, const VectorT< Scalar, 3 > &_v1, const VectorT< Scalar, 3 > &_v2)
return squared radius of circumcircle of triangle (_v0,_v1,_v2)
bool baryCoord(const VectorT< Scalar, 3 > &_p, const VectorT< Scalar, 3 > &_u, const VectorT< Scalar, 3 > &_v, const VectorT< Scalar, 3 > &_w, VectorT< Scalar, 3 > &_result)
Scalar minRadiusSquared(const VectorT< Scalar, 3 > &_v0, const VectorT< Scalar, 3 > &_v1, const VectorT< Scalar, 3 > &_v2)
return squared radius of min. enclosing circle of triangle (_v0,_v1,_v2)
bool isCW(const VectorT< Scalar, 2 > &_v0, const VectorT< Scalar, 2 > &_v1, const VectorT< Scalar, 2 > &_v2)
are 3 vertices in clockwise order? in 2D
bool triangleIntersection(const Vec &_o, const Vec &_dir, const Vec &_v0, const Vec &_v1, const Vec &_v2, typename Vec::value_type &_t, typename Vec::value_type &_u, typename Vec::value_type &_v)
Intersect a ray and a triangle.
bool lineIntersection(const VectorT< Scalar, 2 > &_v0, const VectorT< Scalar, 2 > &_v1, const VectorT< Scalar, 2 > &_v2, const VectorT< Scalar, 2 > &_v3, Scalar &_t1, Scalar &_t2)
intersect two line segments (_v0,_v1) and (_v2,_v3)