J'ai une entité polygonale et je veux pouvoir générer des points à l'intérieur. J'en ai besoin pour une tâche de classification.
Générer des points aléatoires jusqu'à ce que l'on soit à l'intérieur du polygone ne fonctionnerait pas, car le temps que cela prend est vraiment imprévisible.
Réponses:
Commencez par décomposer le polygone en triangles, puis générez des points à l'intérieur de ceux-ci . (Pour une distribution uniforme, pondérez chaque triangle par sa surface.)
la source
Lorsque vous mettez une balise QGIS sur cette question: l'outil Points aléatoires peut être utilisé avec une couche limite.
Si vous recherchez du code, le code source du plugin sous-jacent devrait vous être utile.
la source
Vous pouvez déterminer l'étendue du polygone, puis contraindre la génération de nombres aléatoires pour les valeurs X et Y dans ces étendues.
Processus de base: 1) Déterminer maxx, maxy, minx, miny des sommets du polygone, 2) Générer des points aléatoires en utilisant ces valeurs comme limites 3) Tester chaque point pour l'intersection avec votre polygone, 4) Arrêter de générer lorsque vous avez suffisamment de points satisfaisant l'intersection tester
Voici un algorithme (C #) pour le test d'intersection:
la source
Il existe de bonnes bibliothèques qui font le gros du travail pour vous.
Exemple utilisant [shapely] [1] en python.
Ou utilisez
.representative_point()
pour obtenir un point dans l'objet (comme mentionné par Dain):la source
representative_point
méthode: shapely.readthedocs.io/en/latest/…Si R est une option, voir
?spsample
dans lesp
package. Les polygones peuvent être lus à partir de n'importe quel format pris en charge par GDAL intégré au package rgdal, puisspsample
fonctionnent directement sur l'objet importé avec une variété d'options d'échantillonnage.la source
Je voudrais proposer une solution qui nécessite très peu en termes d'analyse SIG. En particulier, il ne nécessite la triangulation d'aucun polygone.
L'algorithme suivant, donné en pseudocode, fait référence à quelques opérations simples en plus des capacités de gestion de liste de base (créer, trouver la longueur, ajouter, trier, extraire des sous-listes et concaténer) et la génération de flottants aléatoires dans l'intervalle [0, 1):
Ils sont tous disponibles dans presque tous les environnements de programmation SIG ou graphiques (et faciles à coder sinon).
Clip
ne doit pas renvoyer de polygones dégénérés (c'est-à-dire ceux avec une zone nulle).La procédure
SimpleRandomSample
obtient efficacement une liste de points répartis aléatoirement dans un polygone. C'est un emballage pourSRS
, qui divise le polygone en petits morceaux jusqu'à ce que chaque morceau soit suffisamment compact pour être échantillonné efficacement. Pour ce faire, il utilise une liste précalculée de nombres aléatoires pour décider du nombre de points à allouer à chaque pièce.Le SRS peut être "réglé" en changeant le paramètre
t
. Il s'agit du rapport maximum du cadre de délimitation: surface surfacique qui peut être toléré. Le rendre petit (mais supérieur à 1) provoquera la division de la plupart des polygones en plusieurs morceaux; l'agrandir peut entraîner le rejet de nombreux points d'essai pour certains polygones (sinueux, avec des éclats ou plein de trous). Cela garantit que la durée maximale d'échantillonnage du polygone d'origine est prévisible.La procédure suivante s'appelle récursivement si nécessaire. L'expression mystérieuse
t*N + 5*Sqrt(t*N)
estime prudemment une limite supérieure du nombre de points nécessaires, ce qui tient compte de la variabilité aléatoire. La probabilité que cela échoue n'est que de 0,3 par million d'appels de procédure. Augmentez de 5 à 6 ou même 7 pour réduire cette probabilité si vous le souhaitez.la source
Si votre polygone est convexe et que vous connaissez tous les sommets, vous voudrez peut-être envisager de faire une pondération convexe "aléatoire" des sommets pour échantillonner un nouveau point qui est garanti de se trouver à l'intérieur de la coque convexe (polygone dans ce cas).
Par exemple, disons que vous avez un polygone convexe à N côtés avec des sommets
Générer ensuite aléatoirement N poids convexes
Le point échantillonné au hasard est alors donné par
Il peut y avoir différentes manières d'échantillonner N poids convexes
Lorsque votre polygone n'est pas très sévèrement non convexe, vous pouvez d'abord envisager de le convertir en coque convexe. Cela devrait au moins limiter le nombre de points se trouvant en dehors de votre polygone dans une large mesure.
la source
La tâche est très facile à résoudre dans GRASS GIS (une commande) en utilisant v.random .
Ci-dessous un exemple sur la façon d'ajouter 3 points aléatoires dans les polygones sélectionnés (ici les zones de code postal de la ville de Raleigh, NC) à partir de la page de manuel. En modifiant l'instruction SQL "where", le ou les polygones peuvent être sélectionnés.
la source
Lien de réponse
/gis//a/307204/103524
Trois algorithmes utilisant différentes approches.
Lien Git Repo
Fonction ================================================= ==================
Utilisez la fonction avec une requête simple, la géométrie doit être valide et polygone, multi-polygones ou enveloppe
SELECT I_Grid_Point_Distance(geom, 50, 61) from polygons limit 1;
Résultat ================================================= =====================
Deuxième fonction basée sur l' algorithme de Nicklas Avén . J'ai essayé de gérer n'importe quel SRID.
J'ai appliqué les changements suivants dans l'algorithme.
Fonction ================================================= ==================
Utilisez-le avec une simple requête.
SELECT I_Grid_Point(geom, 22, 15, false) from polygons;
Résultat ================================================= ==================
Fonction ================================================= =================
Utilisez-le avec une simple requête.
SELECT I_Grid_Point_Series(geom, 22, 15, false) from polygons;
Résultat ================================================= =========================la source