Estoy buscando un algoritmo de embalaje que reduzca un polígono regular en rectángulos y triángulos rectos. El algoritmo debe intentar usar la menor cantidad de formas posibles y debe ser relativamente fácil de implementar (dada la dificultad del desafío).Algoritmo de embalaje eficiente para polígonos regulares
Si es posible, la respuesta a esta pregunta debe explicar la heurística general utilizada en el algoritmo sugerido.
Creo que la respuesta es bastante simple para polígonos regulares.
Encuentra un eje de simetría y traza una línea entre cada vértice y su espejo. Esto divide el polígono en trapezoides. Cada trapezoide se puede convertir en un rectángulo y dos triángulos rectángulos.
Puede obtener un crédito adicional demostrando que esto produce el número mínimo de fichas. :) – Svante
Ahora creo que esto es realmente óptimo :-) – Mau
No. No siempre es óptimo. Tomemos, por ejemplo, un hexágono regular con dos lados paralelos al eje x = 0. Entonces este algoritmo genera 2 rectángulos y 4 triángulos rectángulos, pero 1 rectángulo y 4 triángulos serían suficientes. No obstante, la solución es probablemente lo suficientemente buena y fácil de implementar. – abc
No es específicamente rectángulos + triángulos rectos, pero un buen punto de investigación para buscar polígonos de teselación es Voronoi Diagrams and Delaunay Triangulations y here y here.
De hecho, si los "triángulos correctos" son lo suficientemente buenos, se garantiza que triangularán para usted, y siempre puede dividir cualquier triángulo en dos triángulos rectos, si realmente los necesita. O puede cortar "puntas" de triángulos para hacer más triángulos rectángulos y algunos rectángulos fuera de los triángulos derechos.
También puede probar ear-clipping, ya sea barriendo radialmente, si sabe que tiene polígonos bastante regulares, o "recortando el trozo convexo más grande". Luego, divide cada triángulo restante en dos para crear triángulos rectos.
polygon http://static.eruciform.com/images/polygon.png
Se podría tratar de hacer menos se rompe mediante el barrido de un lado y luego al otro para hacer un trapecio, que se dividió de manera diferente, pero luego tiene que hacer una comprobación para asegurarse de que su barrido de línea hasn ha cruzado otra línea en algún lugar. Siempre puedes recortar las orejas, incluso con algo prácticamente fractal.
Sin embargo, esto a veces crea triángulos muy delgados. Puede realizar heurísticas, como "tomar el más grande", en lugar de cortar continuamente a lo largo del borde, pero eso lleva más tiempo, acercándose a O (n^2). Delaunay/Vornoi lo hará más rápido en la mayoría de los casos, con triángulos menos delgados.
Absolutamente deben ser rectángulos y triángulos rectos. Sé que suena extraño, pero es un requisito de usuario. – Steve
actualizado. puedes convertir cualquier triángulo en triángulos y rectángulos con bastante facilidad. – eruciform
Las triangulaciones de Delaunay no son ideales aquí porque introducen puntos innecesarios adicionales en el medio. Cada uno de esos puntos internos se puede "arrastrar" a un vértice de polígono adyacente y se queda con un conjunto más pequeño de triángulos. –
Puede intentar "recortar" the largest rectangle that can fit in the polygon, dejando atrás algunas sobras. Sigue repitiendo el recorte de rectángulos en las sobras, hasta que termines con piezas triangulares. Luego, puedes dividirlos en dos triángulos rectángulos si es necesario. No sé si esto siempre dará soluciones que le darán la menor cantidad de rectángulos y triángulos rectángulos.
Creo que tampoco es una buena idea: comer tanto área como sea posible con el primer rectángulo no te dejará con la forma "más fácil" después. – Mau
no estaba claro cuáles eran sus requisitos. formas menos totales o la mayoría del área en formas menos ... – eruciform
Para polígonos regulares, aún así te da formas "agradables". De nuevo, no sé si esto te dará las soluciones "más óptimas". –
es esto para una clase o de una clase de algoritmos gráficos por ordenador? – eruciform
No es para una clase. No estoy en la escuela – Steve
De hecho, podría estar dispuesto a darle una oferta de trabajo a alguien que pueda responder bien a la pregunta si puede programar para iPhone, Mac y .net. ;) – Steve