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-2014 by Computer Graphics Group, RWTH Aachen *
5  * www.openflipper.org *
6  * *
7  *---------------------------------------------------------------------------*
8  * This file is part of OpenFlipper. *
9  * *
10  * OpenFlipper is free software: you can redistribute it and/or modify *
11  * it under the terms of the GNU Lesser General Public License as *
12  * published by the Free Software Foundation, either version 3 of *
13  * the License, or (at your option) any later version with the *
14  * following exceptions: *
15  * *
16  * If other files instantiate templates or use macros *
17  * or inline functions from this file, or you compile this file and *
18  * link it with other files to produce an executable, this file does *
19  * not by itself cause the resulting executable to be covered by the *
20  * GNU Lesser General Public License. This exception does not however *
21  * invalidate any other reasons why the executable file might be *
22  * covered by the GNU Lesser General Public License. *
23  * *
24  * OpenFlipper is distributed in the hope that it will be useful, *
25  * but WITHOUT ANY WARRANTY; without even the implied warranty of *
26  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
27  * GNU Lesser General Public License for more details. *
28  * *
29  * You should have received a copy of the GNU LesserGeneral Public *
30  * License along with OpenFlipper. If not, *
31  * see <http://www.gnu.org/licenses/>. *
32  * *
33 \*===========================================================================*/
34 
35 /*===========================================================================*\
36  * *
37  * $Revision: 18584 $ *
38  * $Author: moebius $ *
39  * $Date: 2014-05-02 14:42:36 +0200 (Fri, 02 May 2014) $ *
40  * *
41 \*===========================================================================*/
42 
43 
44 
45 
46 #ifndef GEO_ALGORITHMS_HH
47 #define GEO_ALGORITHMS_HH
48 
49 
50 //== INCLUDES =================================================================
51 
52 #include <cfloat>
53 #include <ACG/Math/VectorT.hh>
54 #include <vector>
55 
56 
57 namespace ACG {
58 namespace Geometry {
59 
60 
61 //== 3D STUFF =================================================================
62 
63 
64 
66 template<typename Scalar>
67 bool
69  const VectorT<Scalar,3>& _v1,
70  const VectorT<Scalar,3>& _v2,
71  const VectorT<Scalar,3>& _v3,
72  VectorT<Scalar,3>& _result );
73 
74 
76 template<typename Scalar>
77 Scalar
79  const VectorT<Scalar,3>& _v1,
80  const VectorT<Scalar,3>& _v2,
81  const VectorT<Scalar,3>& _v3 )
82 {
84  return circumCenter(_v0, _v1, _v2, _v3, cc) ? (cc-_v0).sqrnorm() : FLT_MAX;
85 }
86 
87 
89 template<typename Scalar>
90 Scalar
92  const VectorT<Scalar,3>& _v1,
93  const VectorT<Scalar,3>& _v2,
94  const VectorT<Scalar,3>& _v3 )
95 {
96  return sqrt(circumRadiusSquared(_v0, _v1, _v2, _v3));
97 }
98 
111 template<typename Scalar>
112 bool edgeConvexPolygonIntersection(std::vector<VectorT<Scalar,3> > _polygon_points,
113  VectorT<Scalar,3> _v0,
114  VectorT<Scalar,3> _v1,
115  VectorT<Scalar,3> &_result);
116 
117 
132 template<typename Scalar>
133 bool
135  const VectorT<Scalar,3>& _v1,
136  VectorT<Scalar,3>& _axis,
137  Scalar& _angle,
138  bool _degree = true);
139 
140 
149 template <typename Scalar>
151 perpendicular( const VectorT<Scalar,3>& _v );
152 
153 
170 template<typename Vec>
171 bool
172 triangleIntersection( const Vec& _o,
173  const Vec& _dir,
174  const Vec& _v0,
175  const Vec& _v1,
176  const Vec& _v2,
177  typename Vec::value_type& _t,
178  typename Vec::value_type& _u,
179  typename Vec::value_type& _v );
180 
181 
194 template<typename Vec>
195 bool
196 axisAlignedBBIntersection( const Vec& _o,
197  const Vec& _dir,
198  const Vec& _bbmin,
199  const Vec& _bbmax,
200  typename Vec::value_type& _t0,
201  typename Vec::value_type& _t1 );
202 
203 
204 //== 2D STUFF =================================================================
205 
207 template<typename Scalar>
208 Scalar
209 pointLineOrientation( const VectorT<Scalar,2>& _p,
210  const VectorT<Scalar,2>& _v0,
211  const VectorT<Scalar,2>& _v1 )
212 {
213  VectorT<Scalar,2> d1(_p-_v0), d2(_v1-_v0);
214  return (d1[0]*d2[1]-d1[1]*d2[0]);
215 }
216 
217 
219 template<typename Scalar>
220 bool
221 isCCW( const VectorT<Scalar,2>& _v0,
222  const VectorT<Scalar,2>& _v1,
223  const VectorT<Scalar,2>& _v2 )
224 {
225  return ( pointLineOrientation(_v0, _v1, _v2) < Scalar(0.0) );
226 }
227 
228 
230 template<typename Scalar>
231 bool
232 isCW( const VectorT<Scalar,2>& _v0,
233  const VectorT<Scalar,2>& _v1,
234  const VectorT<Scalar,2>& _v2 )
235 {
236  return ( pointLineOrientation(_v0, _v1, _v2) > Scalar(0.0) );
237 }
238 
239 
241 template<typename Scalar>
242 bool
243 lineIntersection( const VectorT<Scalar,2>& _v0,
244  const VectorT<Scalar,2>& _v1,
245  const VectorT<Scalar,2>& _v2,
246  const VectorT<Scalar,2>& _v3,
247  Scalar& _t1,
248  Scalar& _t2 );
249 
250 
251 //===========================================================================
254 //===========================================================================
255 
256 
265 template<class Vec>
266 typename Vec::value_type
267 distPointLineSquared( const Vec& _p,
268  const Vec& _v0,
269  const Vec& _v1,
270  Vec* _min_v=0);
271 
272 
273 
285 template<class Vec>
286 typename Vec::value_type
287 distPointLine( const Vec& _p,
288  const Vec& _v0,
289  const Vec& _v1,
290  Vec* _min_v=0 )
291 { return sqrt(distPointLineSquared(_p, _v0, _v1, _min_v)); }
292 
293 
295 template <class Vec>
296 typename Vec::value_type
297 distPointTriangleSquared( const Vec& _p,
298  const Vec& _v0,
299  const Vec& _v1,
300  const Vec& _v2,
301  Vec& _nearestPoint );
302 
304 template <class Vec>
305 typename Vec::value_type
306 distPointTriangle( const Vec& _p,
307  const Vec& _v0,
308  const Vec& _v1,
309  const Vec& _v2,
310  Vec& _nearestPoint )
311 { return sqrt(distPointTriangleSquared(_p, _v0, _v1, _v2, _nearestPoint)); }
312 
321 template < typename VectorT , typename ValueT >
322 inline
323 ValueT
324 distPointPlane(const VectorT& _porigin,
325  const VectorT& _pnormal,
326  const VectorT& _point);
327 
328 
331 //===========================================================================
334 //===========================================================================
335 
337 template<typename Scalar>
338 Scalar
340  const VectorT<Scalar,3>& _v01,
341  const VectorT<Scalar,3>& _v10,
342  const VectorT<Scalar,3>& _v11,
343  VectorT<Scalar,3>* _min_v0=0,
344  VectorT<Scalar,3>* _min_v1=0,
345  bool _fastApprox=false );
346 
347 
349 template<typename Scalar>
350 Scalar
352  const VectorT<Scalar,3>& _v01,
353  const VectorT<Scalar,3>& _v10,
354  const VectorT<Scalar,3>& _v11,
355  VectorT<Scalar,3>* _min_v0=0,
356  VectorT<Scalar,3>* _min_v1=0 )
357 {
358  return sqrt(distLineLineSquared(_v00, _v01, _v10, _v11,
359  _min_v0, _min_v1));
360 }
361 
365 //===========================================================================
368 //===========================================================================
369 
370 
377 template < typename VectorT >
378 VectorT projectToEdge(const VectorT& _start ,
379  const VectorT& _end ,
380  const VectorT& _point );
381 
382 
389 template < typename VectorT >
390 inline
391 VectorT
392 projectToPlane(const VectorT& _porigin,
393  const VectorT& _pnormal,
394  const VectorT& _point);
395 
398 //===========================================================================
401 //===========================================================================
402 
407 template<typename Scalar>
409 bool
410 baryCoord( const VectorT<Scalar,2>& _p,
411  const VectorT<Scalar,2>& _u,
412  const VectorT<Scalar,2>& _v,
413  const VectorT<Scalar,2>& _w,
414  VectorT<Scalar,3>& _result );
415 
416 
418 template<typename Scalar>
419 bool
420 isInTriangle( const VectorT<Scalar,2>& _p,
421  const VectorT<Scalar,2>& _u,
422  const VectorT<Scalar,2>& _v,
423  const VectorT<Scalar,2>& _w )
424 {
425  VectorT<Scalar,3> bary;
426  if (baryCoord(_p, _u, _v, _w, bary))
427  return ((bary[0]>0.0) && (bary[1]>0.0) && (bary[2]>0.0));
428  else {
429  std::cerr << "point in triangle error\n";
430  return false;
431  }
432 }
433 
434 template<typename Scalar>
435 bool
436 circumCenter( const VectorT<Scalar,2>& _v0,
437  const VectorT<Scalar,2>& _v1,
438  const VectorT<Scalar,2>& _v2,
439  VectorT<Scalar,2>& _result );
440 
443 //===========================================================================
446 //===========================================================================
447 
450 template<typename Scalar>
451 bool
452 baryCoord( const VectorT<Scalar,3>& _p,
453  const VectorT<Scalar,3>& _u,
454  const VectorT<Scalar,3>& _v,
455  const VectorT<Scalar,3>& _w,
456  VectorT<Scalar,3>& _result );
457 
458 
460 template<typename Scalar>
461 bool
462 minSphere(const VectorT<Scalar,3>& _v0,
463  const VectorT<Scalar,3>& _v1,
464  const VectorT<Scalar,3>& _v2,
465  VectorT<Scalar,3>& _center,
466  Scalar& _radius);
467 
468 
470 template<typename Scalar>
471 Scalar
473  const VectorT<Scalar,3>& _v1,
474  const VectorT<Scalar,3>& _v2 );
475 
476 
478 template<typename Scalar>
479 Scalar
481  const VectorT<Scalar,3>& _v1,
482  const VectorT<Scalar,3>& _v2 )
483 {
484  return sqrt(minRadiusSquared(_v0, _v1, _v2));
485 }
486 
487 
489 template<typename Scalar>
490 bool
491 circumCenter( const VectorT<Scalar,3>& _v0,
492  const VectorT<Scalar,3>& _v1,
493  const VectorT<Scalar,3>& _v2,
494  VectorT<Scalar,3>& _result );
495 
496 
498 template<typename Scalar>
499 Scalar
501  const VectorT<Scalar,3>& _v1,
502  const VectorT<Scalar,3>& _v2 );
503 
504 
506 template<typename Scalar>
507 Scalar
509  const VectorT<Scalar,3>& _v1,
510  const VectorT<Scalar,3>& _v2 )
511 {
512  return sqrt(circumRadiusSquared(_v0, _v1, _v2));
513 }
514 
522 template<class VectorT>
523 int isObtuse(const VectorT& _p0,
524  const VectorT& _p1,
525  const VectorT& _p2 );
526 
529 //===========================================================================
532 //===========================================================================
533 
534 
538 template <class Vec>
539 typename Vec::value_type
540 triangleAreaSquared( const Vec& _v0,
541  const Vec& _v1,
542  const Vec& _v2 );
543 
544 
548 template <class Vec>
549 typename Vec::value_type
550 triangleArea( const Vec& _v0,
551  const Vec& _v1,
552  const Vec& _v2 )
553 {
554  return sqrt(triangleAreaSquared(_v0,_v1,_v2));
555 }
556 
557 
561 template <typename Scalar, int N>
562 Scalar
563 aspectRatio( const VectorT<Scalar, N>& _v0,
564  const VectorT<Scalar, N>& _v1,
565  const VectorT<Scalar, N>& _v2 );
566 
570 template <typename Scalar, int N>
571 Scalar
572 roundness( const VectorT<Scalar, N>& _v0,
573  const VectorT<Scalar, N>& _v1,
574  const VectorT<Scalar, N>& _v2 );
575 
578 //=============================================================================
579 } // namespace Geometry
580 } // namespace ACG
581 //=============================================================================
582 #if defined(INCLUDE_TEMPLATES) && !defined(GEO_ALGORITHMS_C)
583 #define GEO_ALGORITHMS_TEMPLATES
584 #include "Algorithms.cc"
585 #endif
586 //=============================================================================
587 #endif // GEO_ALGORITHMS_HH defined
588 //=============================================================================
589 
Vec::value_type triangleAreaSquared(const Vec &_v0, const Vec &_v1, const Vec &_v2)
return squared area of triangle (_v0, _v1, _v2)
Definition: Algorithms.cc:167
VectorT projectToEdge(const VectorT &_start, const VectorT &_end, const VectorT &_point)
Definition: Algorithms.cc:833
Vec::value_type distPointTriangleSquared(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:314
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:306
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:1215
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:1266
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:1164
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:865
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:87
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:1316
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:232
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:899
VectorT< Scalar, 3 > perpendicular(const VectorT< Scalar, 3 > &v)
find a vector that's perpendicular to _v
Definition: Algorithms.cc:1111
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:1251
VectorT projectToPlane(const VectorT &_porigin, const VectorT &_pnormal, const VectorT &_point)
projects a point to a plane
Definition: Algorithms.cc:853
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:176
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:351
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:922
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:221
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:91
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:480
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:209
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:287
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:294
int isObtuse(const VectorT &_p0, const VectorT &_p1, const VectorT &_p2)
Definition: Algorithms.cc:962
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:1049
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:420
Vec::value_type triangleArea(const Vec &_v0, const Vec &_v1, const Vec &_v2)
return area of triangle (_v0, _v1, _v2)
Definition: Algorithms.hh:550
Namespace providing different geometric functions concerning angles.
Definition: DBSCANT.cc:10
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:989
ValueT distPointPlane(const VectorT &_porigin, const VectorT &_pnormal, const VectorT &_point)
Checks the distance from a point to a plane.
Definition: Algorithms.cc:821
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:445