Comment trouver le rectangle de surface maximale à l'intérieur d'un polygone convexe?

21

Dans cet article, nous recherchons des algorithmes / idées sur la façon de trouver le rectangle de zone maximale à l' intérieur d'un polygone convexe .

Dans la figure suivante, les nombres sont les zones des rectangles ajustés. Comme indiqué, un rectangle souhaité peut varier dans chaque dimension et peut être dans n'importe quel angle.

Éditer:

Nous n'avons aucune idée claire de la façon de traiter le problème mentionné, comme nous l'avons demandé ici. Néanmoins, nous supposons que le rectangle d'aire maximale peut être l'un de ceux qui ont un bord aligné sur (pas nécessairement le même bord de longueur, bien sûr) un bord du polygone.

entrez la description de l'image ici

Développeur
la source
1
Pourriez-vous spécifier quel logiciel vous utilisez? Aussi, postez votre travail jusqu'ici, ou l'approche générale que vous avez élaborée pour résoudre ce problème. Peut-être que quelqu'un peut améliorer ce que vous avez déjà fait. D'après mon expérience, cela donnera des réponses bien plus utiles que la simple publication d'une question "à l'improviste".
Martin
1
Étroitement liés: gis.stackexchange.com/questions/22895/… .
whuber
@Martin Software: La programmation Pythonsera alors effectuée Fortransi nécessaire. Nous avons une supposition que sur la base de notre post précédent ici également mentionné ci-dessus par whuberce peut être un rectangle avec un bord commun avec le polygone serait une réponse.
Développeur
1
Votre problème est vraiment intéressant, et je pense que j'ai réussi à trouver un algorithme de résolution ici et ici .
nickves
1
@nickves Merci pour les liens. Pourriez-vous s'il vous plaît mettre ces informations comme réponse avec une petite explication des algorithmes? Ce sera potentiellement une bonne réponse à accepter.
Développeur

Réponses:

4

Quelques notes trop grosses pour être insérées dans un commentaire (bien que cela ne suggère pas un algorithme évident):

La ligne de poinçonnage (MODIFIEE) : au moins deux sommets du rectangle d'aire maximale doivent se trouver à la limite du polygone (c.-à-d. Le long d'une arête ou à un sommet). Et si le rectangle d'aire maximale n'est pas un carré, alors au moins trois sommets doivent se trouver à la limite du polygone.

Je l'ai prouvé en quatre étapes:

Remarque n ° 1 : au moins un sommet du rectangle d'aire maximale se trouvera toujours à la limite du polygone. C'est assez évident, mais une preuve pourrait ressembler à ceci (par contradiction): Supposons que vous ayez un rectangle "maximal" sans sommet à la frontière du polygone. Cela signifie qu'il y aurait au moins une petite pièce autour de chacun de ses sommets. Vous pouvez donc agrandir un peu votre rectangle, contredisant sa maximalité.

Remarque n ° 2 : au moins deux sommets du rectangle de la surface maximale se trouveront toujours à la limite du polygone. Une preuve pourrait ressembler à ceci (encore une fois par contradiction): Supposons que vous ayez un rectangle "maximal" avec un seul sommet sur la frontière (garanti par la note # 1). Considérez les deux arêtes non adjacentes à ce sommet. Étant donné que leurs points d'extrémité ne sont PAS sur la frontière, il y a une petite place autour de chacun. Ainsi, l'un ou l'autre de ces bords pourrait être "extrudé" un peu, élargissant la zone du polygone et contredisant sa maximalité.

Remarque # 3 : Il y a deux sommets diagonalement opposés du rectangle d'aire maximale qui se trouvent à la limite du polygone. (Nous savons par la note n ° 2 qu'il y en a au moins deux, mais pas nécessairement qu'ils sont en face l'un de l'autre.) sont à la limite) pourrait être extrudé un peu, augmentant la surface du rectangle et contredisant sa maximalité.

Remarque n ° 4 : (MODIFIÉ) Si le rectangle de la zone maximale n'est pas un carré, alors trois de ses sommets se trouveront à la limite du polygone.

Pour prouver, supposons que ce n'est pas le cas, c'est-à-dire que le rectangle d'aire maximale n'est pas un carré, mais seulement deux de ses sommets se trouvent à la frontière du polygone. Je vais montrer comment construire un rectangle plus grand, contredisant la maximalité.

Appelez les sommets du rectangle A, B, Cet D. Sans perte de généralité, supposez cela Bet ce Dsont les deux qui se trouvent sur la frontière du polygone. Depuis Aet Cà l'intérieur du polygone, il y a une certaine marge de manœuvre autour d'eux (représentés par des cercles autour Aet Cdans l'image ci-dessous). Maintenant, dessinez un cercle autour du rectangle et faites glisser les points Aet Cun peu autour du cercle de la même quantité (pour faire A'et C', illustré ci-dessous) de sorte que le nouveau rectangleA'BC'Dest plus carré que le rectangle d'origine. Ce processus crée un nouveau rectangle qui se trouve également dans le polygone d'origine et a une plus grande surface. C'est une contradiction, donc la preuve est faite.

Construire un nouveau rectangle

Pour croire cette preuve, vous devez vous convaincre que l'aire d'un rectangle inscrit dans un cercle augmente à mesure qu'il devient "plus carré" (c'est-à-dire que la différence entre les longueurs de bord diminue). Vous devez également que le polygone soit convexe pour que les nouvelles lignes soient toutes à l'intérieur. Et il y a probablement d'autres petits détails sous le tapis, mais je suis presque sûr qu'ils fonctionnent tous.

csd
la source
La note n ° 4 est louche, car en "agitant" les deux autres sommets créeront des non-rectangles.
whuber
Vrai. Cependant, votre visualisation du 4ème exemple n'est pas tout à fait correcte (si 2 sommets sont sur la frontière du polygone, vous ne pouvez pas l'étirer davantage). Je ne trouve pas exactement comment l'expliquer (j'ai essayé d'écrire un commentaire mais c'est devenu trop compliqué), mais j'espère que vous avez raison.
Saryk
Je crois qu'il y a des contre-exemples à noter # 4. Cependant, ceux que j'ai trouvés nécessitent des calculs complexes; la plus simple est une perturbation d'un hexagone irrégulier (un carré avec deux coins opposés légèrement coupés).
whuber
Convenu que la note # 4 est louche. Je vais regarder de plus près ce soir et le réparer ou le retirer.
csd
+1 C'est une belle résolution de la difficulté. Merci pour l'édition!
whuber
3

J'ai fait un croquis très rapide et hideux sur votre note verte dans la question. Je ne pouvais pas le poster comme commentaire, j'ai donc dû écrire une réponse, même si ce n'est pas le cas.
Je crois que dans l'image ci-dessous, nous avons un rectangle de zone maximale (pas parfait, c'est juste un croquis fait sur Paint pour donner une idée), et je ne pense pas que vous puissiez en trouver un plus grand qui aurait un côté commun avec le bordures du plygon noir ...
Cependant je peux me tromper, dans ce cas vous avez toutes mes excuses.
Croquis rapide que j'ai fait sur Paint

Saryk
la source
3
Bon point (+1). Il existe cependant un contre-exemple beaucoup plus simple: considérez le problème de l'inscription d'un rectangle de zone maximale dans un octogone régulier. Il est facile de voir (et facile à prouver en trouvant d'abord un carré maximal dans le cercle de l'octogone) que les coins de la solution coïncident avec des sommets alternés de l'octogone et que cette solution est sensiblement plus grande que tout rectangle inscrit aligné sur les bords.
whuber
En fait (j'ai juste un gros doute en ce moment), le plus petit rectangle externe (ceux de ce post ) de ce polygone n'a pas la même orientation que l'un des côtés, n'est-ce pas? (Je verrais la même orientation que mon rectangle rouge)
Saryk
3
Soit dit en passant, ce polygone n'est pas convexe. La question d'origine se limite aux polygones convexes.
csd
2
@csd C'est un bon point, mais Saryk a toujours raison, comme le montre mon contre-exemple. Saryk, il n'y a pas de problème avec le rectangle de délimitation de la surface minimale: il est facile de prouver (rigoureusement) qu'il doit inclure un côté de la coque convexe. Je crois que la surface maximale inscrite rectangle (d'un polygone convexe) n'a besoin que de deux sommets touchant la frontière, pas plus.
whuber
2

La plupart des autres algorithmes trouvent la surface maximale rectangle rectiligne inscrit dans un polygone convexe et ont une complexité de O(log n). Je ne pense pas que votre supposition que le polygone de la zone maximale soit aligné avec l'un des côtés soit correcte, car tout ce que vous auriez à faire serait de faire pivoter les ntemps du polygone , ce qui entraînerait une complexité O(n log n)et, dans ma brève recherche, je ne pourrais pas trouver quoi que ce soit disant que c'était aussi simple que cela.

Cependant, l'article Les plus grands rectangles inscrits dans les polygones convexes de Knauer, et. al., décrit un algorithme d'approximation qui vous rapprochera de la bonne réponse.

D'après ce que je comprends de l'algorithme, il s'appuie sur l'un des polygones connus de la zone maximale alignée sur l'axe, puis échantillonne au hasard les points à l'intérieur de l'espace de polyon, génère plusieurs axes à partir de ces échantillons aléatoires, itère sur cet axe et applique l'axe -algorithme aligné à chacun, puis renvoie le plus grand rectangle de cet ensemble.

lreeder
la source
Y a-t-il peut-être une faute de frappe dans la première phrase? Il ne peut pas y avoir d'algorithme O (log (n)) car la simple lecture des coordonnées est une opération O (n)!
whuber
Le lien est mort
dangerousdave
1
@dangerousdave - Trouvé un lien alternatif pour aussi longtemps que ça dure ....
lreeder