Algorithms.hh

00001 /*===========================================================================*\
00002  *                                                                           *
00003  *                              OpenFlipper                                  *
00004  *      Copyright (C) 2001-2009 by Computer Graphics Group, RWTH Aachen      *
00005  *                           www.openflipper.org                             *
00006  *                                                                           *
00007  *---------------------------------------------------------------------------*
00008  *  This file is part of OpenFlipper.                                        *
00009  *                                                                           *
00010  *  OpenFlipper is free software: you can redistribute it and/or modify      *
00011  *  it under the terms of the GNU Lesser General Public License as           *
00012  *  published by the Free Software Foundation, either version 3 of           *
00013  *  the License, or (at your option) any later version with the              *
00014  *  following exceptions:                                                    *
00015  *                                                                           *
00016  *  If other files instantiate templates or use macros                       *
00017  *  or inline functions from this file, or you compile this file and         *
00018  *  link it with other files to produce an executable, this file does        *
00019  *  not by itself cause the resulting executable to be covered by the        *
00020  *  GNU Lesser General Public License. This exception does not however       *
00021  *  invalidate any other reasons why the executable file might be            *
00022  *  covered by the GNU Lesser General Public License.                        *
00023  *                                                                           *
00024  *  OpenFlipper is distributed in the hope that it will be useful,           *
00025  *  but WITHOUT ANY WARRANTY; without even the implied warranty of           *
00026  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the            *
00027  *  GNU Lesser General Public License for more details.                      *
00028  *                                                                           *
00029  *  You should have received a copy of the GNU LesserGeneral Public          *
00030  *  License along with OpenFlipper. If not,                                  *
00031  *  see <http://www.gnu.org/licenses/>.                                      *
00032  *                                                                           *
00033 \*===========================================================================*/
00034 
00035 /*===========================================================================*\
00036  *                                                                           *
00037  *   $Revision: 8521 $                                                       *
00038  *   $Author: moebius $                                                      *
00039  *   $Date: 2010-02-10 15:57:35 +0100 (Mi, 10. Feb 2010) $                   *
00040  *                                                                           *
00041 \*===========================================================================*/
00042 
00043 
00044 
00045 
00046 #ifndef GEO_ALGORITHMS_HH
00047 #define GEO_ALGORITHMS_HH
00048 
00049 
00050 //== INCLUDES =================================================================
00051 
00052 #include <float.h>
00053 #include "../Math/VectorT.hh"
00054 
00055 
00056 namespace ACG {
00057 namespace Geometry {
00058 
00059 
00060 //== 3D STUFF =================================================================
00061 
00062   
00065 template<typename Scalar>
00066 bool
00067 baryCoord( const VectorT<Scalar,3>&  _p,
00068            const VectorT<Scalar,3>&  _u,
00069            const VectorT<Scalar,3>&  _v,
00070            const VectorT<Scalar,3>&  _w,
00071            VectorT<Scalar,3>&        _result );
00072 
00073 
00075 template <class Vec>
00076 typename Vec::value_type
00077 triangleArea( const Vec& _v0,
00078               const Vec& _v1,
00079               const Vec& _v2 )
00080 {
00081   return sqrt(triangleAreaSquared(_v0,_v1,_v2));
00082 }
00083   
00084 
00086 template <class Vec>
00087 typename Vec::value_type
00088 triangleAreaSquared( const Vec& _v0,
00089                      const Vec& _v1,
00090                      const Vec& _v2 );
00091 
00092 
00094 template<class Vec>
00095 typename Vec::value_type
00096 distPointLine( const Vec& _p,
00097                const Vec& _v0,
00098                const Vec& _v1,
00099                Vec*       _min_v=0 )
00100 { return sqrt(distPointLineSquared(_p, _v0, _v1, _min_v)); }
00101 
00102 
00104 template<class Vec>
00105 typename Vec::value_type
00106 distPointLineSquared( const Vec& _p,
00107                       const Vec& _v0,
00108                       const Vec& _v1,
00109                       Vec*       _min_v=0);
00110 
00112 template <class Vec>
00113 typename Vec::value_type
00114 distPointTriangle( const Vec& _p,
00115                    const Vec& _v0,
00116                    const Vec& _v1,
00117                    const Vec& _v2,
00118                    Vec& _nearestPoint )
00119 { return sqrt(distPointTriangleSquared(_p, _v0, _v1, _v2, _nearestPoint)); }
00120 
00121 
00123 template <class Vec>
00124 typename Vec::value_type
00125 distPointTriangleSquared( const Vec& _p,
00126                           const Vec& _v0,
00127                           const Vec& _v1,
00128                           const Vec& _v2,
00129                           Vec& _nearestPoint );
00130 
00131 
00133 template<typename Scalar>
00134 Scalar
00135 distLineLineSquared( const VectorT<Scalar,3>& _v00,
00136                      const VectorT<Scalar,3>& _v01,
00137                      const VectorT<Scalar,3>& _v10,
00138                      const VectorT<Scalar,3>& _v11,
00139                      VectorT<Scalar,3>*       _min_v0=0,
00140                      VectorT<Scalar,3>*       _min_v1=0,
00141                      bool                          _fastApprox=false );
00142 
00143 
00145 template<typename Scalar>
00146 Scalar
00147 distLineLine( const VectorT<Scalar,3>& _v00,
00148               const VectorT<Scalar,3>& _v01,
00149               const VectorT<Scalar,3>& _v10,
00150               const VectorT<Scalar,3>& _v11,
00151               VectorT<Scalar,3>*       _min_v0=0,
00152               VectorT<Scalar,3>*       _min_v1=0 )
00153 {
00154   return sqrt(distLineLineSquared(_v00, _v01, _v10, _v11,
00155                                   _min_v0, _min_v1));
00156 }
00157 
00158 
00160 template<typename Scalar>
00161 bool
00162 minSphere(const VectorT<Scalar,3>&  _v0,
00163           const VectorT<Scalar,3>&  _v1,
00164           const VectorT<Scalar,3>&  _v2,
00165           VectorT<Scalar,3>&        _center,
00166           Scalar&                   _radius);
00167 
00168 
00170 template<typename Scalar>
00171 Scalar
00172 minRadiusSquared( const VectorT<Scalar,3>&  _v0,
00173                   const VectorT<Scalar,3>&  _v1,
00174                   const VectorT<Scalar,3>&  _v2 );
00175 
00176   
00178 template<typename Scalar>
00179 Scalar
00180 minRadius( const VectorT<Scalar,3>&  _v0,
00181            const VectorT<Scalar,3>&  _v1,
00182            const VectorT<Scalar,3>&  _v2 )
00183 {
00184   return sqrt(minRadiusSquared(_v0, _v1, _v2));
00185 }
00186 
00187 
00189 template<typename Scalar>
00190 bool
00191 circumCenter( const VectorT<Scalar,3>&  _v0,
00192               const VectorT<Scalar,3>&  _v1,
00193               const VectorT<Scalar,3>&  _v2,
00194               VectorT<Scalar,3>&        _result );
00195 
00196 
00198 template<typename Scalar>
00199 Scalar
00200 circumRadiusSquared( const VectorT<Scalar,3>&  _v0,
00201                      const VectorT<Scalar,3>&  _v1,
00202                      const VectorT<Scalar,3>&  _v2 );
00203 
00204 
00206 template<typename Scalar>
00207 Scalar
00208 circumRadius( const VectorT<Scalar,3>&  _v0,
00209               const VectorT<Scalar,3>&  _v1,
00210               const VectorT<Scalar,3>&  _v2 )
00211 {
00212   return sqrt(circumRadiusSquared(_v0, _v1, _v2));
00213 }
00214 
00215 
00216 
00218 template<typename Scalar>
00219 bool
00220 circumCenter( const VectorT<Scalar,3>&  _v0,
00221               const VectorT<Scalar,3>&  _v1,
00222               const VectorT<Scalar,3>&  _v2,
00223               const VectorT<Scalar,3>&  _v3,
00224               VectorT<Scalar,3>&        _result );
00225 
00226 
00228 template<typename Scalar>
00229 Scalar
00230 circumRadiusSquared( const VectorT<Scalar,3>&  _v0,
00231                      const VectorT<Scalar,3>&  _v1,
00232                      const VectorT<Scalar,3>&  _v2,
00233                      const VectorT<Scalar,3>&  _v3 )
00234 {
00235   VectorT<Scalar,3> cc;
00236   return circumCenter(_v0, _v1, _v2, _v3, cc) ? (cc-_v0).sqrnorm() : FLT_MAX;
00237 }
00238 
00239 
00241 template<typename Scalar>
00242 Scalar
00243 circumRadius( const VectorT<Scalar,3>&  _v0,
00244               const VectorT<Scalar,3>&  _v1,
00245               const VectorT<Scalar,3>&  _v2,
00246               const VectorT<Scalar,3>&  _v3 )
00247 {
00248   return sqrt(circumRadiusSquared(_v0, _v1, _v2, _v3));
00249 }
00250 
00251 
00253 template <typename Scalar>
00254 VectorT<Scalar,3>
00255 perpendicular( const VectorT<Scalar,3>&  _v );
00256 
00257 
00258 
00259 //== 2D STUFF =================================================================
00260 
00261 
00262 
00264 template<typename Scalar>
00265 bool
00266 baryCoord( const VectorT<Scalar,2>&  _p,
00267            const VectorT<Scalar,2>&  _u,
00268            const VectorT<Scalar,2>&  _v,
00269            const VectorT<Scalar,2>&  _w,
00270            VectorT<Scalar,3>&        _result );
00271 
00272 
00274 template<typename Scalar>
00275 bool
00276 isInTriangle( const VectorT<Scalar,2>&  _p,
00277               const VectorT<Scalar,2>&  _u,
00278               const VectorT<Scalar,2>&  _v,
00279               const VectorT<Scalar,2>&  _w )
00280 {
00281   VectorT<Scalar,3> bary;
00282   if (baryCoord(_p, _u, _v, _w, bary)) 
00283     return ((bary[0]>0.0) && (bary[1]>0.0) && (bary[2]>0.0));
00284   else {
00285     std::cerr << "point in triangle error\n";
00286     return false;
00287   }
00288 }
00289 
00290 
00292 template<typename Scalar>
00293 Scalar
00294 pointLineOrientation( const VectorT<Scalar,2>&  _p,
00295                       const VectorT<Scalar,2>&  _v0,
00296                       const VectorT<Scalar,2>&  _v1 )
00297 {
00298   VectorT<Scalar,2> d1(_p-_v0), d2(_v1-_v0);
00299   return (d1[0]*d2[1]-d1[1]*d2[0]);
00300 }
00301 
00302 
00303 
00304 
00306 template<typename Scalar>
00307 bool
00308 isCCW( const VectorT<Scalar,2>&  _v0,
00309        const VectorT<Scalar,2>&  _v1,
00310        const VectorT<Scalar,2>&  _v2 )
00311 {
00312   return ( pointLineOrientation(_v0, _v1, _v2) < Scalar(0.0) );
00313 }
00314 
00315 
00317 template<typename Scalar>
00318 bool
00319 isCW( const VectorT<Scalar,2>&  _v0,
00320       const VectorT<Scalar,2>&  _v1,
00321       const VectorT<Scalar,2>&  _v2 )
00322 {
00323   return ( pointLineOrientation(_v0, _v1, _v2) > Scalar(0.0) );
00324 }
00325 
00326 
00328 template<typename Scalar>
00329 bool
00330 lineIntersection( const VectorT<Scalar,2>&  _v0,
00331                   const VectorT<Scalar,2>&  _v1,
00332                   const VectorT<Scalar,2>&  _v2,
00333                   const VectorT<Scalar,2>&  _v3,
00334                   Scalar& _t1,
00335                   Scalar& _t2 );
00336 
00337 
00339 template<typename Scalar>
00340 bool
00341 circumCenter( const VectorT<Scalar,2>&  _v0,
00342               const VectorT<Scalar,2>&  _v1,
00343               const VectorT<Scalar,2>&  _v2,
00344               VectorT<Scalar,2>&        _result );
00345 
00346 
00347 //== N-DIM STUFF ==============================================================
00348 
00349 
00351 template <typename Scalar, int N>
00352 Scalar
00353 aspectRatio( const VectorT<Scalar, N>& _v0,
00354              const VectorT<Scalar, N>& _v1,
00355              const VectorT<Scalar, N>& _v2 );
00356 
00358 template <typename Scalar, int N>
00359 Scalar
00360 roundness( const VectorT<Scalar, N>& _v0,
00361            const VectorT<Scalar, N>& _v1,
00362            const VectorT<Scalar, N>& _v2 );
00363 
00364 
00365 //=============================================================================
00366 } // namespace Geometry
00367 } // namespace ACG
00368 //=============================================================================
00369 #if defined(INCLUDE_TEMPLATES) && !defined(GEO_ALGORITHMS_C)
00370 #define GEO_ALGORITHMS_TEMPLATES
00371 #include "Algorithms.cc"
00372 #endif
00373 //=============================================================================
00374 #endif // GEO_ALGORITHMS_HH defined
00375 //=============================================================================
00376