53 #ifndef GEO_ALGORITHMS_HH
54 #define GEO_ALGORITHMS_HH
60 #include <ACG/Math/VectorT.hh>
74 template<
typename Scalar>
84 template<
typename Scalar>
92 return circumCenter(_v0, _v1, _v2, _v3, cc) ? (cc-_v0).sqrnorm() : FLT_MAX;
97 template<
typename Scalar>
119 template<
typename Scalar>
140 template<
typename Scalar>
146 bool _degree =
true);
157 template <
typename Scalar>
178 template<
typename Vec>
185 typename Vec::value_type& _t,
186 typename Vec::value_type& _u,
187 typename Vec::value_type& _v );
202 template<
typename Vec>
208 typename Vec::value_type& _t0,
209 typename Vec::value_type& _t1 );
215 template<
typename Scalar>
222 return (d1[0]*d2[1]-d1[1]*d2[0]);
227 template<
typename Scalar>
238 template<
typename Scalar>
249 template<
typename Scalar>
274 typename Vec::value_type
294 typename Vec::value_type
304 typename Vec::value_type
305 distPointTriangleSquared(
const Vec& _p,
309 Vec& _nearestPoint );
323 typename Vec::value_type
328 Vec& _nearestPoint );
332 typename Vec::value_type
338 {
return sqrt(distPointTriangleSquared(_p, _v0, _v1, _v2, _nearestPoint)); }
351 typename Vec::value_type
367 template <
typename VectorT ,
typename ValueT >
383 template<
typename Scalar>
391 bool _fastApprox=
false );
395 template<
typename Scalar>
423 template <
typename VectorT >
435 template <
typename VectorT >
453 template<
typename Scalar>
464 template<
typename Scalar>
473 return ((bary[0]>0.0) && (bary[1]>0.0) && (bary[2]>0.0));
475 std::cerr <<
"point in triangle error\n";
480 template<
typename Scalar>
496 template<
typename Scalar>
506 template<
typename Scalar>
516 template<
typename Scalar>
524 template<
typename Scalar>
535 template<
typename Scalar>
544 template<
typename Scalar>
552 template<
typename Scalar>
568 template<
class VectorT>
588 typename Vec::value_type
601 typename Vec::value_type
616 template <
typename Scalar,
int N>
628 template <
typename Scalar,
int N>
640 #if defined(INCLUDE_TEMPLATES) && !defined(GEO_ALGORITHMS_C)
641 #define GEO_ALGORITHMS_TEMPLATES
642 #include "Algorithms.cc"
645 #endif // GEO_ALGORITHMS_HH defined
VectorT< Scalar, 3 > perpendicular(const VectorT< Scalar, 3 > &v)
find a vector that's perpendicular to _v
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
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
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 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 aspectRatio(const VectorT< Scalar, N > &_v0, const VectorT< Scalar, N > &_v1, const VectorT< Scalar, N > &_v2)
return aspect ratio (length/height) of triangle
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)
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
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)
ValueT distPointPlane(const VectorT &_porigin, const VectorT &_pnormal, const VectorT &_point)
Checks the distance from a point to a plane.
int isObtuse(const VectorT &_p0, const VectorT &_p1, const VectorT &_p2)
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)
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 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)
Vec::value_type triangleArea(const Vec &_v0, const Vec &_v1, const Vec &_v2)
return area of triangle (_v0, _v1, _v2)
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)
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)
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)
Vec::value_type distPointLine(const Vec &_p, const Vec &_v0, const Vec &_v1, Vec *_min_v=0)
Compute distance from point to line segment.
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
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)
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.
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 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
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)
Vec::value_type triangleAreaSquared(const Vec &_v0, const Vec &_v1, const Vec &_v2)
return squared area of 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.
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)
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 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)
VectorT projectToEdge(const VectorT &_start, const VectorT &_end, const VectorT &_point)