Forum Programmation.c Algo / Determiner le plus grand rectangle d'une région

Posté par  (site web personnel) .
Étiquettes : aucune
0
30
jan.
2007
Bonjour

Je recherche un algo qui me permettrais de determiner le rectangle le plus grand d'un polygone.
Malheureusement je manque de vocabulaire concernant l'algorithmie.

Pouvez vous me donner des pistes, des liens ou du vocabulaire pour faire mes recherches svp ?

J'ai trouvé la fonction gdk-region-get-clipbox mais en fait elle retourne l'inverse.

http://developer.gnome.org/doc/API/2.0/gdk/gdk-Points-Rectan(...)

Merci de votre aide.

  • # Un lien ...

    Posté par  . Évalué à 5.

    Un développeur de The Gimp a implémenté ça il y a quelques semaines. Voilà un lien vers l'article de son blog où il en parle (en anglais) :
    http://svenfoo.geekheim.de/index.php/2005-04-24/computationa(...)

    • [^] # Re: Un lien ...

      Posté par  (site web personnel) . Évalué à 2.

      Merci beaucoup de ton lien qui semble interessant, malheureusement, c'est au dessus de mon niveau en anglais et en math.

      Quelqu'un a t'il des ressources francophones ou alors moins balèze techniquement ?

  • # simplex?

    Posté par  . Évalué à 3.

    En représentant le rectangle par (x, y, w), ou (x, y) est le point de base du rectangle, et w la largeur du rectangle, on obtient un ensemble de contraintes et une valeur à maximiser: w*w

    Comme maximiser w*w (fonction strictement croissante) revient a maximiser w, le problèmes est un problème de programmation linéaire.

    On doit donc pouvoir le résoudre avec l'algorithme du simplex.
    Ca doit se trouver une lib qui implémente cet algo, non?

    Bon, ça fait pas mal de temps que j'ai pas fait ce genre de choses, donc il y a peut-être des erreurs dans mon raisonnement...

  • # CGAL

    Posté par  . Évalué à 1.

    http://www.cgal.org

    bon, c'est pas du C mais du C++.
    il faut regarder du côté des volumes inscrits (inscribed volumes). Y'a sûrement des références intéressantes de ce côté...

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.