Cette source fournit la mise en oeuvre d'un algorithme pour le calcul de l'enveloppe convexe d'un nuage de points dans le plan.
L'algorithme utilisé est celui decrit dans le cours d'algorithmie de Gerard Berry du College de France, dont la video est disponible à l'adresse suivante :
http://www.college-de-france.fr/default/EN/all/inn_tec2007/cours_n1_les_algorithmes.htm
Ce lien a été fourni par coucou747 lors d'une discussion sur le forum à l'endroit suivant :
http://www.cppfrance.com/forum/sujet-CALCULER-ENVELOPPE-CONVEXE-NUAGE-POINT-CPLUSPLUS_1241680.aspx
Source / Exemple :
/*_________________________________________________________________________________________
#include <iostream>
#include <fstream>
#include <list>
#include <vector>
#include <ctime>
#include <cmath>
/*_________________________________________________________________________________________
struct point
{
double _x ;
double _y ;
};
/*_________________________________________________________________________________________
- //*!
- predicat qui de deux points renvoie le plus bas
- /
bool le_plus_bas( const point & a , const point & b )
{
return a._y < b._y ;
}
/*_________________________________________________________________________________________
- //*!
- foncteur qui permet de classer deux points suivant l'angle entre l'axe des x et le vecteur
- forme par chacun des points et un p donne.
- /
class sens_trigo
{
private:
point _p ;
public:
sens_trigo( const point & p )
:_p( p )
{}
bool operator()( const point & a , const point & b )
{
double tta_a = atan2( a._y - _p._y , a._x - _p._x ) ;
double tta_b = atan2( b._y - _p._y , b._x - _p._x ) ;
return tta_a > tta_b ;
}
};
/*_________________________________________________________________________________________
- //*!
- droite construite a partir de deux points
- dont l'equation est de la forme ax + by + c = 0
- /
class droite
{
private:
double _a ;
double _b ;
double _c ;
public:
droite( const point & p1 , const point & p2 )
:_a( p2._y - p1._y )
,_b( -p2._x + p1._x )
,_c( p1._y * p2._x - p1._x * p2._y )
{}
/*!
- Renvoie true si p1 et p2 sont du meme cote de la droite,
- c'est-a-dire si le signe de ax + by + c pour chacun des points est le meme
- /
bool meme_cote( const point & p1 , const point & p2 )
{
return ( _a * p1._x + _b * p1._y + _c ) * ( _a * p2._x + _b * p2._y + _c ) > 0 ;
}
};
/*_________________________________________________________________________________________
- //*!
- algorithme de calcul de l'enveloppe
- /
std::vector< point > enveloppe( std::list< point > nuage )
{
//Recherche du point le plus bas
nuage.sort( le_plus_bas ) ;
point bas = nuage.front() ;
nuage.pop_front();
//Tri du reste du nuage en fonction des angles par rapport au point le plus bas
nuage.sort( sens_trigo( bas ) ) ;
//On place le point le plus bas dans l'enveloppe
std::vector< point > env ;
env.push_back( bas ) ;
//On replace egalement le point le plus bas a la fin du nuage
nuage.push_back( bas ) ;
//Tant qu'il y a des points dans le nuage...
while ( !nuage.empty() )
{
//On retire le premier point du nuage et on le place dans l'enveloppe
env.push_back( nuage.front() ) ;
nuage.pop_front() ;
//Tant qu'il y a au moins 4 points dans l'enveloppe...
while ( env.size() >= 4 )
{
size_t n = env.size() - 1 ;
const point & b = env[ n ] ;
const point & p2 = env[ n - 1 ] ;
const point & p1 = env[ n - 2 ] ;
const point & a = env[ n - 3 ] ;
//Si les points a et b sont du meme cote que la droite passant par p1 et p2
if ( ! droite( p1 , p2 ).meme_cote( a , b ) )
{
env.erase( env.begin() + n - 1 ) ;
}
else
{
//sinon on quitte la boucle
break ;
}
}
}
return env ;
}
/*_________________________________________________________________________________________
- //*!
- programme illustrant l'utilisation de l'algorithme
- /
int main()
{
//generation d'un nuage de points
srand( (unsigned int) time( 0 ) ) ;
std::list< point > nuage( 100 ) ;
{
std::list< point >::iterator it ;
for ( it = nuage.begin() ; it != nuage.end() ; ++it )
{
it->_x = rand() % 1000 ;
it->_y = rand() % 1000 ;
}
}
//enregistrement du nuage dans un fichier csv
{
std::ofstream ofs( "nuage.csv" ) ;
std::list< point >::iterator it ;
for ( it = nuage.begin() ; it != nuage.end() ; ++it )
{
ofs << it->_x << ";" << it->_y << std::endl ;
}
ofs.close() ;
}
//execution de l'algorithme
std::vector< point > env = enveloppe( nuage ) ;
//enregistrement de l'enveloppe dans un fichier csv
{
std::ofstream ofs( "enveloppe.csv" ) ;
std::vector< point >::iterator it ;
for ( it = env.begin() ; it != env.end() ; ++it )
{
ofs << it->_x << ";" << it->_y << std::endl ;
}
ofs.close() ;
}
}
/*_________________________________________________________________________________________
Conclusion :
Vos suggestions, remarques, et questions sont les bienvenues !
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.