Algoritmo para generar polígono 2D aleatorio

Question

No estoy seguro de cómo abordar este problema. No estoy seguro de cuán compleja es una tarea. Mi objetivo es tener un algoritmo que genere cualquier polígono. Mi único requisito es que el polígono no sea complejo (es decir, que los lados no se crucen). Estoy usando Matlab para hacer las matemáticas, pero cualquier cosa abstracta es bienvenida.

¿Alguna ayuda/dirección?

EDIT:

Estaba pensando más de código que podría generar cualquier polígono incluso cosas como esta:

Answer 1

Nota: He actualizado mi respuesta con una solución que simplemente toma como entrada un número deseado de lados del polígono, en lugar de un par de "números mágicos" no intuitivas al igual que lo había hecho antes ...

Hay una clara forma de hacer lo que quiere mediante el aprovechamiento de las clases de MATLAB DelaunayTri y TriRep y los diversos métodos que emplean para el manejo de mallas triangulares. El código siguiente sigue estos pasos para crear un arbitraria simple polygon:

• generar un número de puntos al azar igual al número deseado de lados más un factor de dulce de azúcar. El factor Fudge asegura que, independientemente del resultado de la triangulación, deberíamos tener suficientes facetas para poder recortar la malla triangular a un polígono con el número deseado de lados.

• Crea una triangulación Delaunay de los puntos, lo que da como resultado un convex polygon que se construye a partir de una serie de facetas triangulares.

• Si el límite de la triangulación tiene más bordes que los deseados, elija una faceta triangular aleatoria en el borde que tiene un vértice único (es decir, el triángulo comparte un borde con el resto de la triangulación). La eliminación de esta faceta triangular reducirá el número de bordes límite.

• Si el límite de la triangulación tiene menos bordes que los deseados, o el paso anterior no pudo encontrar un triángulo para eliminar, elija una faceta triangular aleatoria en el borde que tiene solo uno de sus bordes en el límite de triangulación. La eliminación de esta faceta triangular aumentará la cantidad de bordes límite.

• Si no se encuentran facetas triangulares que coincidan con los criterios anteriores, publique una advertencia de que no se pudo encontrar un polígono con el número deseado de lados y devuelva las coordenadas xey del límite de triangulación actual. De lo contrario, continúe eliminando facetas triangulares hasta que se encuentre el número deseado de bordes, luego devuelva las coordenadas xey del límite de triangulación.

Aquí está la función resultante:

function [x, y, dt] = simple_polygon(numSides) 

    if numSides < 3 
     x = []; 
     y = []; 
     dt = DelaunayTri(); 
     return 
    end 

    oldState = warning('off', 'MATLAB:TriRep:PtsNotInTriWarnId'); 

    fudge = ceil(numSides/10); 
    x = rand(numSides+fudge, 1); 
    y = rand(numSides+fudge, 1); 
    dt = DelaunayTri(x, y); 
    boundaryEdges = freeBoundary(dt); 
    numEdges = size(boundaryEdges, 1); 

    while numEdges ~= numSides 
     if numEdges > numSides 
      triIndex = vertexAttachments(dt, boundaryEdges(:,1)); 
      triIndex = triIndex(randperm(numel(triIndex))); 
      keep = (cellfun('size', triIndex, 2) ~= 1); 
     end 
     if (numEdges < numSides) || all(keep) 
      triIndex = edgeAttachments(dt, boundaryEdges); 
      triIndex = triIndex(randperm(numel(triIndex))); 
      triPoints = dt([triIndex{:}], :); 
      keep = all(ismember(triPoints, boundaryEdges(:,1)), 2); 
     end 
     if all(keep) 
      warning('Couldn''t achieve desired number of sides!'); 
      break 
     end 
     triPoints = dt.Triangulation; 
     triPoints(triIndex{find(~keep, 1)}, :) = []; 
     dt = TriRep(triPoints, x, y); 
     boundaryEdges = freeBoundary(dt); 
     numEdges = size(boundaryEdges, 1); 
    end 

    boundaryEdges = [boundaryEdges(:,1); boundaryEdges(1,1)]; 
    x = dt.X(boundaryEdges, 1); 
    y = dt.X(boundaryEdges, 2); 

    warning(oldState); 

end 

y aquí están algunos resultados de la muestra:

Los polígonos generados podría ser tanto convex or concave, pero para un mayor número de lados deseados casi seguramente serán cóncavos. Los polígonos también se generan a partir de puntos generados aleatoriamente dentro de un cuadrado unitario, por lo que los polígonos con un mayor número de lados generalmente se verán como si tuvieran un límite "cuadrático" (como el ejemplo inferior derecho con el polígono de 50 lados). Para modificar esta forma de delimitación general, puede cambiar la forma en que se seleccionan aleatoriamente los puntos x y y iniciales (es decir, desde una distribución gaussiana, etc.).

Answer 2

Para un polígono 2D convexa (totalmente fuera de la parte superior de la cabeza):

1. Generar un radio aleatorio, R

2. Genera N puntos aleatorios en la circunferencia de un círculo de Radio R

3. Mueve el círculo y dibuja líneas rectas entre los puntos adyacentes del círculo.

Answer 3

Como @templatetypedef y @MitchWheat dicho, es fácil hacerlo mediante la generación de N ángulos aleatorios y radios. Es importante ordenar los ángulos; de lo contrario, no será un simple polígono. Tenga en cuenta que estoy usando un buen truco para dibujar curvas cerradas, lo describí en here. Por cierto, los polígonos pueden ser cóncavos.

Tenga en cuenta que todos estos polígonos tendrán forma de estrella. Generar un polígono más general no es un problema simple en absoluto. Solo para darle una idea del problema, consulte http://www.cosy.sbg.ac.at/~held/projects/rpg/rpg.html y http://compgeom.cs.uiuc.edu/~jeffe/open/randompoly.html.

function CreateRandomPoly() 
    figure(); 
    colors = {'r','g','b','k'}; 
    for i=1:5 
     [x,y]=CreatePoly(); 
     c = colors{ mod(i-1,numel(colors))+1}; 
     plotc(x,y,c); 
     hold on; 
    end   
end 

function [x,y]=CreatePoly() 
    numOfPoints = randi(30); 
    theta = randi(360,[1 numOfPoints]); 
    theta = theta * pi/180; 
    theta = sort(theta); 
    rho = randi(200,size(theta)); 
    [x,y] = pol2cart(theta,rho);  
    xCenter = randi([-1000 1000]); 
    yCenter = randi([-1000 1000]); 
    x = x + xCenter; 
    y = y + yCenter;  
end 

function plotc(x,y,varargin) 
    x = [x(:) ; x(1)]; 
    y = [y(:) ; y(1)]; 
    plot(x,y,varargin{:}) 
end 

Answer 4

Tomé la idea de @MitchWheat y @ templatetypedef de los puntos de muestreo en un círculo y lo llevé un poco más lejos.

En mi aplicación necesito poder controlar cuán extraños son los polígonos, es decir, comenzar con polígonos regulares y, a medida que aumenta los parámetros, se vuelven cada vez más caóticos. La idea básica es la establecida por @templatetypedef; camine alrededor del círculo dando un paso angular al azar cada vez, y en cada paso ponga un punto en un radio aleatorio. En las ecuaciones que estoy generar los pasos angulares como

donde theta_i y r_i dar el ángulo y el radio de cada punto con respecto al centro, U (min, max) tira de un número al azar de una distribución uniforme, y N (mu, sigma) extrae un número aleatorio de una distribución gaussiana, y los valores de clip (x, min, max) un valor en un rango. Esto nos da dos parámetros realmente agradables para controlar qué tan salvajes son los polígonos: épsilon al que llamaré irregularidad controla si los puntos están uniformemente espaciados angularmente alrededor del círculo, y sigma que llamaré spikeyness que controla cuánto pueden variar los puntos del círculo de radio r_ave. Si configuras ambas cosas en 0, obtienes polígonos perfectamente regulares, si los levantas, los polígonos se vuelven más locos.

Azoté este rápidamente en Python y tiene cosas como esta:

Aquí está el código Python completo:

import math, random 

def generatePolygon(ctrX, ctrY, aveRadius, irregularity, spikeyness, numVerts) : 
'''Start with the centre of the polygon at ctrX, ctrY, 
    then creates the polygon by sampling points on a circle around the centre. 
    Randon noise is added by varying the angular spacing between sequential points, 
    and by varying the radial distance of each point from the centre. 

    Params: 
    ctrX, ctrY - coordinates of the "centre" of the polygon 
    aveRadius - in px, the average radius of this polygon, this roughly controls how large the polygon is, really only useful for order of magnitude. 
    irregularity - [0,1] indicating how much variance there is in the angular spacing of vertices. [0,1] will map to [0, 2pi/numberOfVerts] 
    spikeyness - [0,1] indicating how much variance there is in each vertex from the circle of radius aveRadius. [0,1] will map to [0, aveRadius] 
    numVerts - self-explanatory 

    Returns a list of vertices, in CCW order. 
    ''' 

    irregularity = clip(irregularity, 0,1) * 2*math.pi/numVerts 
    spikeyness = clip(spikeyness, 0,1) * aveRadius 

    # generate n angle steps 
    angleSteps = [] 
    lower = (2*math.pi/numVerts) - irregularity 
    upper = (2*math.pi/numVerts) + irregularity 
    sum = 0 
    for i in range(numVerts) : 
     tmp = random.uniform(lower, upper) 
     angleSteps.append(tmp) 
     sum = sum + tmp 

    # normalize the steps so that point 0 and point n+1 are the same 
    k = sum/(2*math.pi) 
    for i in range(numVerts) : 
     angleSteps[i] = angleSteps[i]/k 

    # now generate the points 
    points = [] 
    angle = random.uniform(0, 2*math.pi) 
    for i in range(numVerts) : 
     r_i = clip(random.gauss(aveRadius, spikeyness), 0, 2*aveRadius) 
     x = ctrX + r_i*math.cos(angle) 
     y = ctrY + r_i*math.sin(angle) 
     points.append((int(x),int(y))) 

     angle = angle + angleSteps[i] 

    return points 

def clip(x, min, max) : 
    if(min > max) : return x  
    elif(x < min) : return min 
    elif(x > max) : return max 
    else :    return x 

---

@MateuszKonieczny aquí es el código para crear una imagen de una polígono de una lista de vértices.

verts = generatePolygon(ctrX=250, ctrY=250, aveRadius=100, irregularity=0.35, spikeyness=0.2, numVerts=16) 

black = (0,0,0) 
white=(255,255,255) 
im = Image.new('RGB', (500, 500), white) 
imPxAccess = im.load() 
draw = ImageDraw.Draw(im) 
tupVerts = map(tuple,verts) 

# either use .polygon(), if you want to fill the area with a solid colour 
draw.polygon(tupVerts, outline=black,fill=white) 

# or .line() if you want to control the line thickness, or use both methods together! 
draw.line(tupVerts+[tupVerts[0]], width=2, fill=black) 

im.show() 

# now you can save the image (im), or do whatever else you want with it.