Diseñar rectángulos evitando colisiones (ayuda con el algoritmo)

Question

Tengo una vista (grande) de desplazamiento horizontal y un montón de rectángulos que me gustaría colocar en ella. Cada rectángulo tiene una posición horizontal deseada, pero puede variar desde esa posición hasta una cierta cantidad (una constante, K) si es necesario. Los rectángulos no deben superponerse. La posición vertical de los rectángulos es arbitraria (limitada a la altura de la vista, por supuesto).

Idealmente me gustaría que el tamaño de los rectángulos sea variable ... Supongo que si eso no es posible, puedo hacer que el tamaño varíe en una sola dimensión.

Ahora, habrá imposibilidades en este diseño: dado que solo hay una cierta cantidad de espacio vertical, y que solo pueden alejar K píxeles de su ideal horizontalmente, probablemente no todos los rectángulos podrán dibujarse. Para hacer frente a esto, cada rectángulo tiene una prioridad (P), y los de menor prioridad deben omitirse primero. (Puede suponer que eso no es ambiguo, y que siempre puede decir cuál de los dos rectángulos tiene la prioridad más alta).

Estoy buscando algo del algoritmo conceptual, pero si necesita detalles, esto se ejecutará en un iPad, y habrá algunos miles (> 1000 pero < 10,000) rectángulos a considerar. Idealmente, me gustaría algo lo suficientemente rápido como para volver a ejecutar cada vez que el usuario cambie el nivel de zoom, pero si eso no es fácil, entonces puedo guardar en caché las posiciones. Los objetos son fotos en una línea de tiempo, y quiero acercarlos aproximadamente cuando sucedió el evento. Voy a aproximarme para obtener más de ellos.

He visto algoritmos como this, que hacen el truco de no intersección, pero no tienen la misma idea sobre cada elemento que solo puede moverse hasta una cierta cantidad. Obviamente, sin la última restricción, puede mostrar todos los elementos, por lo que también necesitaré alguna forma de saber en qué punto no se pueden mostrar más rectángulos.

Si resolver el problema como se describe es demasiado difícil, me gustaría recibir una sugerencia de una idea más pragmática. Si todo lo demás falla, siempre podría hacer algo en orden de prioridad, renderizar cada elemento en el lugar deseado si puede, si no, intenta desplazarlo verticalmente, si aún no lo hace, desplazarlo horizontalmente hasta el límite permitido, antes de pasar al siguiente. El orden de prioridad significaría que probablemente se encontraría una solución subóptima, pero se la consideraría como la más importante.

Answer 1

Esta es una de las formas en que creo que esto podría hacerse.

El paso 1 consiste en descubrir todas las ubicaciones donde se puede colocar el nuevo rectángulo amarillo. Sin pérdida de generalidad, podemos almacenar esto como una lista de todas las posibles posiciones X-Y de la esquina superior izquierda del rectángulo. Naturalmente, para un área de inicio tan grande esa lista contendrá millones de entradas, así que para ahorrar espacio almacenaremos esta lista en forma de un conjunto de áreas rectangulares.

Por ejemplo, si nuestra pantalla tiene píxeles de X = 0 a X = 2999 inclusive, y de Y = 0 a Y = 999 inclusive, y nuestro nuevo rectángulo tiene un ancho 300 píxeles y altura de 150 píxeles, la esquina superior izquierda de nuestro nuevo rectángulo puede aparecer en cualquier posición desde (X, Y) = (0, 0) a (2699, 849) inclusive. Guardemos eso como un cuatrillizo, [0, 0, 2699, 849].

Ahora cuando colocamos cada rectángulo existente (rojo) en la pantalla, se descartan algunas de estas posibilidades, ya que darían lugar a que el nuevo rectángulo (amarillo) se superponga. Por ejemplo, si hay un rectángulo rojo [1100, 200, 1199, 299], entonces nuestro rectángulo amarillo no puede tener su esquina superior izquierda en cualquier posición desde (X, Y) = (801, 51) a (1199, 299) inclusivo.

Por lo tanto, reemplace [0, 0, 2699, 849] con cuatro zonas rectangulares que cubren la misma área pero dejan el espacio. Hay muchas maneras de hacerlo, pero aquí hay una: [0, 0, 1199, 50], [1200, 0, 299, 2699], [0, 51, 800, 849], [801, 300, 2699, 849] ]

Sigue agregando más rectángulos rojos a la pantalla. Cada vez que se agrega uno, resta más posibilidades de la lista (esto generalmente dará como resultado una lista que contenga más "zonas seguras" más pequeñas). (Esto puede consumir mucho tiempo para su pantalla completa con más de 1000 rectángulos, si en su lugar comienza con el espacio [XK, 0, X + K, H] que mencionó, entonces relativamente pocos de los 1000 + se superpondrá a esto y el cálculo irá mucho más rápido.) Este código debe escribirse con mucho cuidado y con un montón de pruebas unitarias, porque abundan los errores de cercados.

El resultado final es una lista completa de posibles ubicaciones en la pantalla donde podría colocarse la esquina superior izquierda de su nuevo rectángulo amarillo, expresado en forma de una lista de zonas rectangulares.

Paso 2: consulte esta lista y seleccione la ubicación más conveniente. Cualquier zona rectangular que intersecte su línea vertical ideal tendrá prioridad. Pero es posible que no haya ninguno. En este caso, depende de usted elegir la opción más preferible entre las zonas que caen a la izquierda y las zonas que caen a la derecha de la línea ideal. Como sugerencia: solo se debe considerar una esquina de cada zona en cada caso (la esquina superior izquierda de las zonas a la derecha, la esquina superior derecha de las zonas a la izquierda).