Cómo generar un polígono convexo al azar?

Question

Estoy tratando de idear un método para generar polígonos convexos 2D aleatorios. Debe tener las siguientes propiedades:

• Las coordenadas deben ser enteros;
• el polígono debe estar dentro de un cuadrado con esquinas (0, 0) y (C, C), donde se da C;
• el polígono debe tener el número de vértices cerca de un número dado N.

Por ejemplo, generar polígonos aleatorios que tienen 10 vértices y se encuentran dentro cuadrados x [0..100] [0..100] .

Lo que hace que esta tarea sea difícil, es el hecho de que las coordenadas deben ser números enteros.

El enfoque que probé fue para generar conjunto aleatorio de puntos en la plaza determinada y calcular la envoltura convexa de estos puntos. Pero el casco convexo resultante es muy pequeño vértices en comparación con N.

¿Alguna idea?

Answer 1

Esto no es del todo completo, pero puede darte algunas ideas.

Bail out si N < 3. Genera un círculo unitario con N vértices y gíralo al azar [0..90] grados.

extruir aleatoriamente cada vértice hacia el exterior desde el origen, y utilizar el signo del producto transversal entre cada par de vértices adyacentes y el origen para determinar convexidad. Este es el paso donde hay intercambios entre velocidad y calidad.

Después de conseguir sus vértices creados, encontrar el vértice con la mayor magnitud desde el origen. Divida cada vértice por esa magnitud para normalizar el polígono, y luego escale la copia de seguridad por (C/2). Traduce a (C/2, C/2) y vuelve a convertir en entero.

Answer 2

Un simple algoritmo sería:

1. de inicio con la línea al azar (un dos vértices y dos bordes polígono)
2. Tomar al azar borde E del polígono
3. hacer nuevos punto aleatorio P en este borde
4. adoptar una línea L perpendicular a e de pasar por el punto P. mediante el cálculo de intersección entre la línea T y líneas definidas por los dos bordes adyacentes a e, se calcula el desplazamiento de P máximo cuando la convexidad no está roto.
5. Compense el punto P aleatoriamente en ese rango.
6. Si no es suficientes puntos, repetir de 2.

Answer 3

Su enfoque inicial es correcta - el cálculo de la envolvente convexa es la única manera de satisfacer la aleatoriedad, convexidad y integerness.

La única manera que puedo pensar en la optimización de su algoritmo para obtener más "puntos" a cabo es mediante la organización de ellos alrededor de un círculo en lugar de forma completamente aleatoria. Tus puntos deberían estar más cerca de los "bordes" de tu cuadrado que cerca del centro. En el centro, la probabilidad debería ser ~ 0, ya que el polígono debe ser convexo.

Una opción sencilla sería la configuración de un radio mínimo de puntos que aparezcan - tal vez C/2 o C * 0.75.Calcule el centro del cuadrado C, y si un punto está demasiado cerca, aléjelo del centro hasta que se alcance una distancia mínima.

Answer 4

Este es el algoritmo más rápido que conozco que genera cada polígono convexo con la misma probabilidad. La salida tiene exactamente N vértices, y el tiempo de ejecución es O (N log N), por lo que puede generar incluso grandes polígonos muy rápidamente.

• generar dos listas, X y Y, de N enteros aleatorios entre 0 y C. Asegúrese de que no hay duplicados.
• Ordenar X y Y y almacenar sus elementos máximos y mínimos.
• Divida al azar los otros elementos (no máximo o mínimo) en dos grupos: X1 y X2, y Y1 y Y2.
• Vuelva a insertar los elementos mínimo y máximo al principio y al final de estas listas (minX al comienzo de X1 y X2, maxX al final, etc.).
• Encuentra las diferencias consecutivas (X1[i + 1] - X1[i]), invirtiendo el orden para el segundo grupo (X2[i] - X2[i + 1]). Almacénelos en las listas XVec y YVec.
• Aleatorice (aleatorio) YVec y trate cada par XVec[i] y YVec[i] como un vector 2D.
• Ordene estos vectores por ángulo y colóquelos de extremo a extremo para formar un polígono.
• Mueva el polígono a las coordenadas mínimas y máximas originales.

Una animación e implementación de Java está disponible aquí: Generating Random Convex Polygons.

Este algoritmo se basa en un documento de Pavel Valtr: "Probability that n random points are in convex position." Discreto & Geometría computacional 13.1 (1995): 637-643.