Accueil > > > CALCUL DE L'ENVELOPPE CONVEXE D'UN NUAGE DE POINTS DANS UN PLAN
CALCUL DE L'ENVELOPPE CONVEXE D'UN NUAGE DE POINTS DANS UN PLAN
Information sur la source
Description
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-E NVELOPPE-CONVEXE-NUAGE-POINT-CPLUSPLUS_1241680.asp x
Source
- /*_________________________________________________________________________________________
- */
- #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() ;
- }
- }
- /*_________________________________________________________________________________________
- */
/*_________________________________________________________________________________________
*/
#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 !
Historique
- 14 décembre 2008 21:34:01 :
- ajout snapshot
- 15 décembre 2008 19:38:21 :
- mise à jour du lien de la video
Sources de la même categorie
Commentaires et avis
Discussions en rapport avec ce code source dans le forum
Erreur: invalid use of `this' in non-member function & `int' is not an aggregate type [ par GrosTony ]
Bonjour,J'ai un problème avec une Classe C++, voici le tracé des erreurs :$ makeg++ -c -O4 -W -g -Wall -o Nuage.o Nuage.cppNuage.cpp:4: ISO
enveloppe convexe sous matlab [ par leo2bordo ]
Bonjour, J'ai fait un programme qui crée un nuage de points, ensuite trace la triangulation de Delaunay a ce nuage de points, dessine l'enveloppe conv
calculer une enveloppe convexe d'un nuage de point en c++ [ par fantome2040 ]
Bonjour Comme il est ecrit dans le sujet je cherche un programme en C++ qui me permetrai de calculer une enveloppe convexe d'un nuage de point. Je
GROS PROPLEMES POUR FAIRE RECONNAITRE UNE CLASSE DANS VISUALC++ 2008 Express [ par marius72 ]
Bonsoir,ce message remplace celui que j'ai écrit précédemment,je vais écrire ma demande de façon plus concise et précise :je suis développeur de longu
Aide pour un algorithme [ par ashlee14 ]
Bonjour, etant débutante en C je voudrais savoir si quelqu'un peut me dire les étapes que je dois faire pour réaliser l'algorithme suivant. Le but de
Probleme d'inclusion de fichier (.hpp Vs .cpp)? [ par ano2345 ]
Bonjour a tous,Je suis en train de developper sous Dev-C++ 4.9.9.2 une classe template MyVector basee sur la classe vector de telle maniere que je pui
l'algorithme de trémaux [ par tchesa17 ]
salut,je cherche un programme de l'algorithme de trémaux en c++, et merci de votre aide d'avance.
Compilation + teste [ par nidhaletec ]
je cherche a compiler cette bibliotheque: '' http://trac.openstreetmap.org/browser/applications/lib/libosm " et puis tester les programmes test1.cpp,
Dev-Cpp [ par marcotte ]
Bonjour à tous(tes)Comme débutant, j'avais laissé tombé la programmation C/C++ depuis 2000 (je crois ?) et je voulais m'y remettre avec Dev-Cpp mais l
ALGORITHME DE CLARKE AND WRIGHT [ par maynot09 ]
bonjour, Je suis à la recherche du code ou l'algorithme de Clarke and wright proposé pour le problème du tournées de véhicules avec flotte hétérogéne
|
Derniers Blogs
UNE JOLIE-HORLOGE ET PAS QU'UN PEU !UNE JOLIE-HORLOGE ET PAS QU'UN PEU ! par neodante
Pour les possesseurs d'iPhone, ça y est Bijin Tokei - qui se traduit littéralement en Français par " Jolie Horloge " - est arrivé et GRATUITEMENT s'il vous plaît ! Après la version Tokyo, Hokkaido, night club, racing, Gal, "pour les mademoiselles'", . voi...
Cliquez pour lire la suite de l'article par neodante TECHDAYS PARIS 2010 : CONNECTEZ VOS DONNéES à SHAREPOINT 2010 AVEC LES BUSINESS CONNECTIVITY SERVICESTECHDAYS PARIS 2010 : CONNECTEZ VOS DONNéES à SHAREPOINT 2010 AVEC LES BUSINESS CONNECTIVITY SERVICES par ROMELARD Fabrice
Animé par: Gaetan Bouveret et Julien Chomarat Business Connectivity Services (BCS) est dans SharePoint 2010 la version 2 de Business Data Catalog (BDC dans SharePoint 2007). Il s'agit de la solution permettant de visualiser des données provenan...
Cliquez pour lire la suite de l'article par ROMELARD Fabrice [DIVERS] SUIVRE VOS SéRIES PRéFéRéS SUR LA TOILE[DIVERS] SUIVRE VOS SéRIES PRéFéRéS SUR LA TOILE par orion
Comme de nombreux geek, je suis un grand amateur de série TV et je rate régulièrement des épisodes de mes séries préférés. Une solution s'offre à vous avec ce merveilleux site : Tv Gorge - www.tvgorge.com Moteur de recherche à l'appui, vous pouvez ...
Cliquez pour lire la suite de l'article par orion TECHDAYS PARIS 2010 : LA BI DANS SHAREPOINT 2010TECHDAYS PARIS 2010 : LA BI DANS SHAREPOINT 2010 par ROMELARD Fabrice
Animé par: Vincent Bellet et Baptiste Giraudier La BI dans SharePoint 2010, Les nouveaux services d'application dans SP2010 et SQL Server Reporting services 2008 R2. La BI dans SharePoint est généralisée pour tous afin de permettre à tous les coll...
Cliquez pour lire la suite de l'article par ROMELARD Fabrice
Forum
RE : WIN APIRE : WIN API par racpp
Cliquez pour lire la suite par racpp WIN APIWIN API par omarino_007
Cliquez pour lire la suite par omarino_007
Logiciels
DB-MAIN (9.1.0)DB-MAIN (9.1.0)DB-MAIN is a data-modeling and data-architecture tool. It is designed to help developers and anal... Cliquez pour télécharger DB-MAIN Xilisoft DPG Convertisseur (5.1.37.0120)XILISOFT DPG CONVERTISSEUR (5.1.37.0120)Xilisoft DPG Convertisseur offre aux fans de Nintendo DS une bonne solution leur permettant de dé... Cliquez pour télécharger Xilisoft DPG Convertisseur GraphicsGale (2.01.01)GRAPHICSGALE (2.01.01)GraphicsGale est un logiciel de PixelArt avec de nombreuse fonctionnalités permettant de réalisé ... Cliquez pour télécharger GraphicsGale Architecte 3D (Platinum 2010)ARCHITECTE 3D (PLATINUM 2010)Architecte 3D Platinium vous permet de concevoir facilement les plans votre future maison, de l'é... Cliquez pour télécharger Architecte 3D TeamViewer 5 (TeamViewer 5)TEAMVIEWER 5 (TEAMVIEWER 5)Dépanner un ami,expliquer une manipulation devient un jeu d'enfant.
Prise en main d'un autre ord... Cliquez pour télécharger TeamViewer 5
|