Bueno, te diré primero un método que nunca me falla: la búsqueda ciega, su ejemplo más conocido es la fuerza bruta. Sólo tienes que calcular todas las combinaciones posibles y luego ordenarlas según tu criterio o puntuarlas con una métrica tuya. Luego yo suelo ir incluyéndole heurísticas, pistas que vas sacando tu y pueden ayudar la búsqueda.
En este caso yo lo he hecho en un papel, creo que no me equivoco aunque tengo las mates algo oxidadas y no sabría demostrártelo, esperemos que la intuición no me falle.
Lo que me ha salido es una especie de algoritmo fractal o recursivo, ahora lo explico:
Dados un cuadrado y una función de distancia.
Para un punto es trivial, vale cualquier punto del cuadrado.
Para 2 puntos es trivial, un punto en una esquina y otro en la contraria. Por ello cambiamos el primer paso, en coger cualquier punto preferimos coger uno esquinado. Con esto ya podemos inventar un algoritmo incremental que vaya añadiendo puntos.
Para añadir un punto a un cuadrado con n puntos colocados de esta manera(recursiva, partiendo de los 2 esquinados), trazamos una cruz formada por 2 lineas diagonales que salen de los puntos más externos, la otra diagonal es la que corta perpendicularmente a estas 2, vamos a mirar los puntos que interseccionan la cruz con el perímetro del cuadrado o el cuadrado vamos, que es lo mismo.
El nuevo punto lo ponemos en la primera de estas intersecciones que no contenga un punto. Si las 4 intersecciones ya estan ocupadas usamos el punto central de la interseccion. Si también está ocupado pasamos a repetir el proceso pero con el cuadrado cogiendo uno de los puntos externos y el punto central. Pero ha de ser hecho como exploracion en anchura, o sea sólo mirar un nivel, luego el siguiente subcuadrado hasta los 4, y si entonces no hay hueco pasamos a explorar el segundo nivel de cada uno de los 4 subcuadrados recursivamente.
Soltado el rollo, si este algoritmo es bueno, creo que se puede hacer con un simple bucle iterativo si disponemos el número de puntos a priori(que ya has dicho que sí), el número de puntos que cubre cada nivel son: (4,4+1), +(4,4+4), +(12,12+4)
O sea, que primero se cubren las esquinas, 4
Luego los centros, 1
Cuando hay más de un cuadro anidado, las esquinas se comparten muchas,
son ... bueno te dejo calcularlas, habría que tener más muestras. Esto sería para calcular el numero de divisiones partiendo de un numero de puntos a colocar, luego sólo sería llenar los vértices de las divisiones del cuadrado.
Quizá lo esté liando, a ver, simplifico, rellenas las 4 esquinas en ese orden, luego el centro, luego divides el cuadro en 4 y cubres las intersecciones, de cada subcuadro rellenas el centro, luego de cada subcuadro lo divides en 4 y repites el proceso. Sólo ten en cuenta que no puedes hacerlo con recursividad normal pues sería en profundidad, tu necesitas explorar en anchura(en vez de una pila LIFO usa una cola FIFO)
Perdón por el rollo, espero que te sirva, aunque el mío es para espacio continuo, no discreto(dividido en casillas) quizá podría cambiar, jugar con el redondeo, a veces arriba a veces abajo? no sé, si me animo te intento luego hacer un code
.
Autor
En línea
por que en su defecto tendria que ser un random...
