Discussion :

[moooona]

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

[pseudocode]

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 )

[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.

[moooona]

Bonjour ,
Merci pour vos réponses

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

[pseudocode]

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

[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

[moooona]

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)

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.

[souviron34]

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

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

[moooona]

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

[ToTo13]

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

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

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

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.

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).

[pseudocode]

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).

[souviron34]

je plussoie très fortement

en attendant ma prochaine publication sur une variation de cette heuristique

[ToTo13]

je plussoie très fortement

C'set gentil :-)

en attendant ma prochaine publication sur une variation de cette heuristique

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

[souviron34]

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)

[moooona]

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

[ToTo13]

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.

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

[pseudocode]

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, ...

[3aychoucha]

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

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

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

[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)