Cette question est un peu complexe. J'ai écrit un algorithme pour décomposer un simple polygone en sous-polygones convexes, mais maintenant j'ai du mal à prouver que c'est no optimale (c'est-à-dire le nombre minimal de polygones convexes utilisant des Points Steiner (sommets ajoutés)). Mon professeur insiste sur le fait que ce n'est pas possible avec un algorithme gourmand tel que celui-ci, mais je ne vois pas de contre-exemple.
Donc, si quelqu'un peut prouver que mon algorithme est sous-optimal (ou optimal), je l'apprécierais.
La façon la plus simple d'expliquer mon algorithme avec des images (celles-ci proviennent d'une ancienne version sous-optimale)
Ce que fait mon algorithme, c'est étendre les segments de ligne autour du point i jusqu'à ce qu'il atteigne un point sur le bord opposé.
S'il n'y a pas de sommet dans cette plage, il en crée un nouveau (le point rouge) et s'y connecte :
S'il y a es un ou plusieurs sommets dans la plage, il se connecte au plus proche. Le site généralement produit une décomposition avec le plus petit nombre de polygones convexes :
Cependant, dans certains cas, elle peut échouer - dans la figure suivante, si elle relie d'abord la ligne verte du milieu, cela créera un polygone supplémentaire inutile. Pour cela, je propose de vérifier deux fois toutes les arêtes (diagonales) que nous avons ajoutées, et de vérifier qu'elles sont toutes encore nécessaires. Si ce n'est pas le cas, supprimez-les :
Dans certains cas, cependant, cela ne suffit pas. Voir cette figure :
Remplacer a-b et c-d par a-c donnerait une meilleure solution. Dans ce scénario, cependant, il n'y a pas d'arêtes à supprimer, ce qui pose un problème. Dans ce cas, je suggère un ordre de préférence : pour décider à quel sommet connecter un sommet réflexe, il faut choisir le sommet ayant la plus haute priorité :
le plus bas) le sommet le plus proche
med) le vertex réflexe le plus proche
le plus haut) le réflexe le plus proche qui est aussi à portée de main lorsqu'on travaille à l'envers (difficile à expliquer) --
Sur ce chiffre Les deux sommets 5 et 12 sont dans l'intervalle défini par les segments de droite étendus 10-9 et 8-9, mais le sommet 5 devrait avoir la préférence parce que 9 est dans l'intervalle donné par 4-5 et 6-5, mais PAS dans l'intervalle donné par 13-12 et 11-12. c'est-à-dire que l'arête 9-12 élimine le sommet réflexe de 9, mais N'ÉLIMINE PAS le sommet réflexe de 12, l'arête 9-12 élimine le sommet réflexe à 9, mais n'élimine PAS le sommet réflexe à 12, mais elle PEUT éliminer le sommet réflexe à 5, donc 5 doit être privilégié.
Il est possible que le bord 5-12 existe toujours avec cette version modifiée, mais il peut être supprimé lors du post-traitement.
Y a-t-il des cas que j'ai manqués ?
Pseudo-code (demandé par John Feminella) -- il manque les bits sous les figures 3 et 5
assume vertices in `poly` are given in CCW order
let 'good reflex' (better term??) mean that if poly[i] is being compared with poly[j], then poly[i] is in the range given by the rays poly[j-1], poly[j] and poly[j+1], poly[j]
for each vertex poly[i]
if poly[i] is reflex
find the closest point of intersection given by the ray starting at poly[i-1] and extending in the direction of poly[i] (call this lower bound)
repeat for the ray given by poly[i+1], poly[i] (call this upper bound)
if there are no vertices along boundary of the polygon in the range given by the upper and lower bounds
create a new vertex exactly half way between the lower and upper bound points (lower and upper will lie on the same edge)
connect poly[i] to this new point
else
iterate along the vertices in the range given by the lower and upper bounds, for each vertex poly[j]
if poly[j] is a 'good reflex'
if no other good reflexes have been found
save it (overwrite any other vertex found)
else
if it is closer then the other good reflexes vertices, save it
else
if no good reflexes have been found and it is closer than the other vertices found, save it
connect poly[i] to the best candidate
repeat entire algorithm for both halves of the polygon that was just split
// no reflex vertices found, then `poly` is convex
save polyIl s'avère qu'il y a un autre cas que je n'avais pas prévu : [Figure 5]
Mon algorithme tentera de connecter le sommet 1 au sommet 4, à moins que je n'ajoute une autre vérification pour m'assurer qu'il le peut. Je propose donc de placer tout ce qui est "dans la gamme" dans une file d'attente prioritaire en utilisant le schéma de priorité que j'ai mentionné plus haut, puis de prendre le sommet le plus prioritaire, de vérifier s'il peut être connecté, sinon, de le supprimer et d'utiliser le suivant. I pensez à cela rend mon algorithme O(r n log n) si je l'optimise correctement.
J'ai rassemblé un site web qui décrit vaguement mes découvertes. J'ai tendance à déplacer les choses, alors prenez-les tant que c'est chaud.
