Polygone dans le problème de généralisation des polygones

Je voudrais m'excuser auprès de tous les articles ci-dessous. Vous avez choisi le mauvais forum pour publier cela à l'origine. Cependant, plutôt que d'en faire un gaspillage complet, j'ai retravaillé la question pour qu'elle soit un véritable problème "d'informatique théorique".

Problème: Créez un algorithme qui prend un ensemble de n points ordonnés dans un plan 2D qui forment le contour d'un simple polygone A qui peut être concave ou non et crée un nouveau polygone B avec m points tels que:

1. tous les points de A sont contenus dans B
2. 3 <= m <n
3. B est le polygone dans l'ensemble de tous les B avec la plus petite surface
4. B doit être un simple polygone (c'est-à-dire sans auto-intersection).
5. L'entrée de l'algorithme est le polygone A et "m".
6. La coïncidence des segments en B avec des segments en A est autorisée.

Quelques exemples d'entrées et de sorties attendues:

1. Si A est un carré et m est 3 alors B serait le triangle avec la plus petite surface qui contient A.
2. Si A est un hexagone et m est 4 alors B serait un quadrilatère avec la plus petite surface qui contient A.

Bonne chance à tous ceux qui tentent de résoudre ce problème. Je peux vous promettre que ce sera très difficile, surtout maintenant que la solution doit être optimale.

Je ne sais pas à quoi ressemblent vos polygones, mais peut-être qu'une version simplifiée de l' algorithme Ramer – Douglas – Peucker suffit:

• pour chaque partie convexe , calculer l'aire des triangles P i P i + 1 P i + 2 formés par trois points consécutifs;$A_j$$P_i P_{i+1} P_{i+2}$
• $B_k$$P_i P'_i P_{i+1}$$P_{i+1} P'_{i+2} P_{i+2}$$P_i, P_{i+2}$$P_{i+1}$
• $min\{A_j,B_k\}$
• $n-m$

$A_j$$B_k$

Pour les algorithmes plus complexes, vous pouvez rechercher des " techniques de généralisation de polygones " bien que votre première condition (les points dans A sont contenus dans B) implique des opérations de mise à l'échelle supplémentaires.

Il y a longtemps, j'ai écrit un article qui détaillait un algorithme à temps linéaire pour trouver le triangle de plus petite surface entourant un ensemble de points (ou un polygone):

J. O'Rourke, Alok Aggarwal, Sanjeev Maddila, Michael Baldwin, «Un algorithme optimal pour trouver un minimum de triangles englobants», J. Algorithms , 1986, 7 : 258-269. Lien .

Notre travail a été suivi d'un algorithme général:

«Surface minimale circonscrivant les polygones», Alok Aggarwal, JS Chang et Chee K. Yap, The Visual Computer , Volume 1, Number 2 (1985), 112-117. Lien .

Vous pouvez utiliser Google Scholar pour suivre les articles ultérieurs qui les citent pour trouver des améliorations et des travaux connexes.