Algorithme pour la detection des points extrêmes dans un nuage de points

Version imprimable

15/02/2010, 16h28
bazungula

Algorithme pour la detection des points extrêmes dans un nuage de points

Salut tout le monde,

J'ai un fichier qui contient les points en coordonnées XY. Ces points constituent un nuages de points.

Je voudrai trouver un moyen simple de lire uniquement les points extrêmes ou périphériques de ce nuage de points pour en créer le contour (périmètre).

J'ai essayé plusieurs algorithmes mais je n'arrive pas. Y a t-il quelqu'un qui sait comment on peut faire ça en C++ ?
J'ai surtout besoin d'un algorithme facile à implémenter sur C++.

MERCI BEAUCOUP POUR VOTRE AIDE
15/02/2010, 16h38
gbdivers

Bonjour

Tu peux regarder la bibliothèque CGAL qui propose plusieurs implémentations d'algorithmes d'enveloppe convexe.
http://www.cgal.org/Manual/last/doc_...pter_main.html
16/02/2010, 09h30
3DArchi

Bonjour,
Méthode des contours actifs, par Pierre Schwartz peut-il être une réponse à ton problème ?
18/02/2010, 14h18
bazungula

Citation:

Envoyé par gbdivers

Bonjour

Tu peux regarder la bibliothèque CGAL qui propose plusieurs implémentations d'algorithmes d'enveloppe convexe.
http://www.cgal.org/Manual/last/doc_...pter_main.html

Salut, Merci pour cette réponse que je suis en train d'étudier. Je la compare avec celle des "contours actifs"

Je vous tiens au courant......
18/02/2010, 14h20
bazungula

Citation:

Envoyé par 3DArchi

Bonjour,
Méthode des contours actifs, par Pierre Schwartz peut-il être une réponse à ton problème ?

Salut, cette théorie me semble géniale mais il faut que je comprenne les notions d'énergies internes et externes :calim2:

Je vous tiens au courant
18/02/2010, 15h55
Luc Hermitte

Je doute qu'elle te soit utile: elle sert à trouver les countours d'images.
Or toi, tu as un nuage de points, et la description donnée me fait aussi penser à un problème de recherche de la plus petite enveloppe convexe.

Au pif je dirais:
1- trouver le barycentre
2- trouver le point le plus éloigné
3- classer tous les points par ordre trigo en partant du plus éloigné
4- parcourrir ces points dans l'ordre et écarter ceux qui brisent la convexité (ce qui peut demander un petit retour arrière)

Ce qui m'a l'air de tenir en N ln N. (1:N, 2:N, 3: N ln N, 4:2xN max)
18/02/2010, 16h04
Invité

Si tu lis l'anglais... Regarde ceci (ton "périmètre" s'appelle enveloppe convexe, convex hull en anglais),

http://en.wikipedia.org/wiki/Convex_hull_algorithms

Si tu n'as pas trop de points ou si c'est un "vrai nuage" (la plupart des points sont intérieurs à l'enveloppe), il faut utiliser l'algorithme de Jarvis, en 2D, c'est très facile à faire, et c'est O(nh) ou h est le nombre de supports sur l'enveloppe.

http://en.wikipedia.org/wiki/Gift_wrapping_algorithm

Si tu veux faire le malin, tu prends Graham, un peu plus complexe, meilleures garanties pour les cas tordus (quand presque tous tes points sont sur l'enveloppe).
http://en.wikipedia.org/wiki/Graham_scan

Les choses plus compliquées, c'est surtout en plus grande dimension, ou pour des nombres de points gigantesques.

Francois
23/02/2010, 11h47
bazungula

Citation:

Envoyé par Luc Hermitte

Je doute qu'elle te soit utile: elle sert à trouver les countours d'images.
Or toi, tu as un nuage de points, et la description donnée me fait aussi penser à un problème de recherche de la plus petite enveloppe convexe.

Au pif je dirais:
1- trouver le barycentre
2- trouver le point le plus éloigné
3- classer tous les points par ordre trigo en partant du plus éloigné
4- parcourrir ces points dans l'ordre et écarter ceux qui brisent la convexité (ce qui peut demander un petit retour arrière)

Ce qui m'a l'air de tenir en N ln N. (1:N, 2:N, 3: N ln N, 4:2xN max)

Merci pour ta réponse,
Tu as raison, cet algorithme (ci-dessus) ne me convient pas car elle correspond à un traitement d'image.

Je suis en train de tester ton algo mais à la place de classer les points par ordre trigonométrique en partant du plus éloigné, je préfère:
- calculer les pentes de ces points par rapport au Barycentre.
- Dans le 1er quadrant, le point le plus éloigné ayant la plus pente est dans le contour, ainsi de suite
- Faire de même dans le 2éme, 3ème et 4ème quadrant.

A +
23/02/2010, 11h50
bazungula

Citation:

Envoyé par fcharton

Si tu lis l'anglais... Regarde ceci (ton "périmètre" s'appelle enveloppe convexe, convex hull en anglais),

http://en.wikipedia.org/wiki/Convex_hull_algorithms

Si tu n'as pas trop de points ou si c'est un "vrai nuage" (la plupart des points sont intérieurs à l'enveloppe), il faut utiliser l'algorithme de Jarvis, en 2D, c'est très facile à faire, et c'est O(nh) ou h est le nombre de supports sur l'enveloppe.

http://en.wikipedia.org/wiki/Gift_wrapping_algorithm

Si tu veux faire le malin, tu prends Graham, un peu plus complexe, meilleures garanties pour les cas tordus (quand presque tous tes points sont sur l'enveloppe).
http://en.wikipedia.org/wiki/Graham_scan

Les choses plus compliquées, c'est surtout en plus grande dimension, ou pour des nombres de points gigantesques.

Francois

Merci pour tes propositions,

tes algorithmes me semblent un trop lourd à implémenter.
Je ne sais combien de temps, peuvent prendre leurs calculs. Mais c'est à essayer......
26/02/2010, 17h04
akirira

Citation:

Envoyé par bazungula

J'ai un fichier qui contient les points en coordonnées XY. Ces points constituent un nuages de points.

Je voudrai trouver un moyen simple de lire uniquement les points extrêmes ou périphériques de ce nuage de points pour en créer le contour (périmètre).

De mémoire, j'ai deja fait ça avec OpenCv, y'a des algo implémentés tout cuits
(convexhull et compagnie)

Citation:

Envoyé par akirira

De mémoire, j'ai deja fait ça avec OpenCv, y'a des algo implémentés tout cuits
(convexhull et compagnie)

Salut les gars,

merci pour vos propositions. J'ai trouvé ceci :

Code:

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() ;
	}
}
/*_________________________________________________________________________________________
*/

Caio