Calcul de l'enveloppe convexe d'un nuage de points dans un plan

Soyez le premier à donner votre avis sur cette source.

Snippet vu 11 943 fois - Téléchargée 20 fois

Contenu du snippet

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> /*_________________________________________________________________________________________
  • //*!
  • structure de base
  • /
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 !

A voir également

Ajouter un commentaire Commentaires
Messages postés
180
Date d'inscription
mercredi 22 décembre 2004
Statut
Membre
Dernière intervention
16 août 2012
2
Pistol_Pete , merci pour ta note. Je vais essayer de dégager un peu de temps pour prendre en compte tes deux excellentes suggestions.
Messages postés
1054
Date d'inscription
samedi 2 octobre 2004
Statut
Membre
Dernière intervention
9 juillet 2013
6
Effectivement, j'ai testé l'algo et il est bien en n log(n). Il s'agit en fait de l'algo de Graham.

C'est un très bon algorithme mais c'est peu être pas le meilleur. Matlab implémente le Quick Hull par exemple. Le principe est très attractif et je pense que tu peux amélioré la vitesse de ton algo avec cette méthode.

Le principe: tu calcules les 4 points extrémaux de ton nuage de point (le point le plus à gauche, le plus à droite ,le plus en haut, et le plus en bas). Il forment donc un quadrilatère. Et tu supprimes tous les points qui sont dans ce quadrilatère par ce que tu es sure qu'ils ne font pas partie de l'enveloppe convexe.

Là tu as déjà supprimé une bonne partie des points...
Il doit y avoir beaucoup de doc sur cet algo.

Très bonne source 9/10. Je pense que tu aurais pu faire une petite interface graphique. Cela aurait été plus ludique.
A+
Messages postés
180
Date d'inscription
mercredi 22 décembre 2004
Statut
Membre
Dernière intervention
16 août 2012
2
Damned ! J'avais oublié le tri !
Merci pour le lien PGL10.
Messages postés
326
Date d'inscription
samedi 18 décembre 2004
Statut
Membre
Dernière intervention
5 janvier 2021
2
Messages postés
326
Date d'inscription
samedi 18 décembre 2004
Statut
Membre
Dernière intervention
5 janvier 2021
2
Le cours de Gérard Berry identifie une partie en o(nlogn) et deux autres en o(n). Globalement cet algorithme est donc bien en o(nlogn) comme signalé. Mais c'est déjà bien !
Afficher les 9 commentaires

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.