A continuación se muestra una imagen de ejemplo, si tengo un punto del punto blanco en el medio y quiero encontrar la ubicación más cercana posible para el círculo azul (que obviamente está en la ubicación donde lo coloqué) si ya existen todos los círculos rojos . ¿Cómo puedo encontrar esa ubicación?
El rendimiento para mí no es una preocupación importante para esta aplicación.
design
design-patterns
algorithms
performance
geometry
Botánico
fuente
fuente
Respuestas:
Esta no es una solución general, ya que hay varias situaciones en las que no proporcionará la posición del círculo azul con la distancia más corta al punto blanco. Por ejemplo, si tiene 100 bolas rojas agrupadas y el punto blanco está muy lejos de este grupo de bolas rojas, entonces ninguna de las bolas rojas tendrá influencia en la posición del círculo azul que puede centrarse en el punto blanco. . Tampoco mostrará todos los detalles de los cálculos. De todos modos, para un subconjunto de configuraciones, donde la solución (círculo azul) es tangente a dos círculos rojos, debería funcionar lo siguiente:
1) dejar que R sea el radio del círculo azul
2) hacer un bucle sobre todos los pares de círculos rojos, sí Sé que esto es O (n2).
3) para cada par de círculos i, j con centros en (xi, yi) y (xj, yj) con el radio respectivo ri y rj, calcule el cuadrado de la distancia entre el par de círculos
4) pon todos los pares de círculos que
en una lista
5) recorra la lista, encontrando las 2 soluciones de círculos de radio R tangente a ambos círculos i y j. Para hacer esto, use estas ecuaciones junto con esta imagen
con la información anterior puede encontrar (X1ij, Y1ij) y (X2ij, Y2ij) los centros de los 2 círculos tangentes a los círculos i y j. Para cada candidato, haga un círculo azul sobre todos los demás círculos rojos y vea si no se superpone. Si lo descartan, si no, verifique la distancia al círculo blanco. Si mantiene el que tiene una distancia menor, creo que tendrá la solución cuando termine de recorrer la lista de pares de círculos. El algoritmo parece O (n3).
fuente
La ubicación más cercana al punto estará en el punto o tocando un círculo.
por lo tanto, primero verifique el punto, luego gire el nuevo círculo alrededor del borde de cada círculo existente, calcule la distancia desde el punto y si se superpone a medida que avanza y realice un seguimiento del punto de distancia mínima. Detente cuando hayas atravesado todos los círculos.
es decir. verifique todos los puntos en las líneas verdes, más el círculo blanco. donde la línea verde es un círculo con radio del rojo más el azul
debe verificar toda la línea verde, no solo las intersecciones, de modo que cubra estos casos extremos.
Obviamente, el tamaño del paso de su recorrido será importante en términos de rendimiento. Pero como dice que el rendimiento no es un problema, elija el valor correspondiente a la resolución de su valor de salida. es decir, flotar, largo?
aclaración:
mi sugerencia es forzar la fuerza bruta en todos los puntos alrededor de cada círculo, probando la superposición con todos los otros círculos en cada punto. Sin inteligencia.
Si la foto de ejemplo es indicativa de la cantidad de círculos y la resolución, no debería ser un problema para una PC estándar
tenemos 20 círculos de radio promedio 200, por lo que es aproximadamente 20 * 2 π * 200 puntos * 20 pruebas de intersección = 4800000 iteraciones
Nota:
Los enfoques iterativos como este son defectuosos porque el tamaño de su paso, en este caso la resolución de su salida, puede afectar en gran medida el resultado.
Digamos que tengo dos círculos rojos separados por 2 píxeles y un círculo azul de 1 píxel de radio para apretar entre ellos. Claramente, con cualquiera de los dos píxeles como centro del círculo azul, se superpondrá a uno de los rojos. pero obviamente hay espacio para el círculo si el centro se encuentra entre los dos píxeles.
De ahí mi comentario preguntando sobre la resolución de la salida. lo que dijiste podría ser cualquier cosa.
También puede resolver la ecuación simultánea para cada par de círculos con un aumento del radio en el radio del círculo azul.
esto le dará los puntos donde el círculo azul tocará ambos círculos rojos con mayor precisión que la iteración.
Sin embargo. hay varias condiciones en las que si solo haces esto, obtienes la respuesta incorrecta o no respondes. es decir.
1 o sin círculos
2 o más círculos pero con el punto objetivo lejos y fuera de ellos.
muchos círculos pero con un punto objetivo cerca de la superficie
fuente
Este plunk contiene código de trabajo,
Concepto
Los círculos dados son C1, C2 ... Cn
y las coordenadas del círculo Cn es Cnx, Cny y el radio es Cr
y el radio del círculo requerido es R
si el círculo azul está en la ubicación X, Y y no entra en conflicto con ningún otro círculo, las siguientes ecuaciones son verdaderas
cambiando la primera ecuación,
para que las ecuaciones puedan reescribirse como,
Implementación
comenzar desde la coordenada del punto blanco (Xw, Yw),
la primera coordenada encontrada para satisfacer todas las ecuaciones es la ubicación del círculo azul
fuente
círculo extendido es uno de los círculos con su radio extendido por r
Hay algo de trabajo adicional si O no está en un centro circular. Así que ahora suponga que O == C0
Calcule todas las intersecciones de todos los círculos con C0, utilizando sus respectivos radios más la r , es decir, intersecte los círculos extendidos con el C0 extendido. Si no hay intersecciones, entonces el punto que está buscando está en cualquier lugar de C0, si hay intersecciones, para cada intersección verifique si está dentro de otro círculo extendido (puede limitarse a los círculos que tenían intersecciones con C0). Tome la primera intersección que no está en otro círculo extendido como P, puede haber otras.
Si no hay intersecciones entre los círculos extendidos y C0 que no están dentro de otro círculo extendido, calcule las intersecciones de todos los círculos extendidos entre sí. Luego verifique estas intersecciones en orden de distancia a O, nuevamente si alguna de las intersecciones se encuentra dentro de otro círculo extendido, si es así, descarte, si no, ese es su resultado.
Si imagina esto, imagine dibujar una línea alrededor de todos los círculos que indican una posible ubicación para su círculo azul, tomar la unión de todos los círculos extendidos indicará el área que su círculo azul no puede ser. El punto que está buscando es el punto más cercano que no está en esa unión. Si hay algún punto en C0 que no esté en esa unión, esa es la solución, si C0 está completamente cubierto, entonces P debe estar en una intersección entre otros dos círculos extendidos, y debe estar en un área que no esté cubierta por esta unión (es decir, no en un círculo extendido ).
Esto es O (n ^ 2), hay algunas formas de mejorar esto, sin embargo, se puede usar una cuadrícula para reducir el esfuerzo de la búsqueda por pares, también creo que ordenar los círculos por su cercanía a O, (la distancia entre dos círculos reducidos por la radio) ayudarían a limitar el espacio de búsqueda para la búsqueda de cobertura e intersección
fuente
Posible búsqueda de soluciones
Búsqueda de soluciones reales entre posibles soluciones
Ahora tiene un conjunto de puntos que son posibles soluciones , repítalos y verifique cada uno.
NB: No estoy diciendo que la implementación del algoritmo deba describirse exactamente. Puede intentar mejorar el rendimiento utilizando programación dinámica u omitiendo posibles soluciones donde es obvio que no funcionarán.
fuente