Polygones simplifiés (ou lisses) contenant le polygone détaillé d'origine

Question

J'ai détaillé polygone 2D (représentant une zone géographique), qui est définie par un ensemble très grand nombre de sommets. Je suis à la recherche d'un algorithme qui permettra de simplifier et lisse le polygone (en réduisant le nombre de sommets) avec la contrainte que l' aire du polygone résultant doit contenir tous les sommets de l'détaillée polygone.

Pour le contexte, voici un exemple de l'arête d'un polygone complexe:

Ma recherche:

• J'ai trouvé l'Ramer–Douglas–Peucker algorithme qui permettra de réduire le nombre de sommets -, mais le polygone ne contiennent pas tous les originaux des sommets du polygone. Voir cet article Ramer-Douglas-Peucker sur Wikipédia

• J'ai envisagé d'élargir le polygone (je crois que ceci est également connu comme vers l'extérieur du polygone de compensation). Je trouve ces questions: l'Expansion d'un polygone (convexe seulement) et le Gonflage d'un polygone. Mais je ne pense pas que cela permettra de réduire considérablement le détail de mon polygone.

Merci pour tous les conseils que vous pouvez me donner!

Answer 1

Modifier

À compter de 2013, la plupart des liens ci-dessous ne sont pas fonctionnels plus. Cependant, j'ai trouvé l'article cité, l'algorithme inclus, toujours disponible à cette (très lent) du serveur.

---

Ici vous pouvez trouver un projet traitant exactement à vos questions. Bien qu'il travaille principalement avec une zone "rempli" par des points, vous pouvez le configurer pour fonctionner avec un "périmètre" de la définition de type que le vôtre.

Il utilise un k-plus proches voisins de l'approche pour le calcul de la région.

Échantillons:

Ici vous pouvez demander une copie de la feuille de papier.

Apparemment ils ont prévu d'offrir un service en ligne pour demander des calculs, mais je n'ai pas le tester, et probablement il n'est pas en cours d'exécution.

HTH!

Answer 2

C'est un problème intéressant! Je n'ai jamais essayé quelque chose comme cela, mais voici une idée sur le dessus de ma tête... toutes mes excuses si il n'a pas de sens ou ne fonctionne pas :)

1. Calculer l'enveloppe convexe, qui pourrait être trop grand / imprécis
2. Diviser la coque en N tranches, par exemple de rejoindre chacun de la coque sommets au centre
3. Calculer l'intersection de votre objet avec chaque tranche
4. Répéter de manière récursive pour chaque intersection (calcul de l'intersection de la coque, etc)

Chaque niveau de récursivité devrait donner une meilleure approximation.... lorsque vous avez atteint un niveau satisfaisant, de fusionner toutes les coques à partir de ce niveau pour obtenir la valeur finale de polygone.

Est-ce que sembler comme s'il pouvait faire le travail?