Minimiser les sommets de polygones

Question

Qu'est-ce qu'un bon algorithme pour réduire le nombre de sommets dans un polygone sans en modifier l'apparence?

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

Résultat: un polygone avec beaucoup moins de vertices qui ressemble toujours beaucoup à l’original: quelque chose de utilisable pour la détection de collision, par exemple (pas nécessairement convexe).

Modifier: la solution à ce problème serait similaire à la recherche d’une ligne multizone mieux adaptée sur un graphique. C'est ce qu'on appelle les moindres carrés segmentés dans mon livre d'algorithmes.

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

Answer 1

Éditer: Oh, regardez, Simplifier les polygones / p>

Vous avez mentionné la détection de collision. Vous pouvez aller très simple et calculer une coque convexe englobante tout autour.

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 de départ. À partir du point de départ, faites une rotation autour du centre de gravité pour trouver chaque sommet que vous souhaitez conserver et pour l’affecter au prochain sommet de la coque. La complexité de l'algorithme dépendrait de la manière dont vous avez déterminé les vertices à conserver, mais je suis sûr que vous y avez déjà pensé. Vous pouvez placer tous vos sommets dans des compartiments en fonction de leur emplacement par rapport au centre de gravité. Lorsqu'un compartiment contient plus d'un nombre arbitraire de sommets, vous pouvez le scinder. Ensuite, prenez la moyenne des sommets de ce seau comme sommet à utiliser dans votre coque. Ou bien, oubliez les compartiments et, lorsque vous vous déplacez autour du centre de gravité, choisissez un point uniquement si sa distance est supérieure à une distance donnée du dernier point.

En fait, vous pourriez probablement simplement utiliser tous les sommets de votre polygone en tant que "nuage de points". et calculer la coque concave autour de cela. 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 cette opération jusqu'à ce qu'une certaine proportion des sommets ou de la zone soit atteinte. Il faudrait que je réfléchisse un peu plus aux détails de celui-ci.

Si vous vous souciez de l'apparence du polygone, même dans le cas d'un polygone à intersection automatique, une autre approche serait alors nécessaire, mais cela ne semble pas nécessaire, car vous avez posé des questions sur la détection de collision.

Cet post contient des détails sur la partie coque convexe.

Answer 2

Il y a beaucoup de matériel disponible. Allez simplement sur Google pour des choses comme "réduction de maille", "simplification de maille", "optimisation de maille", etc.