Comment sous-échantillon d'un polygone 2D?

Question

J'ai des polygones qui définissent le contour de comtés au royaume-UNI.Ces formes sont très détaillées (10k à 20k points chacun), ce qui rend les calculs liés (point X dans le polygone P?) tout à fait computationaly cher.

Donc, je voudrais à "sous-échantillon" mes polygones, pour obtenir une forme similaire, mais avec moins de points.Quelles sont les différentes techniques pour le faire?

Le trivial, l'une serait de prendre un tous les N points (donc le sous-échantillonnage d'un facteur N), mais là c'est trop "brut".Je préfère faire une sorte de moyenne de points, ou quelque chose de la saveur.Un pointeur?

Answer 1

Deux solutions viennent à l'esprit:

1) depuis la carte du royaume-UNI est raisonnablement carrée, vous pouvez choisir d'effectuer le rendu d'une image bitmap avec les comtés.Attribuer à chacune une couleur spécifique, puis de rendre les frontières avec un pas de 1 ou 2 pixels épaisse ligne noire.Cela signifie que vous n'aurez plus qu'à effectuer le coûteux intérieur/extérieur de calcul si un échantillon arrive à mentir sur la frontière.La plus grande de l'image, la moins souvent ce qui va arriver.

2) simplifier le comté de contours.Vous pouvez utiliser un récursif Ramer–Douglas–Peucker algorithme récursivement simplifier les limites.Assurez-vous de mettre en cache les résultats.Vous peut ont également pour résoudre ce pas pour l'ensemble du comté de limites, mais pour des limites partagées uniquement à s'assurer qu'aucun des lacunes.Cela peut être très difficile.

Answer 2

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 conçu pour vous 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 3

Polygone triangulation devrait aider ici.Vous devrez toujours vérifier le nombre de polygones, mais ce sont des triangles, de sorte qu'ils sont plus faciles à vérifier et que vous pouvez utiliser quelques optimisations pour déterminer seulement un petit sous-ensemble de polygones à vérifier pour une région donnée ou d'un point.

Comme il semble que vous avez tous les algorithmes dont vous avez besoin pour les polygones, non seulement pour les triangles, vous pouvez aussi fusionner plusieurs triangles qui sont trop petits après triangulation ou si le nombre de triangle devient trop élevée.