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

**pseudocode** · 07/03/2012, 20h18

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

**gragaou** · 08/03/2012, 09h04

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)

**souviron34** · 08/03/2012, 10h36

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,

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

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

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

**moooona** · 08/03/2012, 10h47

Envoyé par souviron34

et un café avec ça ??

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

**souviron34** · 08/03/2012, 10h53

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

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

**moooona** · 08/03/2012, 10h59

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

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

**moooona** · 08/03/2012, 16h23

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

**3aychoucha** · 09/03/2012, 10h15

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

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