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

Version imprimable

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)
07/03/2012, 20h18
pseudocode

Citation:

Envoyé par 3aychoucha

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??

Je ne sais pas si ca sera plus rapide : tout dépend de l'implémentation et de l'utilisation.

Pour ma part, je préfère le Graham scan (ou plutot la variante "Monotone chain") car ca s'implémente sans récursion, juste avec deux boucles while et des piles, et aussi un algo de tri (quicksort).
08/03/2012, 09h04
gragaou

Le problème de QuickHull c'est que dans le pire des cas (Tout les points sur une sphère en 3D) l'algo a comme complexité O(n^2)
08/03/2012, 10h36
souviron34

Citation:

Envoyé par 3aychoucha

Appliquer l'heuristique AKL-toussaint puis appliquer quickHull sera plus rapide que Graham scan??
...
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.

Euh... L'heuristique permet d'éliminer dans le cas général plus de 90% des points par un test simple O(N).

Quand on a beaucoup de points, ça compte.. beaucoup.. :)

Citation:

Envoyé par moooona

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

et un café avec ça ?? :aie:

Ici on ne donne a priori pas de code, sauf contributions..
08/03/2012, 10h47
moooona

Citation:

Envoyé par souviron34

et un café avec ça ?? :aie:

Ici on ne donne a priori pas de code, sauf contributions..

Dans le forum on demande de l'aide. j'ai besoin de l'algorithme détaillé pour implémenter la méthode mais j'ai pas trouvé aucun lien qui me permet de clarifier ça donc j'ai demandé de l'aide s'il y a quelqu'un qui peut me donner un lien où je peux trouver l'algo et j'ai pas demandé à quelqu'un de m'implémenter le code.
Toujours je compte sur moi même pour ça
08/03/2012, 10h53
souviron34

Pourtant, la page Wiki indiquée lus haut donne ce qu'il faut, et ce n'est pas compliqué :aie:

Citation:

Find the two points with the lowest and highest x-coordinates, and the two points with the lowest and highest y-coordinates. (Each of these operations takes O(n).) These four points form a convex quadrilateral, and all points that lie in this quadrilateral (except for the four initially chosen vertices) are not part of the convex hull. Finding all of these points that lie in this quadrilateral is also O(n), and thus, the entire operation is O(n). Optionally, the points with smallest and largest sums of x- and y-coordinates as well as those with smallest and largest differences of x- and y-coordinates can also be added to the quadrilateral, thus forming an irregular convex octagon, whose insides can be safely discarded.

Que veux-tu de plus ???
08/03/2012, 10h59
moooona

cette définition n'est pas claire du tout.
qu'est qu'il vaut dire par

Citation:

ptionally, the points with smallest and largest sums of x- and y-coordinates as well as those with smallest and largest differences of x- and y-coordinates can also be added to the quadrilateral, thus forming an irregular convex octagon, whose insides can be safely discarded.

De plus avec les quatre points définissent par x_min, x_max, y_min, y_max, je vais pas avoir le minimum bounding rectangle mais par contre je peux avoir un rectangle qui englobent tous ces points
08/03/2012, 16h23
moooona

Bonjour,
SVP, Je me suis vraiment bloquée. j'ai pas trouvé comment je peux déterminer le rectangle minmum qui englobe les points.
J'ai essayé de suivre la démonstration suivante pour savoir comment déterminer les extrémités de ce rectangle minimal mais j'ai rien trouvé.
http://www.geometrictools.com/Docume...aRectangle.pdf
j'ai pas trouvé comment à partir de la surface je peux déterminer les extrémités de ce rectangle
De plus j'ai essayé de voir comment en utilisant la méthode de rotating calipers, comment je peux avoir les quatre points d'extrémités de ce rectangle mais je me suis bloquée car j'ai pas trouvé un algorithme bien expliqué.
SVP est ce qu'il y a quelqu'un qui peut m'aider.
Merci
09/03/2012, 10h15
3aychoucha

Bonjour,
Merci pour vos réponses, mais un autre petit soucis:

Citation:

Trouvez les deux points avec le plus bas et le plus haut x-coordonnez, et les deux points avec le plus bas et le plus haut y-coordonnent. (chacune de la prise de ces opérations O(n).) ces quatre points forment un quadrilatère, et tous les points qui se situent dans ce quadrilatère (excepté les quatre sommets au commencement choisis) ne sont pas une partie de la coque convexe.

Comment je peux éliminer les points situés dans un quadrilatère????

Merci d'avance
09/03/2012, 10h37
souviron34

C'est dans les FAQ réfrencées dans les liens généraux du forum..

http://www.faqs.org/faqs/graphics/algorithms-faq/

Sujet 2.03
12/03/2012, 08h47
3aychoucha

Bonjour,

Merci souviron34 pour votre aide :)