Developer Documentation
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Modules Pages
Algorithms.hh
1 /*===========================================================================*\
2  * *
3  * OpenFlipper *
4  * Copyright (c) 2001-2015, RWTH-Aachen University *
5  * Department of Computer Graphics and Multimedia *
6  * All rights reserved. *
7  * www.openflipper.org *
8  * *
9  *---------------------------------------------------------------------------*
10  * This file is part of OpenFlipper. *
11  *---------------------------------------------------------------------------*
12  * *
13  * Redistribution and use in source and binary forms, with or without *
14  * modification, are permitted provided that the following conditions *
15  * are met: *
16  * *
17  * 1. Redistributions of source code must retain the above copyright notice, *
18  * this list of conditions and the following disclaimer. *
19  * *
20  * 2. Redistributions in binary form must reproduce the above copyright *
21  * notice, this list of conditions and the following disclaimer in the *
22  * documentation and/or other materials provided with the distribution. *
23  * *
24  * 3. Neither the name of the copyright holder nor the names of its *
25  * contributors may be used to endorse or promote products derived from *
26  * this software without specific prior written permission. *
27  * *
28  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS *
29  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED *
30  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A *
31  * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER *
32  * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, *
33  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, *
34  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR *
35  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF *
36  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING *
37  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS *
38  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. *
39  * *
40 \*===========================================================================*/
41 
42 /*===========================================================================*\
43  * *
44  * $Revision$ *
45  * $Author$ *
46  * $Date$ *
47  * *
48 \*===========================================================================*/
49 
50 
51 
52 
53 #ifndef GEO_ALGORITHMS_HH
54 #define GEO_ALGORITHMS_HH
55 
56 
57 //== INCLUDES =================================================================
58 
59 #include <cfloat>
60 #include <ACG/Math/VectorT.hh>
61 #include <vector>
62 #include <iostream>
63 
64 #include "../Math/Matrix3x3T.hh"
65 
66 
67 namespace ACG {
68 namespace Geometry {
69 
70 
71 //== 3D STUFF =================================================================
72 
73 
74 
76 template<typename Scalar>
77 bool
78 circumCenter( const VectorT<Scalar,3>& _v0,
79  const VectorT<Scalar,3>& _v1,
80  const VectorT<Scalar,3>& _v2,
81  const VectorT<Scalar,3>& _v3,
82  VectorT<Scalar,3>& _result );
83 
84 
86 template<typename Scalar>
87 Scalar
88 circumRadiusSquared( const VectorT<Scalar,3>& _v0,
89  const VectorT<Scalar,3>& _v1,
90  const VectorT<Scalar,3>& _v2,
91  const VectorT<Scalar,3>& _v3 )
92 {
93  VectorT<Scalar,3> cc;
94  return circumCenter(_v0, _v1, _v2, _v3, cc) ? (cc-_v0).sqrnorm() : FLT_MAX;
95 }
96 
97 
99 template<typename Scalar>
100 Scalar
101 circumRadius( const VectorT<Scalar,3>& _v0,
102  const VectorT<Scalar,3>& _v1,
103  const VectorT<Scalar,3>& _v2,
104  const VectorT<Scalar,3>& _v3 )
105 {
106  return sqrt(circumRadiusSquared(_v0, _v1, _v2, _v3));
107 }
108 
121 template<typename Scalar>
122 bool edgeConvexPolygonIntersection(std::vector<VectorT<Scalar,3> > _polygon_points,
123  VectorT<Scalar,3> _v0,
124  VectorT<Scalar,3> _v1,
125  VectorT<Scalar,3> &_result);
126 
127 
142 template<typename Scalar>
143 bool
144 rotationOfTwoVectors( const VectorT<Scalar,3>& _v0,
145  const VectorT<Scalar,3>& _v1,
146  VectorT<Scalar,3>& _axis,
147  Scalar& _angle,
148  bool _degree = true);
149 
150 
159 template <typename Scalar>
160 VectorT<Scalar,3>
161 perpendicular( const VectorT<Scalar,3>& _v );
162 
163 
180 template<typename Vec>
181 bool
182 triangleIntersection( const Vec& _o,
183  const Vec& _dir,
184  const Vec& _v0,
185  const Vec& _v1,
186  const Vec& _v2,
187  typename Vec::value_type& _t,
188  typename Vec::value_type& _u,
189  typename Vec::value_type& _v );
190 
191 
204 template<typename Vec>
205 bool
206 axisAlignedBBIntersection( const Vec& _o,
207  const Vec& _dir,
208  const Vec& _bbmin,
209  const Vec& _bbmax,
210  typename Vec::value_type& _t0,
211  typename Vec::value_type& _t1 );
212 
213 
214 //== 2D STUFF =================================================================
215 
217 template<typename Scalar>
218 Scalar
219 pointLineOrientation( const VectorT<Scalar,2>& _p,
220  const VectorT<Scalar,2>& _v0,
221  const VectorT<Scalar,2>& _v1 )
222 {
223  VectorT<Scalar,2> d1(_p-_v0), d2(_v1-_v0);
224  return (d1[0]*d2[1]-d1[1]*d2[0]);
225 }
226 
227 
229 template<typename Scalar>
230 bool
231 isCCW( const VectorT<Scalar,2>& _v0,
232  const VectorT<Scalar,2>& _v1,
233  const VectorT<Scalar,2>& _v2 )
234 {
235  return ( pointLineOrientation(_v0, _v1, _v2) < Scalar(0.0) );
236 }
237 
238 
240 template<typename Scalar>
241 bool
242 isCW( const VectorT<Scalar,2>& _v0,
243  const VectorT<Scalar,2>& _v1,
244  const VectorT<Scalar,2>& _v2 )
245 {
246  return ( pointLineOrientation(_v0, _v1, _v2) > Scalar(0.0) );
247 }
248 
249 
251 template<typename Scalar>
252 bool
253 lineIntersection( const VectorT<Scalar,2>& _v0,
254  const VectorT<Scalar,2>& _v1,
255  const VectorT<Scalar,2>& _v2,
256  const VectorT<Scalar,2>& _v3,
257  Scalar& _t1,
258  Scalar& _t2 );
259 
260 
261 //===========================================================================
264 //===========================================================================
265 
266 
275 template<class Vec>
276 typename Vec::value_type
277 distPointLineSquared( const Vec& _p,
278  const Vec& _v0,
279  const Vec& _v1,
280  Vec* _min_v=0);
281 
282 
283 
295 template<class Vec>
296 typename Vec::value_type
297 distPointLine( const Vec& _p,
298  const Vec& _v0,
299  const Vec& _v1,
300  Vec* _min_v=0 )
301 { return sqrt(distPointLineSquared(_p, _v0, _v1, _min_v)); }
302 
303 
305 template <class Vec>
306 typename Vec::value_type
307 distPointTriangleSquared( const Vec& _p,
308  const Vec& _v0,
309  const Vec& _v1,
310  const Vec& _v2,
311  Vec& _nearestPoint );
312 
324 template <class Vec>
325 typename Vec::value_type
326 distPointTriangleSquaredStable( const Vec& _p,
327  const Vec& _v0,
328  const Vec& _v1,
329  const Vec& _v2,
330  Vec& _nearestPoint );
331 
333 template <class Vec>
334 typename Vec::value_type
335 distPointTriangle( const Vec& _p,
336  const Vec& _v0,
337  const Vec& _v1,
338  const Vec& _v2,
339  Vec& _nearestPoint )
340 { return sqrt(distPointTriangleSquared(_p, _v0, _v1, _v2, _nearestPoint)); }
341 
352 template <class Vec>
353 typename Vec::value_type
354 distPointTriangleStable( const Vec& _p,
355  const Vec& _v0,
356  const Vec& _v1,
357  const Vec& _v2,
358  Vec& _nearestPoint )
359 { return sqrt(distPointTriangleSquaredStable(_p, _v0, _v1, _v2, _nearestPoint)); }
360 
369 template < typename VectorT , typename ValueT >
370 inline
371 ValueT
372 distPointPlane(const VectorT& _porigin,
373  const VectorT& _pnormal,
374  const VectorT& _point);
375 
376 
379 //===========================================================================
382 //===========================================================================
383 
385 template<typename Scalar>
386 Scalar
387 distLineLineSquared( const VectorT<Scalar,3>& _v00,
388  const VectorT<Scalar,3>& _v01,
389  const VectorT<Scalar,3>& _v10,
390  const VectorT<Scalar,3>& _v11,
391  VectorT<Scalar,3>* _min_v0=0,
392  VectorT<Scalar,3>* _min_v1=0,
393  bool _fastApprox=false );
394 
395 
397 template<typename Scalar>
398 Scalar
399 distLineLine( const VectorT<Scalar,3>& _v00,
400  const VectorT<Scalar,3>& _v01,
401  const VectorT<Scalar,3>& _v10,
402  const VectorT<Scalar,3>& _v11,
403  VectorT<Scalar,3>* _min_v0=0,
404  VectorT<Scalar,3>* _min_v1=0 )
405 {
406  return sqrt(distLineLineSquared(_v00, _v01, _v10, _v11,
407  _min_v0, _min_v1));
408 }
409 
413 //===========================================================================
416 //===========================================================================
417 
418 
425 template < typename VectorT >
426 VectorT projectToEdge(const VectorT& _start ,
427  const VectorT& _end ,
428  const VectorT& _point );
429 
430 
437 template < typename VectorT >
438 inline
439 VectorT
440 projectToPlane(const VectorT& _porigin,
441  const VectorT& _pnormal,
442  const VectorT& _point);
443 
446 //===========================================================================
449 //===========================================================================
450 
455 template<typename Scalar>
457 bool
458 baryCoord( const VectorT<Scalar,2>& _p,
459  const VectorT<Scalar,2>& _u,
460  const VectorT<Scalar,2>& _v,
461  const VectorT<Scalar,2>& _w,
462  VectorT<Scalar,3>& _result );
463 
464 
466 template<typename Scalar>
467 bool
468 isInTriangle( const VectorT<Scalar,2>& _p,
469  const VectorT<Scalar,2>& _u,
470  const VectorT<Scalar,2>& _v,
471  const VectorT<Scalar,2>& _w )
472 {
473  VectorT<Scalar,3> bary;
474  if (baryCoord(_p, _u, _v, _w, bary))
475  return ((bary[0]>0.0) && (bary[1]>0.0) && (bary[2]>0.0));
476  else {
477  std::cerr << "point in triangle error\n";
478  return false;
479  }
480 }
481 
482 template<typename Scalar>
483 bool
484 circumCenter( const VectorT<Scalar,2>& _v0,
485  const VectorT<Scalar,2>& _v1,
486  const VectorT<Scalar,2>& _v2,
487  VectorT<Scalar,2>& _result );
488 
491 //===========================================================================
494 //===========================================================================
495 
498 template<typename Scalar>
499 bool
500 baryCoord( const VectorT<Scalar,3>& _p,
501  const VectorT<Scalar,3>& _u,
502  const VectorT<Scalar,3>& _v,
503  const VectorT<Scalar,3>& _w,
504  VectorT<Scalar,3>& _result );
505 
506 
508 template<typename Scalar>
509 bool
510 minSphere(const VectorT<Scalar,3>& _v0,
511  const VectorT<Scalar,3>& _v1,
512  const VectorT<Scalar,3>& _v2,
513  VectorT<Scalar,3>& _center,
514  Scalar& _radius);
515 
516 
518 template<typename Scalar>
519 Scalar
520 minRadiusSquared( const VectorT<Scalar,3>& _v0,
521  const VectorT<Scalar,3>& _v1,
522  const VectorT<Scalar,3>& _v2 );
523 
524 
526 template<typename Scalar>
527 Scalar
528 minRadius( const VectorT<Scalar,3>& _v0,
529  const VectorT<Scalar,3>& _v1,
530  const VectorT<Scalar,3>& _v2 )
531 {
532  return sqrt(minRadiusSquared(_v0, _v1, _v2));
533 }
534 
535 
537 template<typename Scalar>
538 bool
539 circumCenter( const VectorT<Scalar,3>& _v0,
540  const VectorT<Scalar,3>& _v1,
541  const VectorT<Scalar,3>& _v2,
542  VectorT<Scalar,3>& _result );
543 
544 
546 template<typename Scalar>
547 Scalar
548 circumRadiusSquared( const VectorT<Scalar,3>& _v0,
549  const VectorT<Scalar,3>& _v1,
550  const VectorT<Scalar,3>& _v2 );
551 
552 
554 template<typename Scalar>
555 Scalar
556 circumRadius( const VectorT<Scalar,3>& _v0,
557  const VectorT<Scalar,3>& _v1,
558  const VectorT<Scalar,3>& _v2 )
559 {
560  return sqrt(circumRadiusSquared(_v0, _v1, _v2));
561 }
562 
570 template<class VectorT>
571 int isObtuse(const VectorT& _p0,
572  const VectorT& _p1,
573  const VectorT& _p2 );
574 
577 //===========================================================================
580 //===========================================================================
581 
582 
589 template <class Vec>
590 typename Vec::value_type
591 triangleAreaSquared( const Vec& _v0,
592  const Vec& _v1,
593  const Vec& _v2 );
594 
595 
602 template <class Vec>
603 typename Vec::value_type
604 triangleArea( const Vec& _v0,
605  const Vec& _v1,
606  const Vec& _v2 )
607 {
608  return sqrt(triangleAreaSquared(_v0,_v1,_v2));
609 }
610 
611 
618 template <typename Scalar, int N>
619 Scalar
620 aspectRatio( const VectorT<Scalar, N>& _v0,
621  const VectorT<Scalar, N>& _v1,
622  const VectorT<Scalar, N>& _v2 );
623 
630 template <typename Scalar, int N>
631 Scalar
632 roundness( const VectorT<Scalar, N>& _v0,
633  const VectorT<Scalar, N>& _v1,
634  const VectorT<Scalar, N>& _v2 );
635 
638 template<typename Vector>
639 Vector closestPointLineSegment(Vector x, Vector p1, Vector p2) {
640  const auto delta = ((p2-p1)|(x-p1)) / (p2-p1).sqrnorm();
641  //std::cout << "\x1b[32mdelta = " << delta << "\x1b[0m" << std::endl;
642  if (delta <= 0) {
643  //std::cout << "\x1b[43mdelta <= 0\x1b[0m" << std::endl;
644  return p1;
645  } else if (delta >= 1) {
646  //std::cout << "\x1b[43mdelta >= 1\x1b[0m" << std::endl;
647  return p2;
648  } else if (delta != delta) { // p1 = p2 or x = p1
649  //std::cout << "\x1b[43mdelta != delta\x1b[0m" << std::endl;
650  return (x-p1).sqrnorm() < (x-p2).sqrnorm() ? p1 : p2;
651  } else {
652  //std::cout << "\x1b[43mdelta \\in [0, 1]\x1b[0m" << std::endl;
653  return (1 - delta) * p1 + delta * p2;
654  }
655 };
656 
657 template<typename Vector>
658 Vector closestPointTri(Vector p, Vector a, Vector b, Vector c) {
659  constexpr double thresh = 1e-8;
660 
661  const auto n = ((b - a) % (c - a)); // normalization unnecessary
662 
663  if ((b-a).sqrnorm() < thresh || (c-a).sqrnorm() < thresh || n.sqrnorm() < thresh) {
664  //std::cout << "\x1b[42mDegenerate case.\x1b[0m" << std::endl;
665  // Degenerate triangle. Find distance to longest segment.
666  std::array<ACG::Vec3d, 2> max_segment = {a, b};
667  double max_len = (b-a).sqrnorm();
668  if ((c-a).sqrnorm() > max_len)
669  max_segment = {a, c};
670  if ((c-b).sqrnorm() > max_len)
671  max_segment = {b, c};
672 
673  // closestPointLineSegment is stable, even if the segment is super short
674  return closestPointLineSegment(p, max_segment[0], max_segment[1]);
675  }
676 
677  const auto abd = Matrix3x3d::fromColumns(a-c, b-c, n).inverse() * (p - c);
678  const bool alpha = (abd[0] >= 0.0),
679  beta = (abd[1] >= 0.0),
680  gamma = (1.0-abd[0]-abd[1] >= 0.0);
681 
682  if (alpha && beta && gamma) {
683  //std::cout << "\x1b[42mInside case.\x1b[0m" << std::endl;
684  // Inside triangle.
685  return abd[0] * a + abd[1] * b + (1.0 - abd[0] - abd[1]) * c;
686  } else if (!alpha) {
687  //std::cout << "\x1b[42m!alpha case.\x1b[0m" << std::endl;
688  // Closest to line segment (b, c).
689  return closestPointLineSegment(p, b, c);
690  } else if (!beta) {
691  //std::cout << "\x1b[42m!beta case.\x1b[0m" << std::endl;
692  // Closest to line segment (a, c).
693  return closestPointLineSegment(p, a, c);
694  } else if (!gamma) {
695  //std::cout << "\x1b[42m!gamma case.\x1b[0m" << std::endl;
696  // Closest to line segment (a, b).
697  return closestPointLineSegment(p, a, b);
698  } else {
699  throw std::logic_error("This cannot happen.");
700  }
701 }
702 
703 //=============================================================================
704 } // namespace Geometry
705 } // namespace ACG
706 //=============================================================================
707 #if defined(INCLUDE_TEMPLATES) && !defined(GEO_ALGORITHMS_C)
708 #define GEO_ALGORITHMS_TEMPLATES
709 #include "Algorithms.cc"
710 #endif
711 //=============================================================================
712 #endif // GEO_ALGORITHMS_HH defined
713 //=============================================================================
714 
ACG::Geometry::minRadiusSquared
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)
Definition: Algorithms.cc:1100
ACG::Geometry::minRadius
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)
Definition: Algorithms.hh:528
ACG::Geometry::circumRadius
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)
Definition: Algorithms.hh:101
ACG
Namespace providing different geometric functions concerning angles.
Definition: DBSCANT.cc:51
ACG::Geometry::roundness
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
Definition: Algorithms.cc:1302
ACG::Geometry::distPointTriangleSquaredStable
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)
Definition: Algorithms.cc:476
ACG::Geometry::triangleIntersection
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.
Definition: Algorithms.cc:1317
ACG::Geometry::edgeConvexPolygonIntersection
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.
Definition: Algorithms.cc:182
ACG::Geometry::triangleAreaSquared
Vec::value_type triangleAreaSquared(const Vec &_v0, const Vec &_v1, const Vec &_v2)
return squared area of triangle (_v0, _v1, _v2)
Definition: Algorithms.cc:173
ACG::Geometry::projectToPlane
VectorT projectToPlane(const VectorT &_porigin, const VectorT &_pnormal, const VectorT &_point)
projects a point to a plane
Definition: Algorithms.cc:904
ACG::Geometry::circumCenter
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)
Definition: Algorithms.cc:916
ACG::Geometry::circumRadiusSquared
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)
Definition: Algorithms.cc:950
ACG::Geometry::isCW
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
Definition: Algorithms.hh:242
ACG::Geometry::distLineLineSquared
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)
Definition: Algorithms.cc:496
ACG::Geometry::rotationOfTwoVectors
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.
Definition: Algorithms.cc:973
ACG::Geometry::minSphere
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
Definition: Algorithms.cc:1040
ACG::Geometry::perpendicular
VectorT< Scalar, 3 > perpendicular(const VectorT< Scalar, 3 > &v)
find a vector that's perpendicular to _v
Definition: Algorithms.cc:1162
ACG::Geometry::distPointTriangle
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)
Definition: Algorithms.hh:335
ACG::Geometry::isObtuse
int isObtuse(const VectorT &_p0, const VectorT &_p1, const VectorT &_p2)
Definition: Algorithms.cc:1013
ACG::Geometry::pointLineOrientation
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
Definition: Algorithms.hh:219
ACG::Geometry::distPointPlane
ValueT distPointPlane(const VectorT &_porigin, const VectorT &_pnormal, const VectorT &_point)
Checks the distance from a point to a plane.
Definition: Algorithms.cc:872
ACG::Geometry::aspectRatio
Scalar aspectRatio(const VectorT< Scalar, N > &_v0, const VectorT< Scalar, N > &_v1, const VectorT< Scalar, N > &_v2)
return aspect ratio (length/height) of triangle
Definition: Algorithms.cc:1266
ACG::Geometry::triangleArea
Vec::value_type triangleArea(const Vec &_v0, const Vec &_v1, const Vec &_v2)
return area of triangle (_v0, _v1, _v2)
Definition: Algorithms.hh:604
ACG::Geometry::distLineLine
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)
Definition: Algorithms.hh:399
ACG::Geometry::axisAlignedBBIntersection
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.
Definition: Algorithms.cc:1367
ACG::Geometry::distPointLine
Vec::value_type distPointLine(const Vec &_p, const Vec &_v0, const Vec &_v1, Vec *_min_v=0)
Compute distance from point to line segment.
Definition: Algorithms.hh:297
ACG::Geometry::isInTriangle
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
Definition: Algorithms.hh:468
ACG::Geometry::distPointLineSquared
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)
Definition: Algorithms.cc:300
ACG::Geometry::baryCoord
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)
Definition: Algorithms.cc:93
ACG::Geometry::lineIntersection
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)
Definition: Algorithms.cc:1215
ACG::Geometry::distPointTriangleStable
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)
Definition: Algorithms.hh:354
ACG::Geometry::isCCW
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
Definition: Algorithms.hh:231
ACG::Geometry::projectToEdge
VectorT projectToEdge(const VectorT &_start, const VectorT &_end, const VectorT &_point)
Definition: Algorithms.cc:884