Cherche l'algorithme le plus rapide pour déterminer le minimum bounding rectangle et le convex hull en 2D

Version imprimable

Voir 40 message(s) de cette discussion en une page

29/02/2012, 16h37
moooona

Cherche l'algorithme le plus rapide pour déterminer le minimum bounding rectangle et le convex hull en 2D

Bonjour,
Je cherche le minimum bounding rectangle d'un ensemble des points en 2D.
A partir de mes recherches dans le net j'ai trouvé qu'il faut trouver le convex hull tout d'abord.
J'ai trouvé dans quelques forum que le quick convex hull est le plus rapide mais je n'ai pas trouvé l'algorithme de cette méthode.
En fait j'ai besoin de la méthode la plus rapide car j'ai presque 900000 points. Est ce qu'il y a quelqu'un qui peut me donner l'algorithme le plus rapide pour déterminer le minimum bounding rectangle.
j'ai cherché même pour le convex hull et je n'ai pas trouvé l'algorithme juste j'ai trouvé des liens qui expliquent ce qu'il faut faire mais j'ai pas trouvé l'algorithme exacte.
Merci
29/02/2012, 17h29
pseudocode

Citation:

Envoyé par moooona

j'ai cherché même pour le convex hull et je n'ai pas trouvé l'algorithme juste j'ai trouvé des liens qui expliquent ce qu'il faut faire mais j'ai pas trouvé l'algorithme exacte.
Merci

The Quickhull algorithm for convex hulls

( accessible depuis le site www.qhull.org )
01/03/2012, 07h58
ToTo13

Bonjour,

pour l'enveloppe convexe, j'utilise la marche de Graham , la complexité est en O(N Log N) car elle utilise un tri (Quick Sort), suivi d'un parcourt en O(N).

Pour la bounding box, je ne crois pas qu'il y ait d'algorithme optimal. La plupart du temps on calcule un diamètre de Ferêt autour de l'axe principal.
01/03/2012, 09h15
moooona

Bonjour ,
Merci pour vos réponses

Citation:

Envoyé par ToTo13

Bonjour,

pour l'enveloppe convexe, j'utilise la marche de Graham , la complexité est en O(N Log N) car elle utilise un tri (Quick Sort), suivi d'un parcourt en O(N).

Pour la bounding box, je ne crois pas qu'il y ait d'algorithme optimal. La plupart du temps on calcule un diamètre de Ferêt autour de l'axe principal.

Est ce que vous pouvez me donner un lien où je peux trouver l'algorithme détaillé qui explique comment on peut calculer le diamètre de Ferêt.
Merci
01/03/2012, 09h56
pseudocode

Citation:

Envoyé par ToTo13

Pour la bounding box, je ne crois pas qu'il y ait d'algorithme optimal. La plupart du temps on calcule un diamètre de Ferêt autour de l'axe principal.

Je ne sais pas si c'est optimal, mais c'est assez rapide : rotating calipers
01/03/2012, 10h28
souviron34

Pour calculer le convex hull, il y a tout un tas d'algos.

Les plus rapides sont en O(N), puis O(Nm), puis O(NlogN)

La différence entre tient dans les hypothèses de base : polygone simple ou complexe, en gros.

Voir :

Convex hull algorithms (wiki)

et

A History of Linear-time Convex Hull Algorithms for Simple Polygons
01/03/2012, 11h13
moooona

Citation:

Envoyé par souviron34

Pour calculer le convex hull, il y a tout un tas d'algos.

Les plus rapides sont en O(N), puis O(Nm), puis O(NlogN)

La différence entre tient dans les hypothèses de base : polygone simple ou complexe, en gros.

mais j'ai trouvé que javaris march est le plus rapide (complexité O(Nm)). Je n'ai pas trouvé un algorithme de complexité O(N)

Citation:

Envoyé par pseudocode

Je ne sais pas si c'est optimal, mais c'est assez rapide : rotating calipers

J'ai trouvé ces deux algorithmes
The minimum area enclosing rectangle for a convex polygon et The minimum perimeter enclosing rectangle for a convex polygon mais j'ai pas compris quel est le meilleur.
01/03/2012, 17h26
souviron34

Citation:

Envoyé par moooona

Je n'ai pas trouvé un algorithme de complexité O(N)

euh.. Le deuxième lien indique "LINEAR" time.. :aie:
01/03/2012, 17h45
moooona

Citation:

Envoyé par souviron34

Pour calculer le convex hull, il y a tout un tas d'algos.

Convex hull algorithms (wiki)

SVP j'ai besoin de vos aides.
D'après ce que j'ai vu dans le net, j'ai trouvé que QUickHull est le plus rapide car j'ai beaucoup de points et je cherche l'algorithme le plus rapide.
Est ce que c'est ça ou non et j'ai pas trouvé un algorithme détaillé de cette méthode
01/03/2012, 20h41
ToTo13

Citation:

Envoyé par souviron34

A History of Linear-time Convex Hull Algorithms for Simple Polygons

Citation:

Envoyé par souviron34

euh.. Le deuxième lien indique "LINEAR" time.. :aie:

Linéaire oui, mais dans un cas bien particulier :-)

Citation:

Envoyé par moooona

mais j'ai trouvé que javaris march est le plus rapide (complexité O(Nm)). Je n'ai pas trouvé un algorithme de complexité O(N)
J'ai trouvé ces deux algorithmes
The minimum area enclosing rectangle for a convex polygon et The minimum perimeter enclosing rectangle for a convex polygon mais j'ai pas compris quel est le meilleur.

Citation:

Envoyé par moooona

SVP j'ai besoin de vos aides.
D'après ce que j'ai vu dans le net, j'ai trouvé que QUickHull est le plus rapide car j'ai beaucoup de points et je cherche l'algorithme le plus rapide.
Est ce que c'est ça ou non et j'ai pas trouvé un algorithme détaillé de cette méthode

Il faudrait que tu vérifies si les pires des cas peuvent survenir dans ton problème. Car Jarvis et Quick Hull ont cette complexité dans le pire des cas, mais sont très rapide ne moyenne.

Puisque tu as de très nombreux points, je te conseille d'utiliser l'heuristique d' AKL Toussaint, qui permet de supprimer de TRES nombreux points avant de réaliser le calcul et ainsi d'optimiser grandement tout ce qui suit.

Pour ce qui est de QuickHull, tu as vraiment tout ce dont tu as besoin :
[ame="http://www.google.fr/search?client=safari&rls=en&q=quickhull+algorithm&ie=UTF-8&oe=UTF-8&redir_esc=&ei=789PT8DxCufB0QWCwanbCw"]- 1 -[/ame]

- 2 - et même du code source [ame="http://www.google.fr/search?client=safari&rls=en&q=quickhull+c&ie=UTF-8&oe=UTF-8&redir_esc=&ei=UdBPT_-qLKWs0QXyirzSCw"]C[/ame] (3 liens) et [ame="http://www.google.fr/search?client=safari&rls=en&q=quickhull+java&ie=UTF-8&oe=UTF-8&redir_esc=&ei=ltBPT6OfMqiq0QXh9LXvCw"]java[/ame] (2 liens).

Et pour Jarvis :
- 1 -
[ame="http://www.google.fr/search?client=safari&rls=en&q=convex+hull+jarvis&ie=UTF-8&oe=UTF-8&redir_esc=&ei=7NBPT9WeM4Oh0QXll53dCw"]- 2 - [/ame] (avec des jolies démos javascript).
01/03/2012, 22h56
pseudocode

Citation:

Envoyé par ToTo13

Puisque tu as de très nombreux points, je te conseille d'utiliser l'heuristique d' AKL Toussaint, qui permet de supprimer de TRES nombreux points avant de réaliser le calcul et ainsi d'optimiser grandement tout ce qui suit.

Je plussoie très fortement cette solution : pre-processing avec AKL Toussaint, suivi d'un algo de convex-hull sur les points restants (pour ma part, je préfère le Graham scan).
02/03/2012, 02h35
souviron34

je plussoie très fortement :)

en attendant ma prochaine publication sur une variation de cette heuristique ;)
02/03/2012, 10h06
ToTo13

Citation:

Envoyé par souviron34

je plussoie très fortement :)

C'set gentil :-)

Citation:

Envoyé par souviron34

en attendant ma prochaine publication sur une variation de cette heuristique ;)

Allez hop, au travail. J'ai hate de voir le résultat !
02/03/2012, 10h28
souviron34

Citation:

Envoyé par ToTo13

Allez hop, au travail. J'ai hate de voir le résultat !

c'est en cours.. mais avec 2 autres en //.

Je ne modifie pas la complexité "théorique", mais j'améliore (pas mal) la compleixté "cyclomatique", ou disons le nombre d'opérations.. Disons que la complexité de calcul est la même que la complexité théorique.

Encore un peu de patience (1 mois j'espère) :)
02/03/2012, 11h29
moooona

Citation:

Envoyé par souviron34

c'est en cours.. mais avec 2 autres en //.

Je ne modifie pas la complexité "théorique", mais j'améliore (pas mal) la compleixté "cyclomatique", ou disons le nombre d'opérations.. Disons que la complexité de calcul est la même que la complexité théorique.

Encore un peu de patience (1 mois j'espère) :)

souviron, j'ai pas trouvé des informations sur cet algorithme. Il n'est pas connu pour le convex hull et j'ai pas trouvé des analyses et des études sur cet algorithme.
Est ce que c'est le plus rapide pour déterminer le convex hull et est ce que vous avez des liens qui définissent l'algorithme.
Merci bien pour votre aide
02/03/2012, 11h56
ToTo13

Citation:

Envoyé par moooona

souviron, j'ai pas trouvé des informations sur cet algorithme. Il n'est pas connu pour le convex hull et j'ai pas trouvé des analyses et des études sur cet algorithme.
Est ce que c'est le plus rapide pour déterminer le convex hull et est ce que vous avez des liens qui définissent l'algorithme.
Merci bien pour votre aide

Regarde ici.
02/03/2012, 14h20
moooona

oui, j'ai vu ce lien mais il ne donne pas l'algorithme détaillé.
Il indique qu'il va prendre les points qui ont Xmax, y_max, x_min, ymin mais après comment je peux déterminer les autres points du convex hull?
02/03/2012, 18h30
pseudocode

Citation:

Envoyé par moooona

oui, j'ai vu ce lien mais il ne donne pas l'algorithme détaillé.
Il indique qu'il va prendre les points qui ont Xmax, y_max, x_min, ymin mais après comment je peux déterminer les autres points du convex hull?

C'est normal. Le lien de Toto13 est celui de l'heuristique de AKL Toussaint, qui s'occupe seulement de "supprimer" les points qui n'appartiendront pas a l'enveloppe.

Pour la construction de l'enveloppe avec les points restant, il faut utiliser les algos qu'on a déjà cité : Quickhull, Graham scan, ...
07/03/2012, 16h46
3aychoucha

Bonjour,
Je suis intéressé par le sujet et j'ai quelques questions:

Citation:

Envoyé par pseudocode

Je plussoie très fortement cette solution : pre-processing avec AKL Toussaint, suivi d'un algo de convex-hull sur les points restants(pour ma part, je préfère le Graham scan).

Pourquoi?? quel est son avantage par rapport au quickHull??? pourtant que le quickHull est très rapide
Appliquer l'heuristique AKL-toussaint puis appliquer quickHull sera plus rapide que Graham scan??

Dans ce lien je trouve d'autres algorithmes pour chercher le convexHull http://en.wikipedia.org/wiki/Convex_...hms#Algorithms
alors quel est le meilleur pourtant qu'ils ont presque tous la même complexité?

Citation:

Envoyé par ToTo13

Puisque tu as de très nombreux points, je te conseille d'utiliser l'heuristique d' AKL Toussaint, qui permet de supprimer de TRES nombreux points avant de réaliser le calcul et ainsi d'optimiser grandement tout ce qui suit.

Dans mes recherches sur google je ne trouve pas d'explications détaillées ou un bout de code de cette heuristique, :aie: :aie: donc ça reste un peu flou srtt pour un débutant.

Une dernière question: En 3D, quel est le meilleur et le plus rapide algorithme pour déterminer le convexHull??

Merci d'avance :)
07/03/2012, 18h32
moooona

Bonjour,
est ce qu'il y a quelqu'un qui peut me donner un lien vers le code ou bien l'algorithme de calcul de Minimum bounding rectangle. J'ai trouvé la méthode rotating calipers mais j'ai pas trouvé un code ou bien un algorithme détaillé de cette méthode.
J'ai trouvé ce lien qui indique qu'il y a une méthode implémenté en java mais j'ai pas trouvé le code
http://big-o.nl/apps/compgeom/api/co...java.util.List)

Voir 40 message(s) de cette discussion en une page