python - Distribuya los puntos en un círculo lo más uniformemente posible.
algorithm geometry (9)
Planteamiento del problema
Tengo el siguiente problema: tengo un círculo con un cierto número (cero o más) de puntos en él. Estas posiciones son fijas. Ahora tengo que colocar otro conjunto de puntos en el círculo, ya que todos los puntos juntos están distribuidos lo más uniformemente posible alrededor del círculo.
Gol
Mi objetivo ahora es desarrollar un algoritmo que tome una lista de ángulos (que representan los puntos fijos) y un valor int (que representa cuántos puntos adicionales se deben colocar) y que devuelva una lista de ángulos nuevamente (que contenga solo los ángulos donde los puntos adicionales deberían mentira).
Los puntos no tienen que estar realmente distribuidos uniformemente (todos a la misma distancia uno del otro), sino que tan uniformemente como sea posible. Una solución perfecta puede no existir la mayor parte del tiempo, ya que ciertos puntos son fijos.
El rango de todos los ángulos se encuentra entre -pi y + pi.
Ejemplos
Algunos ejemplos de lo que estoy tratando de archivar:
fixed_points = [-pi, -pi/2, pi/2]
v v v
|---------|---------|---------|---------|
-pi -pi/2 0 pi/2 pi
fill_circle(fixed_points, 1)
# should return: [0]
fill_circle(fixed_points, 2)
# should return: [-pi/6, pi/6]
o:
fixed_points = [-pi, -pi*3/4, -pi/4]
v v v
|---------|---------|---------|---------|
-pi -pi/2 0 pi/2 pi
fill_circle(fixed_points, 6)
Este último ejemplo debería devolver algo como: Un punto es establecer entre -pi * 3/4 y -pi / 4, es decir: -pi / 2 y distribuir los otros 5 puntos entre -pi / 4 y + pi ( recuerde que es un círculo, por lo que en este caso -pi = + pi):
v v x v x x x x x
|---------|---------|---------|---------|
-pi -pi/2 0 pi/2 pi
Intento anterior
Comencé con un algoritmo recursivo que primero busca el intervalo más grande entre dos puntos y establece el nuevo punto en el medio. Sin embargo, no da resultados satisfactorios. Considere, por ejemplo, esta configuración, con dos puntos necesarios para insertar:
v v v
|---------|---------|---------|---------|
-pi -pi/2 0 pi/2 pi
first step: insert right in the middle of largest interval
v v x v
|---------|---------|---------|---------|
-pi -pi/2 0 pi/2 pi
second step: insert right in the middle of largest interval
-> all intervals are evenly large, so one of them will be taken
v x v v v
|---------|---------|---------|---------|
-pi -pi/2 0 pi/2 pi
No es una solución muy buena, ya que podría haber estado mucho mejor distribuida (ver más arriba: -pi / 6 y + pi / 6).
Perdón por la larga pregunta, espero que entiendas lo que quiero archivar.
No necesito un algoritmo de trabajo completo, sino la idea correcta para desarrollar uno. Tal vez algún pseudocódigo si quieres. Estaría muy agradecido por algunos consejos para empujarme en la dirección correcta. ¡Gracias por adelantado!
Actualización: algoritmo completado:
¡Gracias a todos por sus respuestas o comentarios! Apareció que básicamente necesitaba una versión no codiciosa de mi algoritmo ya existente. Realmente me gustó la idea de haydenmuhls de simplificar un poco el problema encapsulando una clase de intervalo / segmento:
class Segment:
def __init__(self, angle, prev_angle, wrap_around):
self.angle = angle
self.length = abs(angle - prev_angle + /
(2*math.pi if wrap_around else 0))
self.num_points = 0
def sub_length(self):
return self.length / (self.num_points + 1)
def next_sub_length(self):
return self.length / (self.num_points + 2)
def add_point(self):
self.num_points += 1
Esto hace que el algoritmo real sea increíblemente fácil y legible:
def distribute(angles, n):
# No points given? Evenly distribute them around the circle
if len(angles) == 0:
return [2*math.pi / n * i - math.pi for i in xrange(n)]
# Sort the angles and split the circle into segments
s, pi, ret = sorted(angles), math.pi, []
segments = [Segment(s[i], s[i-1], i == 0) for i in xrange(len(s))]
# Calculate the length of all subsegments if the point
# would be added; take the largest to add the point to
for _ in xrange(n):
max(segments, key = lambda x: x.next_sub_length()).add_point()
# Split all segments and return angles of the points
for seg in segments:
for k in xrange(seg.num_points):
a = seg.angle - seg.sub_length() * (k + 1)
# Make sure all returned values are between -pi and +pi
ret.append(a - 2*pi if a > pi else a + 2*pi if a < -pi else a)
return ret
Nunca dijiste qué se mide con precisión "cómo está espaciado uniformemente". La varianza de la raíz cuadrada media total del intervalo de tamaño de los intervalos de intervalo perfectamente espaciados, o algo más?
Si observa cualquier intervalo abierto en particular al principio, creo que una solución óptima que coloque k puntos en ese intervalo siempre los espaciará de manera uniforme. Por lo tanto, el problema se reduce a la elección de puntos de corte para el tamaño de intervalo mínimo, para obtener un cierto número de puntos intersticiales. Cuando haya terminado, si no tiene suficientes puntos para distribuir, suelte un punto de cada intervalo de mayor a menor y repítalo hasta obtener algo sensato.
Sin embargo, no estoy seguro de cuál es la mejor manera de elegir los puntos de corte.
Podrías usar un objeto de intervalo. Un intervalo es un arco del círculo entre dos de los puntos inmóviles originales.
El siguiente es sólo un pseudo-código. No esperes que se ejecute en cualquier lugar.
class Interval {
private length;
private point_count;
constructor(length) {
this.length = length;
this.point_count = 0;
}
public add_point() {
this.point_count++;
}
public length() {
return this.length;
}
// The current length of each sub-interval
public sub_length() {
return this.length / (this.point_count + 1);
}
// The sub-interval length if you were to add another point
public next_sub_length() {
return this.length / (this.point_count + 2);
}
public point_count() {
return this.point_count;
}
}
Cree una lista de estos objetos correspondientes a los intervalos entre los puntos de su círculo. Cada vez que agregue un punto, seleccione el intervalo con el mayor next_sub_length (). Cuando hayas terminado, no será difícil reconstruir el nuevo círculo.
Esto debería darle la separación con el intervalo mínimo más grande posible. Es decir, si puntúa una solución por la longitud de su intervalo más pequeño, esto le dará la puntuación más alta posible. Creo que para eso has estado disparando.
Edición: Me acabo de dar cuenta de que preguntaste específicamente sobre esto en Python. Soy un buen Python n00b, pero deberías poder convertir esto en un objeto de Python fácilmente, aunque no necesitarás los captadores, ya que todo en Python es público.
Primero, redefinimos el término de la siguiente manera: Encuentre tal distribución de N puntos, que la longitud de la distancia mínima entre cualquiera de los dos puntos de estos y M predefinidos sea máxima. Entonces tu tarea es encontrar este máximo de longitud mínima. Llámelo L Tiene M longitudes de segmentos existentes, asumiendo que están almacenados en la lista s . Así que si esta longitud es L primer lugar
min(s) > L
y la cantidad máxima de puntos adicionales es
f(L) = sum(ls/L -1 for ls in s)
Por lo tanto, puede encontrar una L óptima utilizando la búsqueda binaria tomando el inicio L = 0 y la máxima L = min (s) y comprobando la condición si la suma (ls / L -1 para ls en s)> = N. Luego para cada segmento s [ i] simplemente puede colocar s [i] / L -1 de puntos de manera equitativa. Creo que esta es la solución óptima.
Actualizado Hubo falla en min(s) > L Fue lo suficientemente bueno para el término redefinido, pero error para el original. He cambiado esta condición a max(s) > L También se agregó la omisión de segmentos más pequeños que L en la búsqueda binaria. Aquí está el código actualizado completo:
from math import pi,floor
def distribute(angles,n):
s = [angles[i] - angles[i-1] for i in xrange(len(angles))]
s = [ls if ls > 0 else 2*pi+ls for ls in s]
Lmin, Lmax = 0., max(s)
while Lmax - Lmin >1e-9:
L = (Lmax + Lmin)/2
if sum(max(floor(ls/L) -1,0) for ls in s ) < n: Lmax = L
else : Lmin = L
L= Lmin
p = []
for i in xrange(len(s)):
u = floor(s[i]/L) -1
if u <= 0:continue
d = s[i]/(u+1)
for j in xrange(u):
p.append(angles[i-1]+d*(j+1))
return p[:n]
print distribute((0, pi/4),1)
print distribute((-pi,-pi/2,pi/2),2
Propongo que consideres el problema como:
- Una línea envuelta - que le permite determinar la distancia entre puntos fácilmente, y luego volver a asignarla al círculo
o
- Considere los ángulos entre los puntos y el centro del círculo en lugar de la distancia del arco. Nuevamente, esto simplifica el posicionamiento de nuevos puntos y es quizás el candidato más fácil para volver a mapear los puntos del borde del círculo. Encuentre todos los ángulos entre los puntos ya colocados, luego biseca el más grande (o similar) y coloque el nuevo punto en el punto apropiado en el borde del círculo.
Supongamos que los intervalos entre los puntos son a_1 ... a_n. Luego, si dividimos cada segmento en piezas de tamaño mínimo d, podemos ajustar el floor(a_i/d) - 1 puntos en el segmento. Esto significa que la sum(floor(a/d) for a in interval_lengths) debe ser mayor o igual que n + s donde n es el número de puntos que queremos agregar, y s es el número de puntos que ya están allí. Queremos elegir d lo más grande posible, probablemente es mejor hacer una búsqueda binaria para obtener la mejor d.
Una vez que hayamos elegido d, simplemente recorra cada segmento agregando puntos cada d grados hasta que queden menos de 2 d grados en el segmento
Edite todo lo que necesita es encontrar d tal sum(floor(a/d) for a in interval_lengths) == n + s , luego asigne floor(a_i/d) - 1 al segmento i cada a_i/(floor(a_i/d) - 1) grados. La búsqueda binaria encontrará esto rápidamente.
Edición adicional
Aquí está el código para encontrar d
def get_d(n, a, lo=0, hi=None):
s = len(a)
lo = 360./(s + n)
hi = 2. * lo
d = (lo + hi)/2
c = sum(floor(x/d) for x in a)
while c != (n + s):
if c < (n + s):
hi = mid
else:
lo = mid
d = (lo + hi)/2
c = sum(floor(x/d) for x in a)
return d
Supongamos que ya tienes M puntos dados y que N más necesitan ser agregados. Si todos los puntos estuvieran espaciados de manera uniforme, entonces tendría espacios de 2*pi/(N+M) entre ellos. Por lo tanto, si corta en sus puntos M para dar M segmentos de ángulo, puede colocar puntos en un segmento (espaciados uniformemente entre sí) hasta que el espacio sea menor o igual a 2*pi/(N+M) .
Por lo tanto, si la longitud de un segmento es L , debe colocar el floor(L*(N+M)/(2*pi)) - 1 puntos en él.
Ahora te van a quedar algunos puntos. Clasifique los segmentos por el espaciado que tendría entre los puntos si se agregara un punto más. En realidad, agregue el punto al segmento con el rango más bajo. Vuelva a insertarlo en su lista ordenada y vuelva a hacer esto, hasta que se quede sin puntos.
Como cada vez que coloca un punto en un segmento en el que el resultado será puntos lo más espaciados posible, y el espacio entre los puntos no depende del orden en el que los agregó, terminará con el espacio óptimo.
(Edición: donde "óptimo" significa "distancia mínima máxima entre puntos", es decir, evitar el peor escenario posible de puntos uno encima del otro lo mejor posible).
(Edit: espero que quede claro que la idea es decidir cuántos puntos van a cada segmento, y solo al final, una vez que se hayan decidido todos los números, los separa de manera equitativa dentro de cada segmento).
Tengo una función llamada "condición" que toma dos argumentos: un numerador (const) y un denominador (pass-by-ref). O "crece" o "reduce" el valor del denominador hasta que un número entero de "denominadores" se ajusta al numerador, es decir, ese numerador / denominador es un número entero.
Si el denominador ha crecido o se ha reducido depende de cuál hará que cambie en una cantidad menor.
Establezca el numerador en 2 * pi y el denominador en algo parecido al espaciado que desee, y debería tener una distribución bastante parecida.
Tenga en cuenta que también tengo una función "comparar" que compara dos dobles por igualdad dentro de una cierta tolerancia.
bool compare( const double num1, const double num2, const double epsilon = 0.0001 )
{
return abs(num1 - num2) < epsilon;
}
entonces la función de condición es
void condition(const double numerator, double &denominator)
{
double epsilon = 0.01;
double mod = fmod( numerator, denominator );
if( compare(mod, 0) )
return;
if( mod > denominator/2 ) // decide whether to grow or shrink
epsilon *= -1;
int count = 0;
while( !compare( fmod( numerator, denominator ), 0, 0.1) )
{
denominator += epsilon;
count++;
if( count > 10000 ) // a safety net
return;
}
}
Espero que ayude, sé que este pequeño algo me ha sido muy útil varias veces.
One idea, write angles as list (in degrees): [30, 80, 120, 260, 310] Convert to differences: [ 50, 40, 140, 50, 80] Note that we wrap around 310 + 80 (mod 360) = 30, the first angle For each point to be added, split the largest difference: n=1, split 140: [50, 40, 70, 70, 50, 80 ] n=2, split 80: [50, 40, 70, 70, 50, 40, 40] Convert back to angles: [30, 80, 120, 190, 260, 310, 350]
Starting with array [30, 80, 120, 260, 310] and adding n = 5 angles, the given algorithm (see below) gives [30, 55, 80, 120, 155, 190, 225, 260, 310, 350] with a root mean square of the differences between angles rms(diff) = sqrt[sum(diff * diff)] / n = 11.5974135047, which appears to be optimal for practical purposes.