Comment calculer combien de polygones je peux mettre à l'intérieur d'un polygone?

9

J'utilise habituellement des qgis. J'explique mon problème avec un exemple: il y a une forêt (géométrie irrégulière1) et un arbre (géomery2). Je veux connaître le nombre maximum d'arbres que la forêt peut contenir. De plus, je veux une sortie de fichier de formes de la meilleure disposition de ces arbres à l'intérieur de la forêt.entrez la description de l'image ici

qgis polygon ksatzu
la source
3
Beau problème ....
WKT
Je ne sais même pas par où commencer. Cela ressemble à un problème / algorithme de degré Maters.
HeikkiVesanto
2
Si vous pouvez accéder à un essai gratuit d'ArcGIS (ou télécharger R qui est gratuit), le logiciel Geospatial Modeling Environment dispose d'un gencirclesinpolys (Generate Circles In Polygons)outil qui pourrait être utile.
Joseph
2
Vous cherchez un outil pour résoudre les problèmes d'emballage mais je n'en connais aucun pour QGIS
underdark
1
@Joseph J'ai utilisé l'outil Geospatial Modeling Environment, ça marche. Malheureusement, l'outil génère un arrangement régulier de cercles (ou hexagones) dans les limites des polygones, cela implique que la forme en sortie ne montre pas (nécessairement) la meilleure disposition des entités, je veux dire le nombre maximum possible.
ksatzu

Réponses:

5

Essayez cette application en ligne svgnest.com/

étapes: 1. svg crée un fichier (comme dans la figure 1); 2. Allez sur le lien et téléchargez svg; 3. Sélectionnez avec la souris le polygone conteneur; 4. commencer

après un certain nombre d'itérations, vous pouvez verrouiller et télécharger le fichier svg (voir figure 2)

NB: le polygone et les cercles doivent être dans le même fichier svg

Figure 1

Figure 2

pigreco
la source
4

Problème intéressant!

J'ai fait une chose similaire avec des polygones irréguliers (dans ce cas, les bâtiments ont été emballés pour ne pas se chevaucher)

entrez la description de l'image ici

Postgresql et postgis utilisés, et python. L'algorithme approximatif était

  • Trouver un point aléatoire dans la boîte englobante du polygone (ST_Envelope)
  • Si pointer en dehors du polygone, revenir en arrière d'une étape
  • Faire une géométrie pour l'arbre centré sur ce point aléatoire
  • Si cela chevauche un arbre placé existant (ST_Overlaps), revenez au début
  • Ajouter un arbre au point
  • Revenir en arrière pour commencer

Je ne peux pas garantir que cela donnera l'optimum global, vous auriez besoin d'un algorithme de «cercle d'emballage» pour cela (comme d'autres l'ont mentionné).

Il continuera indéfiniment, vous devrez donc mettre du code pour décider quand quitter, par exemple

  • lorsque la superficie combinée d'arbres placés est un certain pourcentage de la superficie du polygone
  • lorsqu'il faut plus de N itérations pour trouver un arbre sans chevauchement.

Selon Circle Packing sur Wikipedia, la meilleure densité d'emballage est obtenue avec une grille hexagonale. Il pourrait être possible de créer une telle grille en utilisant MMQGIS, dont l'espacement est basé sur la taille de vos arbres, qui je suppose sont identiques. Placer ensuite un arbre sur chaque sommet. Mais alors, vous avez le problème de savoir où placer la grille pour maximiser le nombre d'arbres.

Steven Kay
la source