objeto Posicionamiento Algoritmo

Question

me pregunto si hay una solución "óptima" para este problema:

tengo a n x m (píxel) de espacio de tamaño con p preexistente rectangled - objetos en distintos tamaños en la misma. Ahora quiero colocar q nuevos objetos del mismo tamaño en este espacio sin ninguna superposición.

El algoritmo vine con:

1. Crea una matriz A [] [] con el tamaño [(n)/(size_of_object_from_q)]x[(n)/(size_of_object_from_q)]

2. Iterar todos los elementos de p y para cada uno:

   mark all fields in A[][] as occupied, where the element "lies"

3. Coloque todos los elementos de q en los lugares donde los campos en A [] [] no estén marcados

(muchacho, espero que podría hacer que comprensible ...)

¿Hay alguna forma mejor de hacer esto? ¡Cualquier ayuda realmente sería apreciada!

Answer 1

A partir de una breve búsqueda en Internet, parece que el embalaje rectangular óptimo es un problema NP-hard. Supongo que las personas inteligentes de la academia encontraron algunos algoritmos de aproximación para eso, por lo que es una opción para buscar en Google.

Pero me gustaría tratar de hacer el trabajo simple método de primera:

1. dividir sus objetos en tamaños según su anchura
2. Trate de colocarlos línea por línea desde el más grande al más pequeño.

Supongo que en muchos casos esta ingenua solución funcionará.

Answer 2

Sé que esta no es una respuesta específica a su pregunta, pero puede ser útil para investigar y/o profundizar en el código fuente graphviz. graphviz ofrece varios modelos de diseño, incluido neato, que intenta minimizar una función energética global.

Wikipedia tiene algún pseudocódigo para force-base algorithms.

Answer 3

Si entiendo la pregunta, parece que está buscando un algoritmo de empaquetamiento bin "óptimo" (también conocido como el problema Knapsack). Ese es un problema NP-Completo, aunque su descripción suena como que probablemente pueda forzar su camino a una solución óptima.