Version imprimable
Je ne sais pas si ca sera plus rapide : tout dépend de l'implémentation et de l'utilisation.Citation:
Envoyé par 3aychoucha
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).
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)
Euh... L'heuristique permet d'éliminer dans le cas général plus de 90% des points par un test simple O(N).Citation:
Envoyé par 3aychoucha
Quand on a beaucoup de points, ça compte.. beaucoup.. :)
et un café avec ça ?? :aie:Citation:
Envoyé par moooona
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.Citation:
Envoyé par souviron34
Toujours je compte sur moi même pour ça
Pourtant, la page Wiki indiquée lus haut donne ce qu'il faut, et ce n'est pas compliqué :aie:
Que veux-tu de plus ???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.
cette définition n'est pas claire du tout.
qu'est qu'il vaut dire par
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 pointsCitation:
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.
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
Bonjour,
Merci pour vos réponses, mais un autre petit soucis:
Comment je peux éliminer les points situés dans un quadrilatère????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.
Merci d'avance
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
Bonjour,
Merci souviron34 pour votre aide :)