Existe-t-il un algorithme efficace pour générer une coque concave 2D?

Question

Ayant un ensemble de (2D) des points à partir d'un fichier GIS (une carte de la ville), j'ai besoin de générer le polygone qui définit le "contour" pour cette carte (ses limites). Ses paramètres d'entrée serait la points et un maximum de bord de la longueur. Il serait alors de sortie correspondant (probablement non convexe) polygone.

La meilleure solution que j'ai trouvé jusqu'à présent a été de générer les triangles de Delaunay, puis retirez les arêtes externes qui sont plus longs que la longueur maximale des bords. Après tous les bords externes sont plus courts que cela, j'ai simplement supprimer les bords internes et d'obtenir le polygone que je veux. Le problème est, ce qui est très consommatrice de temps et je me demandais si il ya une meilleure façon.

Answer 1

Un des anciens étudiants de notre laboratoire a utilisé certaines techniques applicables pour sa thèse de doctorat. Je crois que l’une d’elles s’appelle "formes alpha" et est référencée dans l’article suivant:

http://www.cis.rit.edu/people/faculty/kerekes/pdfs/AIPR_2007_Gurram.pdf

Ce document donne d'autres références que vous pouvez suivre.

Answer 2

Cet article traite de la génération efficace de polygones simples pour caractériser la forme d’un ensemble de points dans le plan et fournit l’algorithme. Il y a aussi une applet Java en utilisant le même algorithme ici .

Answer 3

Les gars ici affirment avoir développé un k-plus proches voisins approche pour la détermination de la concave de la coque d'un ensemble de points qui se comporte "de façon quasi linéaire sur le nombre de points". Malheureusement, leur papier, semble être très bien gardé et vous devrez demander à eux .

Voici un bon jeu de références qui comprend le ci-dessus et pourrait vous amener à trouver une meilleure approche.

Answer 4

Bonne question! Je n'ai pas essayé, mais mon premier coup serait cette méthode itérative:

1. Créer un ensemble de N ("pas"), et ajouter tous les points de votre jeu à N.
2. Choix de 3 points à partir de N au hasard pour former un polygone initial P. les Supprimer à partir de N.
3. Utiliser certains des points dans un polygone de l'algorithme et de regarder les points de N. Pour chaque point en N, si elle est maintenant contenue par P, le retirer de N. dès Que vous trouvez un point de N qui n'est pas encore contenue dans P, passez à l'étape 4. Si N est vide, vous avez terminé.
4. Appelez le point vous avez trouvé A. Trouvez la ligne P le plus proche de Un, et d'ajouter dans le milieu.
5. Retournez à l'étape 3

Je pense qu'il serait de travailler aussi longtemps qu'il fonctionne bien assez - une bonne heuristique pour votre initiale de 3 points peut vous aider.

Bonne chance!