1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170
| /*_________________________________________________________________________________________
*/
#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() ;
}
}
/*_________________________________________________________________________________________
*/ |
Partager