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

**moooona** · 29/02/2012, 16h37

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** · 29/02/2012, 17h29

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 )

**ToTo13** · 01/03/2012, 07h58

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** · 01/03/2012, 09h15

Bonjour ,
Merci pour vos réponses

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

**pseudocode** · 01/03/2012, 09h56

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

**souviron34** · 01/03/2012, 10h28

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** · 01/03/2012, 17h45

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

**moooona** · 01/03/2012, 11h13

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)

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.