Existe-t-il un algorithme efficace pour générer une coque concave 2D?
https://stackoverflow.com/questions/83593
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Ayant un ensemble de points (2D) à partir d’un fichier SIG (une carte de ville), je dois générer le polygone qui définit le "contour" de cette carte (ses limites). Ses paramètres d'entrée seraient les points définis et une «longueur d'arête maximale». Il produirait alors le polygone correspondant (probablement non convexe).
La meilleure solution que j’ai trouvée jusqu’à présent était de générer les triangles de Delaunay, puis de supprimer les arêtes externes plus longues que la longueur maximale. Après que toutes les arêtes externes soient plus courtes que cela, je supprime simplement les arêtes internes et récupère le polygone que je souhaite. Le problème, c’est que cela prend beaucoup de temps et je me demande s’il existe un meilleur moyen.
Autres conseils
Un des anciens étudiants de notre laboratoire a utilisé certaines techniques applicables pour sa thèse de doctorat. Je crois que l’un d’eux s’appelle "formes alpha". et est référencé dans l'article suivant:
http://www.cis.rit.edu/ personnes / faculté / kerekes / pdfs / AIPR_2007_Gurram.pdf
Ce document fournit d'autres références que vous pouvez suivre.
Les gars ici déclarent avoir mis au point une approche du plus proche voisin pour déterminer la coque concave d'un ensemble de points qui se comporte "presque linéairement sur le nombre de points". Malheureusement, leur article semble être très bien gardé et vous devrez demander à eux pour cela.
Voici un bon jeu de références qui inclut ce qui précède et pourrait vous amener à trouver une meilleure approche.
La réponse peut toujours être intéressante pour quelqu'un d'autre: on peut appliquer une variante de l'algorithme du carré de marche , appliquée (1) dans la coque concave, et (2) puis sur (par exemple 3). différentes échelles qui dépendent de la densité moyenne de points. Les échelles doivent être multiples, ce qui vous permet de créer une grille que vous pourrez utiliser pour un échantillonnage efficace. Cela permet de trouver rapidement des échantillons vides = carrés, des échantillons qui se trouvent complètement dans un "cluster / nuage". des points, et ceux qui sont entre. Cette dernière catégorie peut alors être utilisée pour déterminer facilement la polyligne représentant une partie de la coque concave.
Tout est linéaire dans cette approche, aucune triangulation n’est nécessaire, elle n’utilise pas de formes alpha et elle est différente de l’offre commerciale / brevetée décrite ici ( http://www.concavehull.com/ )
Une solution simple consiste à contourner le polygone. Avec une arête courante à la limite reliant les points P0 et P1, le prochain point sur la limite P2 sera le point avec le plus petit possible A, où
H01 = bearing from P0 to P1
H12 = bearing from P1 to P2
A = fmod( H12-H01+360, 360 )
|P2-P1| <= MaxEdgeLength
Ensuite, vous définissez
P0 <- P1
P1 <- P2
et répétez jusqu'à ce que vous reveniez à votre point de départ.
Ceci est toujours O (N ^ 2), vous voudrez donc un peu trier votre liste de points. Vous pouvez limiter le nombre de points à prendre en compte à chaque itération si vous les triez, par exemple, dans leur direction depuis le centre de la ville.
Bonne question! Je n'ai pas du tout essayé cela, mais mon premier coup serait cette méthode itérative:
- Créez un ensemble N ("non contenu") et ajoutez tous les points de votre ensemble à N.
- Choisissez 3 points de N au hasard pour former un polygone initial P. Supprimez-les de N.
- Utilisez un algorithme de point-dans-polygone et examinez les points dans N. Pour chaque point dans N, s'il est maintenant contenu par P, supprimez-le de N. Dès que vous trouvez un point dans N qui n'est toujours pas contenu dans P, passez à l'étape 4. Si N devient vide, vous avez terminé.
- Appelez le point que vous avez trouvé A. Trouvez la ligne dans P la plus proche de A et ajoutez A. au milieu.
- Retournez à l'étape 3
Je pense que cela fonctionnerait tant que les performances seraient suffisantes - une bonne heuristique pour vos 3 points initiaux pourrait vous aider.
Bonne chance!
Vous pouvez le faire dans QGIS avec ce plug-in; https://github.com/detlevn/QGIS-ConcaveHull-Plugin
En fonction de la manière dont vous en avez besoin pour interagir avec vos données, vous devriez probablement vérifier comment cela s'est passé ici.
Le kit de développement logiciel interactif Bing Maps V8 contient une option de coque concave dans les opérations de forme avancées.
Une solution rapide et approximative (également utile pour les coques convexes) consiste à trouver les limites nord et sud de chaque petit élément est-ouest.
En fonction du nombre de détails que vous souhaitez, créez un tableau de taille supérieure / inférieure. Pour chaque point, calculez la colonne E-W dans laquelle il se trouve, puis mettez à jour les limites supérieure / inférieure de cette colonne. Après avoir traité tous les points, vous pouvez interpoler les points haut / bas des colonnes manquantes.
Cela vaut également la peine de faire une vérification rapide à l’avance pour les très fines formes minces et de choisir entre bin NS ou Ew.
En tant que référence très répandue, PostGIS commence par un obus convexe, puis le dépose, vous pouvez le voir ici.
https /postgis/blob/380583da73227ca1a52da0e0b3413b92ae69af9d/postgis/postgis.sql.in#L5819
