Generar áreas de igual tamaño en polígonos.

8

Estoy buscando una lógica de pseudocódigo que encuentre náreas de igual tamaño en un polígono dado. No debe haber espacio entre o fuera de las áreas coincidentes. Se debe devolver la primera coincidencia de áreas válida.

Asumiendo el siguiente polígono [2,2, 3,1, 5,1, 5,4, 4,5, 2,3]como entrada:

ingrese la descripción de la imagen aquí

... y 3como parámetro, una salida válida podría ser [ [2,2, 3,2, 3,3, 4,3, 4,5, 2,3], [2,2, 3,1, 5,1, 4,2, 4,3, 3,3, 3,2], [4,5, 4,2, 5,1, 5,4] ]:

ingrese la descripción de la imagen aquí

Otra salida válida con parámetro 3es [ [3,4, 3,3, 4,3, 4,2, 3,2, 3,1, 2,2, 2,3], [4,3, 4,2, 3,2, 3,1, 5,1, 5,3], [3,4, 3,3, 5,3, 5,4, 4,5] ]:

ingrese la descripción de la imagen aquí

Tenga en cuenta que las áreas no tienen que compartir el mismo punto central. Puede ocurrir que una o más áreas caigan justo entre otras áreas dentro del polígono.

Aquí hay otro ejemplo de entrada / salida de muestra.

Asumiendo el siguiente polígono [1,3, 1,1, 7,1, 7,2, 8,2, 8,3, 5,6, 4,6]como entrada:

ingrese la descripción de la imagen aquí

..y 5como parámetro una salida válida podría ser [ [1,3, 1,1, 3,1, 3,2, 4,3, 3,4, 3,3], [3,2, 3,1, 7,1, 7,2, 6,2, 6,3, 5,3, 5,2], [6,2, 8,2, 8,3, 6,5, 5,5, 5,4, 6,4], [1,3, 3,3, 3,4, 5,5, 6,4, 6,5, 7,5, 6,6, 5,6], [3,4, 4,3, 3,2, 5,2, 5,3, 6,3, 6,4, 5,4, 4,5] ]:

ingrese la descripción de la imagen aquí

Se hacen los siguientes supuestos:

  • la dirección de todas las fronteras es divisible por 45

  • las coordenadas enteras se usan para todos los polígonos

  • el área entera del polígono de entrada siempre es divisible por n

  • todos los polígonos pueden ser tanto convexas o cóncavas las

  • solucionable, lo que significa que las náreas pueden encajar correctamente en el polígono dado

Sergey Lukin
fuente
1
Compartir su investigación ayuda a todos . Cuéntanos qué has probado y por qué no satisfizo tus necesidades. Esto demuestra que te has tomado el tiempo para tratar de ayudarte a ti mismo, nos salva de reiterar respuestas obvias y, sobre todo, te ayuda a obtener una respuesta más específica y relevante. También vea Cómo preguntar
mosquito
¿Te refieres a áreas de "igual tamaño", no "igualmente distribuidas", supongo?
Doc Brown
@DocBrown tienes razón, sabía que me equivocaría aquí. Definitivamente quise decir de igual tamaño. Corregido
Sergey Lukin
¿Son sus polígonos de entrada siempre convexos, como en su ejemplo?
Doc Brown
@DocBrown Cualquier formato funcionará realmente, simplemente elegí este formato porque lo vi en algún lugar y supuse que es el principal, pero me encantaría que me corrijan.
Sergey Lukin

Respuestas:

6

No solucionable Probé varios métodos hasta que me di cuenta de que no se podía hacer.

Asuma una forma con área 4, que debe dividirse en 2 partes con área 2 cada una:

cuadrícula

El triángulo y el cuadrado más a la izquierda deben ser parte de la forma 1, pero necesita otro triángulo. El único lugar que podría tomarse es el cuadrado a la derecha, pero luego el resto se divide en dos regiones.

NiklasJ
fuente
2
No se puede resolver en general, por supuesto, pero supongo que el OP podría estar interesado en un algoritmo que resuelva el problema para cada caso en el que se puede resolver, y de lo contrario da como resultado que no se puede resolver ;-) Le dio un voto a favor, tampoco.
Doc Brown
Buena atrapada. No lo pensé. Podríamos agregar una suposición de que el área es válida siempre que consista en coordenadas de ruta que no sean interceptadas por otras áreas, lo que resultaría en [ [0,1, 2,1, 2,2, 3,2, 2,3, 2,2 1,2], [2,2, 2,0, 3,0, 3,2] ] aceptar el hecho de que se lanza una excepción en caso de que la función repita todas las variantes y no encuentre un partido. ¿Qué piensas?
Sergey Lukin
En aras de la simplicidad, he agregado la suposición de que solo se pasan como entradas las variaciones solucionables de polígonos y el número de áreas. Mira mi edición. Gracias
Sergey Lukin
6

Como dije en mi comentario a la respuesta de Doc Browns (por lo demás excelente), hay una cuestión de elección de la división cuadrado-> triángulo que hace que sea un poco más difícil usar un algoritmo. Además, no tiene que hacerlo en serie, pero puede hacerlo en paralelo, como muestran algunas de mis sugerencias.

Hice varios enfoques heurísticos al principio.

Voronoi: Elija N puntos (coordenadas no enteros) en la forma, crear un mapa de Voronoi. Deje que los puntos se atraigan y se repelen entre sí con respecto a su área (atrae demasiado, repele demasiado pequeño).

Útil para A / N grandes, fácil de caer en máximos locales.

Método de círculo: el objetivo es eliminar áreas problemáticas y luego continuar usando otro método.

Elija un punto (no entero) en el interior y un radio r. El interior menos el círculo creará k subregiones desconectadas. Si alguna de las subregiones es de tamaño A / n, elimínela. Además, si alguno es 2 * A / n, debería ser fácil dividirlo y eliminarlo también. Baje el radio ligeramente y continúe (posiblemente use alguna búsqueda binaria).

Crecimiento de puntos problemáticos: comience a usar el método que menciona Doc Brown, pero dado que hay dos opciones en la mayoría de los bordes, omita el gráfico y haga crecer cada región en el borde para crear la menor cantidad posible de puntos problemáticos nuevos (puntos problemáticos = solo triángulos compartiendo un borde con el resto de la forma). Por ejemplo, al elegir nuevos vecinos para incluir, agréguelos en orden de convexidad (cóncavo = convexidad negativa)

Crecimiento de la cinta: para áreas casi convexas o convexas. Elija un punto en el borde exterior, haga que una cinta de ancho de unidad siga el borde exterior hasta que tenga la longitud correcta, asegurándose de nunca crear un nuevo punto desconectado. Si es necesario, omita los últimos triángulos y haga que crezca un poco de ancho. Deje que la siguiente cinta siga donde terminó la última hasta que el área final sea del tamaño correcto.

Como un juego u orgánico: Crea N "países". Ponlos en lugares al azar. Déjalos crecer orgánicamente. Cuando se encuentran, el que tiene el área actual más pequeña es el más fuerte y gana el triángulo. Probablemente propenso a máximos locales?

NiklasJ
fuente
3

La estrategia general debe ser eliminar la primera parte del área A / n de su polígono P0 (donde A es el área total), dejándolo con un nuevo polígono P1 del área AA / n. Luego repita esto produciendo un polígono P2, luego P3, y después de n repeticiones, tiene su solución. Tenga en cuenta que es posible en cada paso que no pueda encontrar una pieza tan nueva donde las partes restantes todavía formen un polígono conectado, en el que debe retroceder un paso e intentar encontrar otra pieza, o detener el algoritmo sin un resultado .

Para construir tal pieza de tamaño A / n, comience dividiendo su polígono en "piezas de cuadrícula". Cualquier cuadrícula dentro del polígono forma una pieza así, así como cualquier medio cuadrado en forma de triángulo donde el borde del polígono divide el cuadrado en dos mitades. Puede utilizar una prueba de punto en el polígono para esto, iterar sobre todos los medios cuadrados dentro del cuadro delimitador del polígono y probar si su punto medio está dentro del polígono dado (si ambas partes de un cuadrado están contenidas, uno puede usar el plaza completa en su lugar). Luego, creas un gráfico plano, donde cada una de las piezas define un vértice (con un "área" o "peso" de 1 o 1/2). Los bordes de ese gráfico están dados por las piezas vecinas. Esto reduce su problema geométrico a un problema de gráfico, donde está buscando un sub-gráfico conectado con vértices de peso total A / n, y el gráfico restante todavía está conectado .

El último problema podría resolverse mediante un retrocesoAcercarse. Comience con un vértice que se pueda eliminar del gráfico sin desconectarlo. Puede elegir el vértice al azar, si lo desea, o barajar la lista de todos los vértices al azar una vez, para volver a usar en los siguientes pasos. Ahora intente encontrar un segundo vértice que esté conectado al primero, que pueda eliminarse del gráfico restante sin destruir también su conexión. Si hay múltiples posibilidades, elija una al azar. Para los vértices que representan un cuadrado, también puede permitir una operación de gráfico donde divide el cuadrado en dos triángulos (esto crea nuevos vértices de peso 1/2) de una u otra forma posible. Esto es solo un poco más complicado que simplemente mover un vértice del gráfico original al sub-gráfico, pero no debería ser demasiado difícil.

Repita eso hasta que su subgrafo alcance un peso total A / n, o no encuentre otro vértice. Si ese es el caso, "retroceda" un nivel e intente primero un vértice diferente.

Hay varias formas de optimizar esto, por ejemplo, debe elegir una prueba de conectividad rápida para gráficos. Supongo que encontrará muchos algoritmos para este subproblema, use Google o comience aquí . Puede valer la pena buscar un algoritmo que pueda verificar rápidamente si un gráfico conectado todavía está conectado cuando se elimina un vértice.

Espero que esto ayude.

Doc Brown
fuente
Esto suena exactamente lo que necesitaba. Me he imaginado esta estrategia en teoría y hasta ahora todo tiene sentido para mí, ahora es el momento de ponerla en práctica. Informaré cuando tenga algo que mostrar. Muchas gracias!
Sergey Lukin
Creo que hay un pequeño problema con este enfoque. Para cada cuadrado, hay dos posibles opciones de triángulos. Para verificar realmente todos ellos y garantizar una solución en caso de que haya una, supongo que deberá hacerlo para las 2 ^ n opciones.
NiklasJ
@NiklasJ: tienes razón, mira mi respuesta mejorada que tiene esto en cuenta.
Doc Brown
@SergeyLukin: Cambié un poco mi respuesta para tener en cuenta el comentario de NiklasJ.
Doc Brown