Générer des points situés à l'intérieur du polygone

30

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.

user2024
la source
3
Au contraire, le temps est prévisible. Il est proportionnel au rapport de la zone d'étendue du polygone divisé par la zone du polygone, multiplié par le temps nécessaire pour générer et tester un seul point. Le temps varie un peu, mais la variation est proportionnelle à la racine carrée du nombre de points. Pour les nombres importants, cela devient sans conséquence. Brisez les polygones tortueux en morceaux plus compacts si nécessaire pour réduire ce rapport de surface à une valeur faible. Seuls les polygones fractals vous causeront des ennuis, mais je doute que vous les ayez!
whuber
3
doublon possible de points
Pablo
@Pablo: bonnes trouvailles. Cependant, ces deux questions sont spécifiques au logiciel et concernent toutes deux le placement de tableaux réguliers de points dans des polygones, et non des points aléatoires
whubber
d'accord avec la différence plus grande entre les points aléatoires et la génération régulière de points dans un polygone.
Mapperz

Réponses:

20

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.)

Dan S.
la source
2
+1 Simple et efficace. Il convient de souligner que des points uniformément aléatoires peuvent être générés dans un triangle sans rejet du tout, car il existe des mappages préservant la zone (facilement calculés) entre n'importe quel triangle et un triangle rectangle isocèle, qui est un demi-carré, disons la moitié où la coordonnée y dépasse la coordonnée x. Générez deux coordonnées aléatoires et triez-les pour obtenir un point aléatoire dans le triangle isocèle, puis mappez-le sur le triangle d'origine.
whuber
+1 J'aime beaucoup la discussion des coordonnées trilinéaires référencées par l'article que vous citez. Je suppose que cela se prêterait à une sphère dont la surface est représentée comme une tesselation de triangles. Sur un plan projeté, ce ne serait pas une distribution vraiment aléatoire, n'est-ce pas?
Kirk Kuykendall
@whuber - +1 de retour sur vous. Une autre façon (dans le lien, mais ils l'ont agité à la main) est de refléter les points rejetés du quadrilatère uniformément échantillonné à travers le bord partagé et de nouveau dans le triangle.
Dan S.22
@Kirk - le lien de citation est un peu anti-utile car il répertorie un tas de mauvaises méthodes d'échantillonnage (non uniformes), y compris les coordonnées trilinéaires, avant la "bonne" voie. Il ne semble pas qu'il existe un moyen direct d'obtenir un échantillonnage uniforme avec des coordonnées trilinéaires. J'aborderais l'échantillonnage uniforme sur toute la sphère en convertissant des vecteurs unitaires aléatoires en 3D en leur équivalent lat / lon, mais c'est juste moi. (Incertain sur l' échantillonnage contraint de triangles sphériques / polygones.) (Également incertain sur l' échantillonnage vraiment uniforme par exemple wgs84: Reprend -il simplement des angles faussera un peu vers les pôles, je pense.)
Dan S.
1
@Dan Pour échantillonner uniformément la sphère, utilisez une projection cylindrique d'aire égale (les coordonnées sont la longitude et le cosinus de latitude). Si vous voulez échantillonner sans utiliser de projection, il y a une belle astuce: générer trois variables normales standard indépendantes (x, y, z) et les projeter au point (R x / n, R y / n, R * z / n ) où n ^ 2 = x ^ 2 + y ^ 2 + z ^ 2 et R est le rayon terrestre. Convertissez en (lat, lon) si nécessaire (en utilisant des latitudes authaliques lorsque vous travaillez sur un sphéroïde). Cela fonctionne parce que cette distribution normale trivariée est sphériquement symétrique. Pour échantillonner des triangles, respectez une projection.
whuber
14

Lorsque vous mettez une balise QGIS sur cette question: l'outil Points aléatoires peut être utilisé avec une couche limite.

entrez la description de l'image ici

Si vous recherchez du code, le code source du plugin sous-jacent devrait vous être utile.

obscur
la source
1
Même 5 ans plus tard, toujours très utile!
Stranded Kid
10

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:

bool PointIsInGeometry(PointCollection points, MapPoint point)
{
int i;
int j = points.Count - 1;
bool output = false;

for (i = 0; i < points.Count; i++)
{
    if (points[i].X < point.X && points[j].X >= point.X || points[j].X < point.X && points[i].X >= point.X)
    {
        if (points[i].Y + (point.X - points[i].X) / (points[j].X - points[i].X) * (points[j].Y - points[i].Y) < point.Y)
        {
            output = !output;
        }
    }
    j = i;
}
return output;
}
Dan Walton
la source
10

Il existe de bonnes bibliothèques qui font le gros du travail pour vous.

Exemple utilisant [shapely] [1] en python.

import random
from shapely.geometry import Polygon, Point

def get_random_point_in_polygon(poly):
     minx, miny, maxx, maxy = poly.bounds
     while True:
         p = Point(random.uniform(minx, maxx), random.uniform(miny, maxy))
         if poly.contains(p):
             return p

p = Polygon([(0, 0), (0, 2), (1, 1), (2, 2), (2, 0), (1, 1), (0, 0)])
point_in_poly = get_random_point_in_polygon(mypoly)

Ou utilisez .representative_point()pour obtenir un point dans l'objet (comme mentionné par Dain):

Renvoie un point calculé à moindre coût qui se trouve à l'intérieur de l'objet géométrique.

poly.representative_point().wkt
'POINT (-1.5000000000000000 0.0000000000000000)'

  [1]: https://shapely.readthedocs.io
monkut
la source
2
Ne devrait-il pas provenir de l'import shapely.geometry ...?
PyMapr
1
Vous pouvez également utiliser la representative_pointméthode: shapely.readthedocs.io/en/latest/…
dain
6

Si R est une option, voir ?spsampledans le sppackage. Les polygones peuvent être lus à partir de n'importe quel format pris en charge par GDAL intégré au package rgdal, puis spsamplefonctionnent directement sur l'objet importé avec une variété d'options d'échantillonnage.

mdsumner
la source
+1 - Puisque R est open source si l'on veut répliquer, vous pouvez toujours aller dans la source pour voir comment cela se fait. Pour les modèles de points, on peut également être intéressé par les outils de simulation dans le package spatstat.
Andy W
5

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):

Area:        Return the area of a polygon (0 for an empty polygon).
BoundingBox: Return the bounding box (extent) of a polygon.
Width:       Return the width of a rectangle.
Height:      Return the height of a rectangle.
Left:        Split a rectangle into two halves and return the left half.
Right:       ... returning the right half.
Top:         ... returning the top half.
Bottom:      ... returning the bottom half.
Clip:        Clip a polygon to a rectangle.
RandomPoint: Return a random point in a rectangle.
Search:      Search a sorted list for a target value.  Return the index  
             of the last element less than the target.
In:          Test whether a point is inside a polygon.

Ils sont tous disponibles dans presque tous les environnements de programmation SIG ou graphiques (et faciles à coder sinon). Clipne doit pas renvoyer de polygones dégénérés (c'est-à-dire ceux avec une zone nulle).

La procédure SimpleRandomSampleobtient efficacement une liste de points répartis aléatoirement dans un polygone. C'est un emballage pour SRS, 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.

Procedure SimpleRandomSample(P:Polygon, N:Integer) {
    U = Sorted list of N independent uniform values between 0 and 1
    Return SRS(P, BoundingBox(P), U)
}

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.

Procedure SRS(P:Polygon, B:Rectangle, U:List) {
    N = Length(U)
    If (N == 0) {Return empty list}
    aP = Area(P)
    If (aP <= 0) {
        Error("Cannot sample degenerate polygons.")
        Return empty list
    }
    t = 2
    If (aP*t < Area(B)) {
        # Cut P into pieces
        If (Width(B) > Height(B)) {
            B1 = Left(B); B2 = Right(B)
        } Else {
            B1 = Bottom(B); B2 = Top(B)
        }
        P1 = Clip(P, B1); P2 = Clip(P, B2)
        K = Search(U, Area(P1) / aP)
        V = Concatenate( SRS(P1, B1, U[1::K]), SRS(P2, B2, U[K+1::N]) )
    } Else {
        # Sample P
        V = empty list
        maxIter = t*N + 5*Sqrt(t*N)
        While(Length(V) < N and maxIter > 0) {
            Decrement maxIter
            Q = RandomPoint(B)
            If (Q In P) {Append Q to V}
        }
       If (Length(V) < N) {
            Error("Too many iterations.")
       }
    }
    Return V
}
whuber
la source
2

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

V_i, i={1,..,N}

Générer ensuite aléatoirement N poids convexes

 w_1,w_2,..,w_N such that  w_i = 1; w_i>=0

Le point échantillonné au hasard est alors donné par

Y=  w_i*V_i

Il peut y avoir différentes manières d'échantillonner N poids convexes

  • Choisissez N-1 nombres uniformément au hasard dans une plage (sans remplacement), triez-les et normalisez les N intervalles entre eux pour obtenir les poids.
  • Vous pouvez également échantillonner à partir de la distribution de Dirichlet qui est souvent utilisée comme un conjugué avant pour la distribution multinomiale, qui est similaire aux poids convexes dans votre cas.

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.

Algoseer
la source
2

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.

Génération de points aléatoires dans des polygones sélectionnés

markusN
la source
1
Rappel obligatoire que les codes postaux sont des lignes, pas des polygones.
Richard
Peux-tu élaborer? Pour moi aussi ici, il se réfère aux domaines: en.wikipedia.org/wiki/ZIP_Code#Primary_state_prefixes
markusN
Bien sûr: les codes postaux font référence à des bureaux de poste particuliers et à leurs itinéraires de livraison du courrier. Par conséquent, les codes postaux sont des lignes et non des polygones. Ils peuvent se chevaucher, contenir des trous et ne couvrent pas nécessairement l'ensemble des États-Unis ou un État donné. Les utiliser pour diviser la zone est dangereux pour cette raison. Les unités de recensement (comme les groupes de blocs) sont un meilleur choix. Voir aussi: ceci et cela .
Richard
1
Merci! Cela dépend probablement aussi du pays, voir par exemple en.wikipedia.org/wiki/Postal_codes_in_Germany - cependant, les codes postaux ne sont pas mon sujet principal, je voulais juste illustrer et répondre à la question originale "Générer des points qui se trouvent à l'intérieur du polygone" plutôt que discuter des définitions de code postal qui est OT ici :-)
markusN
1
A noté sur les deux points. Je devrais probablement faire une petite entrée de blog pour que je puisse le dire plus succinctement la prochaine fois :-)
Richard
1

Lien de réponse

/gis//a/307204/103524

Trois algorithmes utilisant différentes approches.

Lien Git Repo

  1. Voici une approche simple et optimale, utilisant la distance réelle des coordonnées des directions x et y. L'algorithme interne utilise le WGS 1984 (4326) et la transformation des résultats en SRID inséré.

Fonction ================================================= ==================

CREATE OR REPLACE FUNCTION public.I_Grid_Point_Distance(geom public.geometry, x_side decimal, y_side decimal)
RETURNS public.geometry AS $BODY$
DECLARE
x_min decimal;
x_max decimal;
y_max decimal;
x decimal;
y decimal;
returnGeom public.geometry[];
i integer := -1;
srid integer := 4326;
input_srid integer;
BEGIN
CASE st_srid(geom) WHEN 0 THEN
    geom := ST_SetSRID(geom, srid);
        ----RAISE NOTICE 'No SRID Found.';
    ELSE
        ----RAISE NOTICE 'SRID Found.';
END CASE;
    input_srid:=st_srid(geom);
    geom := st_transform(geom, srid);
    x_min := ST_XMin(geom);
    x_max := ST_XMax(geom);
    y_max := ST_YMax(geom);
    y := ST_YMin(geom);
    x := x_min;
    i := i + 1;
    returnGeom[i] := st_setsrid(ST_MakePoint(x, y), srid);
<<yloop>>
LOOP
IF (y > y_max) THEN
    EXIT;
END IF;

CASE i WHEN 0 THEN 
    y := ST_Y(returnGeom[0]);
ELSE 
    y := ST_Y(ST_Project(st_setsrid(ST_MakePoint(x, y), srid), y_side, radians(0))::geometry);
END CASE;

x := x_min;
<<xloop>>
LOOP
  IF (x > x_max) THEN
      EXIT;
  END IF;
    i := i + 1;
    returnGeom[i] := st_setsrid(ST_MakePoint(x, y), srid);
    x := ST_X(ST_Project(st_setsrid(ST_MakePoint(x, y), srid), x_side, radians(90))::geometry);
END LOOP xloop;
END LOOP yloop;
RETURN
ST_CollectionExtract(st_transform(ST_Intersection(st_collect(returnGeom), geom), input_srid), 1);
END;
$BODY$ LANGUAGE plpgsql IMMUTABLE;

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 ================================================= ===================== entrez la description de l'image ici

  1. 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.

    1. Variable séparée pour les directions x et y pour la taille des pixels,
    2. Nouvelle variable pour calculer la distance en sphéroïde ou ellipsoïde.
    3. Saisissez n'importe quel SRID, transformez la fonction Geom dans l'environnement de travail de Spheroid ou Ellipsoid Datum, puis appliquez la distance de chaque côté, obtenez le résultat et transformez-le en SRID d'entrée.

Fonction ================================================= ==================

CREATE OR REPLACE FUNCTION I_Grid_Point(geom geometry, x_side decimal, y_side decimal, spheroid boolean default false)
RETURNS SETOF geometry AS $BODY$ 
DECLARE
x_max decimal; 
y_max decimal;
x_min decimal;
y_min decimal;
srid integer := 4326;
input_srid integer; 
BEGIN
CASE st_srid(geom) WHEN 0 THEN
  geom := ST_SetSRID(geom, srid);
  RAISE NOTICE 'SRID Not Found.';
    ELSE
        RAISE NOTICE 'SRID Found.';
    END CASE;

    CASE spheroid WHEN false THEN
        RAISE NOTICE 'Spheroid False';
        srid := 4326;
        x_side := x_side / 100000;
        y_side := y_side / 100000;
    else
        srid := 900913;
        RAISE NOTICE 'Spheroid True';
    END CASE;
    input_srid:=st_srid(geom);
    geom := st_transform(geom, srid);
    x_max := ST_XMax(geom);
    y_max := ST_YMax(geom);
    x_min := ST_XMin(geom);
    y_min := ST_YMin(geom);
RETURN QUERY
WITH res as (SELECT ST_SetSRID(ST_MakePoint(x, y), srid) point FROM
generate_series(x_min, x_max, x_side) as x,
generate_series(y_min, y_max, y_side) as y
WHERE st_intersects(geom, ST_SetSRID(ST_MakePoint(x, y), srid))
) select ST_TRANSFORM(ST_COLLECT(point), input_srid) from res;
END;
$BODY$ LANGUAGE plpgsql IMMUTABLE STRICT;

Utilisez-le avec une simple requête.

SELECT I_Grid_Point(geom, 22, 15, false) from polygons;

Résultat ================================================= ==================entrez la description de l'image ici

  1. Fonction basée sur un générateur en série.

Fonction ================================================= =================

CREATE OR REPLACE FUNCTION I_Grid_Point_Series(geom geometry, x_side decimal, y_side decimal, spheroid boolean default false)
RETURNS SETOF geometry AS $BODY$
DECLARE
x_max decimal;
y_max decimal;
x_min decimal;
y_min decimal;
srid integer := 4326;
input_srid integer;
x_series DECIMAL;
y_series DECIMAL;
BEGIN
CASE st_srid(geom) WHEN 0 THEN
  geom := ST_SetSRID(geom, srid);
  RAISE NOTICE 'SRID Not Found.';
    ELSE
        RAISE NOTICE 'SRID Found.';
    END CASE;

    CASE spheroid WHEN false THEN
        RAISE NOTICE 'Spheroid False';
    else
        srid := 900913;
        RAISE NOTICE 'Spheroid True';
    END CASE;
    input_srid:=st_srid(geom);
    geom := st_transform(geom, srid);
    x_max := ST_XMax(geom);
    y_max := ST_YMax(geom);
    x_min := ST_XMin(geom);
    y_min := ST_YMin(geom);

    x_series := CEIL ( @( x_max - x_min ) / x_side);
    y_series := CEIL ( @( y_max - y_min ) / y_side );
RETURN QUERY
SELECT st_collect(st_setsrid(ST_MakePoint(x * x_side + x_min, y*y_side + y_min), srid)) FROM
generate_series(0, x_series) as x,
generate_series(0, y_series) as y
WHERE st_intersects(st_setsrid(ST_MakePoint(x*x_side + x_min, y*y_side + y_min), srid), geom);
END;
$BODY$ LANGUAGE plpgsql IMMUTABLE STRICT;

Utilisez-le avec une simple requête.

SELECT I_Grid_Point_Series(geom, 22, 15, false) from polygons; Résultat ================================================= =========================

entrez la description de l'image ici

Muhammad Imran Siddique
la source