algorithm - programming - max subarray geeksforgeeks

¿Divide la rejilla(matriz 2D) en partes con formas aleatorias? (3)

Esto es lo que haría: usar el algoritmo de Voronoi. Primero coloque algunos puntos al azar, luego deje que el algoritmo de Voronoi genere las partes. Para tener una idea de cómo se ve, consulta: este applet .

El problema
Quiero dividir una cuadrícula (matriz 2D) en partes con formas aleatorias (piense en las placas tectónicas de la Tierra ).

Los criterios son:

El usuario ingresa el tamaño de la cuadrícula (el programa debe escalar porque podría ser muy grande).
El usuario ingresa el factor de división de la cuadrícula (cuántas partes).
La cuadrícula es una cuadrícula hexagonal de forma rectangular, y está tapada arriba y abajo, se envuelve alrededor de la izquierda y la derecha.
No hay fragmentación de las partes.
Sin partes dentro de otras partes.
No hay piezas pequeñas o súper grandes.
Piezas con forma aleatoria, que no son círculos perfectos o formas serpenteantes.

Mi solución:

Cree un método que pueda acceder / manipular las celdas adyacentes.
Determina aleatoriamente el tamaño de cada parte (la suma de todas las partes es igual al tamaño de la matriz 2D completa).
Complete toda la matriz 2D con el número de identificación de la última pieza.
Para cada parte excepto la última:
Sembrar el número de identificación de la pieza actual en una celda aleatoria de la matriz 2D.
Itere el conjunto completo y almacene la dirección de cada celda adyacente a las celdas ya sembradas con el número de identificación de parte actual.
Extraiga una de las direcciones almacenadas y llene esa celda con el número de identificación de placa actual (para que la pieza comience a formarse).
Repita hasta que se alcance el tamaño de la pieza.

Tenga en cuenta que para evitar partes con largos "brazos" o grandes agujeros en su interior, creé dos matrices de almacenamiento: una para celdas adyacentes a una sola celda con el número de identificación de parte actual y la otra para celdas adyacentes a más de una, luego agoto el último antes que el anterior.

Ejecutar mi solución ofrece lo siguiente:
Tamaño de la rejilla: 200
ancho: 20
altura: 10
Partes: 7

66633333111114444466
00033331111114444466
00003331111114444466
00003331111144444660
00000333111164444660
00000336111664422600
00000336615522222200
00006655555522222200
00006655555552222220
00066655555552222220

Número de parte: 0
Tamaño de la parte: 47

Número de parte: 1
Tamaño de la pieza: 30

Número de parte: 2
Tamaño de la pieza: 26

Número de parte: 3
Tamaño de la pieza: 22

Número de parte: 4
Tamaño de la pieza: 26

Número de parte: 5
Tamaño de la pieza: 22

Número de parte: 6
Tamaño de la pieza: 27

Problemas con mi solución:

La última parte siempre está fragmentada; en el caso anterior, hay tres grupos separados de seis.
El algoritmo se detendrá cuando las piezas se forman en callejones sin salida y no tienen espacio para crecer a su tamaño completo (el algoritmo no permite formar partes sobre otras, a menos que sea la última parte, que se establece sobre la totalidad Arreglo 2D al comienzo).
Si no especifico los tamaños de las piezas antes de formar la matriz 2d, y me limito a especificar el número de piezas y generar aleatoriamente los tamaños de las partes sobre la marcha, esto deja abierta la posibilidad de que se formen pequeñas partes, que también podrían estar allí en absoluto, especialmente cuando la matriz 2D es muy grande. Mi método actual de tamaño de parte limita los tamaños de las partes a entre 10% y 40% del tamaño total de la matriz 2D. Puede estar bien si no especifico los tamaños de las partes si hay alguna forma súper elegante de hacerlo: el único control que tendrá el usuario es el tamaño de la matriz 2d y el número de partes.

Otras ideas:

Forme las partes en cuadrados perfectamente alineados, luego recorra la matriz 2D y permita que cada parte invada aleatoriamente otras partes, combinándolas en formas aleatorias.
Dibuje líneas serpenteantes a través de la cuadrícula y complete los espacios creados, tal vez usando algunas matemáticas como esta: http://mathworld.wolfram.com/PlaneDivisionbyLines.html

Conclusión:
Así que aquí está el problema: soy un programador principiante que no está seguro si estoy abordando este problema de la manera correcta. Puedo crear algunos métodos más de "parche", que cambian las partes fragmentadas juntas, y permiten que las partes formadas salten de los callejones sin salida si se quedan atascadas en ellas, pero se siente desordenado.

¿Cómo abordarías este problema? ¿Hay alguna matemática sexy que pueda usar para simplificar las cosas tal vez?

Gracias

Hace algunos meses hice algo similar para un juego, aunque era una cuadrícula rectangular en lugar de una cuadrícula hexagonal. Aún así, la teoría es la misma, y surgió con agradables áreas contiguas de aproximadamente el mismo tamaño: algunas eran más grandes, otras más pequeñas, pero ninguna era demasiado pequeña o demasiado grande. YMMV.

Haga una serie de punteros a todos los espacios en su cuadrícula. Mezcle la matriz.
Asigne los primeros N identificadores - 1, 2, 3, etc.
Hasta que la matriz indique que no hay espacios que no tienen ID,
Itere a través de la matriz en busca de espacios que no tienen ID
Si el espacio tiene vecinos en la cuadrícula que TIENEN ID, asigne el espacio al ID de una selección aleatoria ponderada de los ID de sus vecinos.
Si no tiene vecinos con identificaciones, salte a la siguiente.
Una vez que no hay espacios no vacíos, tiene su mapa con áreas suficientemente blobby.

Como Rekin sugirió, un diagrama de Voronoi más algunas perturbaciones aleatorias generalmente harán un buen trabajo, y en un espacio discreto como el que tienes, es relativamente fácil de implementar.

Solo quería dar algunas ideas sobre cómo hacer la perturbación aleatoria. Si lo haces en la resolución final, tomará mucho tiempo o será mínimo. Puede tratar de hacer una perturbación de resolución múltiple. Por lo tanto, comience con una cuadrícula bastante pequeña, genere al azar, calcule el diagrama de Voronoi. Luego, altere aleatoriamente los bordes, algo así como, para cada par de celdas adyacentes con regiones diferentes, empuje la región de una manera u otra. Es posible que deba ejecutar un postproceso para asegurarse de que no tenga islas diminutas. Un simple relleno sanitario funcionará.

Luego crea una cuadrícula que sea dos veces el tamaño (en cada dirección) y copia tus regiones. Probablemente puedas usar el vecino más cercano. Luego vuelva a perturbar los bordes y repita hasta que alcance la resolución deseada.