0
354
VisualizaçõesEncuentra el rectángulo más grande que cabe dentro de un polígono
Necesito encontrar el rectángulo más grande que pueda caber dentro de cualquier polígono,
lo que intenté es dividir el svg en la cuadrícula 2d y hacer un bucle en la matriz 2d para ver si la celda de la cuadrícula actual se cruza con el polígono para crear una nueva matriz binaria 2d donde la intersección es 1 más 0
ahora necesito encontrar el rectángulo más grande de esa matriz 2d Y, lo que es más importante, su ubicación
como ejemplo:
si la matriz 2d es así, necesito encontrar el rect más grande en esa matriz y su x1, y1 (inicio i, j) y x2, y2 (final i, j).
1 Respostas
Responde à pergunta0
bueno, puede forzar la ubicación por fuerza bruta y buscar el tamaño que será O(n^6) si n es el tamaño promedio del lado de su mapa en píxeles ...
La ubicación puede acelerarse mediante la búsqueda (aceptando datos no estrictamente ordenados), por ejemplo, así:
lo que llevaría a ~O(n^4.log^2(n)) . Pero tenga cuidado, la búsqueda debe configurarse correctamente para no omitir la solución ... La búsqueda de tamaño también se puede mejorar utilizando una técnica similar a la que hice aquí:
Simplemente use una métrica diferente para crear tablas LUT de posiciones de inicio y fin para cada x e y (4 tablas LUT) que acelerarán la búsqueda que conduce a ~O(n^2.log^2(n)) mientras se crea LUT es O(n^2) . por cierto, las mismas LUT que a veces uso en OCR como aquí (últimas 2 imágenes):
Ahora, el problema con este enfoque es que no puede manejar el polígono cóncavo correctamente, ya que puede haber más bordes por x, y que solo 2. Entonces, para remediarlo, necesitaría tener más LUT y usarlos según la posición en el polígono (dividir el polígono para áreas "convexas")
Entonces, al juntar todo esto, se vería algo como esto:
approx loop (center x) // ~O(log(n)) approx loop (center y) // ~O(log(n)) grow loop (square size to max using) LUT // O(n) { grow loop (x size to max while decreasing original square y size) // O(n) grow loop (y size to max while decreasing original square x size) // O(n) use bigger from the above 2 rectangles } Simplemente no olvide usar el area of polygon / area of rectangle como valor de error de aproximación. Este algoritmo está dando como resultado ~O(n^2.log^2(n)) que no es muy bueno pero aún es factible.
Otra opción es convertir su polígono en cuadrados, y usar técnicas de empaquetamiento en contenedores o gráficos o retroceso para crecer hasta el rectángulo más grande ... pero esas no son mi taza de té, por lo que no tengo la confianza suficiente para crear una respuesta sobre ellos.