Minimiser les sommets des polygones

Question

Qu'est-ce qu'un bon algorithme pour réduire le nombre de sommets d'un polygone sans changer la façon dont il est très apparent?

Entrée: Un polygone, représenté par une liste de points, avec beaucoup trop de verticies: entrée brute de la souris, par exemple.

Sortie: Un polygone avec beaucoup moins de verticies qui ressemble encore beaucoup à l'original: quelque chose utilisable pour la détection de collision, par exemple (pas nécessairement convexe). Edit: La solution à cette question serait similaire à trouver une ligne multi-segmentée de meilleur ajustement sur un graphique. C'est ce qu'on appelle les moindres carrés segmentés dans mon livre d'algorithmes.

Edit2: L'algorithme Douglas Peucker est ce que je veux vraiment.

Answer 1

Edit: Oh regarde, Simplifying Polygons

Vous avez mentionné la détection de collision. Vous pouvez aller très simple et calculer une coque convexe limitant autour d'elle. Si vous vous souciez des zones concaves, vous pouvez calculer une coque concave en prenant le centroïde de votre polygone, et en choisissant un point pour commencer. À partir du point de départ, tournez autour du centroïde, trouvez chaque sommet que vous voulez conserver et attribuez-le comme sommet suivant dans la coque de délimitation. La complexité de l'algorithme viendrait dans la façon dont vous avez déterminé quels sommets conserver, mais je suis sûr que vous y avez déjà pensé. Vous pouvez lancer tous vos sommets dans des compartiments en fonction de leur emplacement par rapport au centroïde. Quand un seau reçoit plus qu'un nombre arbitraire de sommets, vous pouvez le diviser. Ensuite, prenez la moyenne des sommets dans ce seau comme le sommet à utiliser dans votre coque de délimitation. Ou, oubliez les seaux, et quand vous vous déplacez autour du centroïde, choisissez seulement un point si c'est plus d'une distance donnée du dernier point. En fait, vous pourriez probablement utiliser tous les vertices de votre polygone comme "nuage de points" et calculer la coque concave autour de celle-ci. Je vais chercher un lien d'algorithme. Le pire des cas serait un polygone complètement convexe.

Une autre alternative consiste à commencer par un rectangle de délimitation. Pour chaque sommet du rectangle, trouvez la distance entre le point et le polygone. Pour le sommet le plus éloigné, divisez-le en deux autres sommets et déplacez-les dans certains. Répétez jusqu'à ce qu'une partie des sommets ou de la zone soit atteinte. Je devrais réfléchir aux détails de celui-ci un peu plus. Si vous tenez à ce que le polygone ressemble réellement, même dans le cas d'un polygone à auto-intersection, alors une autre approche serait nécessaire, mais cela ne semble pas nécessaire puisque vous avez posé des questions sur la détection de collision.

Ce post a quelques détails sur la partie de la coque convexe.

Answer 2

Il y a beaucoup de matériel là-bas. Juste google pour des choses comme "la réduction du maillage", "simplification du maillage", "l'optimisation du maillage", etc.