Solapamiento De Rectángulos (etiquetado De Mapas)

[sés]

 Mi problema es el siguiente:

Necesito dibujar en pantalla puntos representados por iconos.
Como puede que varios puntos estén muy cerca o incluso en el mismo sitio, necesito un algoritmo para que no se solapen, desplazando aquellos que lo hagan.

He buscado por "map labeling", pero no encuentro nada que me resuelva el problema (y los que podrían resolverlo son demasiado complejos para lo que quiero).

¿Alguien sabe como hacerlo o ha hecho algo similar?

[CoLSoN2]

 no creo ke tenga mucha historia (a no ser que esté equivocado en cuanto a lo que te refieres):
- Supondré que los iconos son de NxN pixeles y que los puntos (2 para el ejemplo) son p1(x1,y1) y p2(x2,y2)
- Supondré también que todo son coordenadas 2d

Código [Seleccionar] Expand

mientras que distancia(p1,p2) < 2*N
           v = p2 - p1
           normalizar(v)
           p2 = p2+v
Explicación: Desplazar el punto 2 cada vez más lejos del punto 1 hasta que no se solapen

distancia(p1,p2) sería un simple:

Código [Seleccionar] Expand


  devolver raiz( (x2-x1)^2 + (y2-y1)^2 )


y normalizar, pues eso xD

espero que te sirva de algo, talue

[sés]

 Ya :P... pero no se trata de dos puntos, se trata de montones.

Si alejo esos puntos o uno de ellos (por cierto, ¿hacia donde?) y, al hacerlo, se monta en otro... ¿y si alejo ese otro? ¿y si se monta en otro? ¿y si eso otro tb lo alejo...?  (uoh)

[Mars Attacks]

 Una solución sencilla sería asignar a la pantalla una matriz de coordenadas enteras, y para cada elemento que muevas se trunque su posición x e y al entero más cercano, marcando la casilla pertinente de la matriz y desmarcando desde la que procedía. Si mueves el punto a una casilla que ya está marcada, al soltar el botón debería devolver ese punto a las coordenadas originales.
¿Te sirve?

[sés]

 Pero el problema es: Si la posicion donde debería ir un punto está ocupada, ¿dónde le pongo? ¿le desplazo, donde?

No se trata de ir poniendo puntos sin que se solapen, se trata de dibujar puntos que YA TIENEN COORDENADAS ASIGNADAS, pero evitando que se solapen.

Como pone en el título es para "etiquetado de mapas". Supon que tienes que poner los nombres de todos los pueblos de madrid en un mapa. Si los pones, por ejemplo, centrados en los puntos, muchos se montarán sobre otros. Tengo que desplazar los que se monten, pero manteniéndolos cerca de su punto.

[Mars Attacks]

 Aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaah. Juer, pues qué cortito soy, no lo había entendido  :(  Lo siento.
Así en principio... no se me ocurre nada. Tal vez aplicar lo dicho por Colson empezando desde el centro de la imagen y haciendo una espiral hacia fuera.
Uf, habría que pensar un poco ese problema  :angry:  Si se me ocurre algo ya lo pondré por aquí, pero espero que a alguien más inteligente (cualquiera) se le ocurra algo antes y me ahorre una noche de insomnio.

¡Un sésludo!

[Forum Master]

 Y no sería buena opcion hacer una circunferencia alrededor del punto, la divides en las partes que necesites y en cada parte le pones un nombre y luego le haces una linea desde caca nombre al punto (eso si los nombres quedan demasiado lejos debido a que hay muchos). Es decir, que tienes 2 nombres: circunferencia pequeña con nombres arriba y abajo. Es que todo depende de cuantos nombres tengas que ponerle al punto puede ser muy engorroso  (uoh)  

[CoLSoN2]

 pos pon números, y una leyenda con textos XD

[Forum Master]

pos pon números, y una leyenda con textos XD

Ciertamente la solución más facil suele ser la más clara  (ole)  

[Mars Attacks]

 ¿Y qué pasa si se le solapan los números?

[sés]

 Pues... "sería buena opcion hacer una circunferencia alrededor del punto, la divides en las partes que necesites y en cada parte le pones un nombre y luego..." (uoh)  

[tiutiu]

 Creo q he dado con una solucion, aunq se debria optimizar para q no fuese muy lenta. T digo primero como la he hallado y asi la practicas tu y la depuras xD Me he basado en el algoritmo d CoLSoN (pq tienes un 2 en el nombre?).

-He cogido las cartas (baraja española mejor (uoh) nah es broma (twist)) y he repartido por encima d la cama no menos de 8 pero no mas de 10 xDDD
-Entonces he cogido una al azar (para no parecer un capullo he cogido una q tuviese una carta solapada). Y he hecho una iteracion por todas las cartas q tenia solapadas (interseccion rectangulo-rectangulo) y las he desplazado (la carga q escojo no la toco, es la q DESPLAZA a las demas).
-Entonces elijo otra carta y hago lo mismo.

Lo he probado varias veces y me sale (al menos con mi cerebro como procesador y memoria d programa xD).
Alguno dira "Si, y entraras en un bucle infinito pq puede q dos cartas esten repeliendose por siempre la una a la otra". Pues hombre, ahora acabo d repetir el proceso 'haciendome la pua' y si q podria hacer miles de iteraciones por todos los iconos, pero weno, al final lo q hago es cambiar el orden de escoger los iconos.

Ya esta, version RC1 de Algoritmo del empujon (Prod-Algorithm queda mas uber xDDD)

Código [Seleccionar] Expand


//Prod-Algorithm por tiutiu ver1.0 RC1
//Pseudo-codigo

por cada ic1 = icono en iconos
{
 por cada ic2 = icono en ic1.iconos_solapados
 {
   d = normalizar(ic2.pos - ic1.pos) * m //m es la distancia minima pa q no esten solapados
   ic2.pos += d
 }
}

Si se quiere se puede hacer otra iteracion hasta q iconos_solapados sea 0. Por cierto, la coleccion iconos_solapados la hallas con la interseccion rectangulo-rectangulo q antes he mencionado.

Un saludo :blink:

PD: Se podria poner el tipo d letra courier para cuando escribes codigo?

[sés]

 Si inserto digamos... 10 iconos, que se van desplzando digamos hacia arriba... y luego inserto otro que los tiene que desplazar hacia abajo... (nooo)

Esto me recuerda al típico problema de colocar reinas en un tablero de ajedrez... sólo que en un tablero sólo hay 8 casillas alrededor de un cuadro.

Gracias a todos, buscaré un poco más por internet antes de ponerme a hacerlo desde cero. Que es para el curro, no para mí.
Si fuera para mí, directamente intentaba hacerlo yo  B)

[Ryuchan]

 Yo iria separando objetos solapados e una vez separados agruparlos para considerarlos un todo a la hora de separar el resto.
Es decir, empiezas buscando 2 objetos solapados. Si no encuentras ninguno ya has acabado :)
Si encuentras una pareja que se solapa pues la separas y creas una bounding box que englobe los 2 objetos que a partir de ahora a efectos del algoritmo seran solo 1. Entonces repites el proceso y cada vez que separes 2 objetos creas uno nuevo (que se entiende que no sera un icono tuyo sino un elemento temporal del algoritmo) creando la bounding box correspondiente con las coordenadas min i max de los 2 objetos, y prosigues con el algoritmo.
Deberia llegar el caso en que ya no hay mas objetos solapandose.
Funcionar seguro que funciona. Pero quiza no distribuya los iconos lo mas eficientemente posible en el espacio, quiza queden zonas muy vacias y otras muy apretadas.

Yo usaria una estructura parecida a esta:
struct Objeto
{
   Caja BoundingBox;
   Objeto* Hijos[2];
   MiTipoDeIcona* Icona;
}

Inicialmente crearias un Objeto para cada icona tuya calculando su bounding box asignando el puntero correspondiente y poniendo a NULL los 2 hijos.
Esotos objetos los meterias en una lista de objetos a separar.
Cuando unieras 2 objetos crearias uno nuevo, asignarias a los 2 punteros de los hijos los objetos agrupados, calcularias la bounding box del nuevo objeto, pondrias a NULL el puntero de la Icona e eliminarias de la lista de objetos a separar los 2 objetos hijos.
Suponiendo que la Icona tiene atributos de posicion, cada vez que desplazes un objeto para separarlo de otro deberias aplicar el mismo desplazamiento a su icona si es que la tiene, y a las iconas de sus hijos, recursivamente, si es que existen.

Una vez acabado el proceso tendras todas las iconas en el sitio donde deben ir para que queden separadas.

[TurMach]

 Aun que  quizas sea matar moscas a  cañonazoa mira esta  web:

www.red3d.com/cwr/boids

Explica dinamica de grupos. Basicamente se trata de asignar furzas de repulsion y atraccion para crear comportamientos de grupos.

Puede que esto te sirva de inspiracion para encontrar la solucion que buscas.

enga  :lol: