Generar puntos que se encuentran dentro del polígono

24

Tengo una función de polígono y quiero poder generar puntos dentro de ella. Necesito esto para una tarea de clasificación.

Generar puntos al azar hasta que uno esté dentro del polígono no funcionaría porque es realmente impredecible el tiempo que lleva.

    
pregunta user2024 22.02.2011 - 19:06

8 respuestas

17

Comience por descomponer el polígono en triángulos, luego puntos dentro de esos . (Para una distribución uniforme, pese cada triángulo por su área).

    
respondido por el Dan S. 22.02.2011 - 20:23
14

Al poner una etiqueta QGIS en esta pregunta: la herramienta Puntos aleatorios se puede usar con una capa límite.

Si está buscando un código, el código fuente del complemento subyacente debería ser de ayuda.

    
respondido por el underdark 24.02.2011 - 13:50
9

Podrías determinar la extensión del polígono, luego restringir la generación de números aleatorios para los valores de X e Y dentro de esas extensiones.

Proceso básico: 1) Determine maxx, maxy, minx, miny de polígonos, vértices, 2) Generar puntos aleatorios utilizando estos valores como límites. 3) Prueba cada punto para la intersección con tu polígono, 4) Deje de generar cuando tenga suficientes puntos que satisfagan la prueba de intersección

Aquí hay un algoritmo (C #) para la prueba de intersección:

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;
}
    
respondido por el Dan Walton 22.02.2011 - 19:10
7

Hay algunas bibliotecas buenas por ahí que hacen la mayor parte del trabajo pesado por ti.

Ejemplo usando shapely en python.

import random
from shapely 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)
    
respondido por el monkut 03.10.2013 - 07:26
5

Si R es una opción, vea ?spsample en el paquete sp . Los polígonos se pueden leer desde cualquier formato compatible con GDAL incorporado en el paquete rgdal, y luego spsample funciona directamente en objetos importados con una variedad de opciones de muestreo.

    
respondido por el mdsumner 24.02.2011 - 11:01
4

Me gustaría ofrecer una solución que requiere muy poco en términos de análisis GIS. En particular, no requiere triangular ningún polígono.

El siguiente algoritmo, dado en pseudocódigo, se refiere a algunas operaciones simples además de las capacidades básicas de manejo de listas (crear, encontrar longitud, agregar, ordenar, extraer listas y concatenar) y generación de flotadores aleatorios en el intervalo [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.

Todos estos están disponibles en casi cualquier entorno de programación de gráficos o GIS (y es fácil de codificar si no). Clip no debe devolver polígonos degenerados (es decir, aquellos con área cero).

El procedimiento SimpleRandomSample obtiene una lista de puntos distribuidos aleatoriamente dentro de un polígono. Es una envoltura para SRS , que rompe el polígono en partes más pequeñas hasta que cada pieza es lo suficientemente compacta como para muestrearla de manera eficiente. Para hacer esto, utiliza una lista precalculada de números aleatorios para decidir cuántos puntos asignar a cada pieza.

SRS se puede "sintonizar" cambiando el parámetro t . Este es el cuadro de límite máximo: relación de área de polígono que se puede tolerar. Hacerlo pequeño (pero mayor que 1) hará que la mayoría de los polígonos se dividan en muchas partes; hacer que sea grande puede hacer que muchos puntos de prueba sean rechazados para algunos polígonos (sinuosos, con astillas o llenos de agujeros). Esto garantiza que el tiempo máximo para muestrear el polígono original es predecible.

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

El siguiente procedimiento se llama a sí mismo recursivamente si es necesario. La misteriosa expresión t*N + 5*Sqrt(t*N) estima de forma conservadora un límite superior sobre cuántos puntos se necesitarán, lo que explica la variabilidad aleatoria. La probabilidad de que esto falle es de solo 0,3 por millón de llamadas a procedimientos. Aumente de 5 a 6 o incluso 7 para reducir esta probabilidad si lo desea.

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
}
    
respondido por el whuber 23.02.2011 - 21:40
2

Si tu polígono es convexo y conoces todos los vértices, deberías considerar hacer una ponderación convexa "aleatoria" de los vértices para muestrear un nuevo punto que se garantiza que se encuentre dentro del casco convexo (polígono en este caso) .

Por ejemplo, digamos que tienes un polígono convexo de N lados con vértices

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

Luego genera aleatoriamente N pesos convexos

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

El punto muestreado aleatoriamente es dado por

Y= ∑ w_i*V_i

Puede haber diferentes maneras de muestrear N convexas

  • Elija números N-1 de manera uniforme y aleatoria dentro de un rango (sin reemplazo), ordénelos y normalice los intervalos N entre ellos para obtener los pesos.
  • También puede tomar muestras de la distribución de Dirichlet, que a menudo se usa como un conjugado antes de la distribución multinomial, que es similar a los pesos convexos en su caso.

Cuando tu polígono no es muy convexo, deberías considerar convertirlo en un casco convexo. Esto debería al menos limitar en gran medida la cantidad de puntos que se encuentran fuera de su polígono.

    
respondido por el algoseer 13.05.2017 - 01:50
1

La tarea es muy fácil de resolver en GRASS GIS (un comando) usando v.random .

Debajo de un ejemplo sobre cómo agregar 3 puntos aleatorios en polígonos seleccionados (aquí, áreas de código postal de la ciudad de Raleigh, NC) desde la página del manual. Al modificar la declaración "donde" de SQL, se pueden seleccionar los polígonos.

    
respondido por el markusN 13.05.2017 - 11:54

Lea otras preguntas en las etiquetas