¿Cómo calcular un par de puntos más cercanos en dos círculos en 3D?

Question

Tengo dos círculos 2D en el espacio 3D (definido por un centro, normal y radio) y estoy tratando de llegar a un par de puntos que es uno de los conjuntos de pares más cercanos de puntos. Sé que hay entre 1 y un número infinito de pares de puntos, solo necesito un solo par coincidente.

¿Hay una manera simple de hacer eso? La precisión no es esencial. El radio de ambos círculos es el mismo valor distinto de cero.

En caso de que el fondo sea útil, mi algoritmo general toma una curva NURBS en el espacio y extruye un polígono 2d a lo largo de la curva, produciendo un cilindro deformado. Solo muestro varios puntos a lo largo de la curva. La normal de cada círculo es la tangente de la curva NURBS, y estoy tratando de encontrar la forma de alinear las muestras adyacentes, para que no tenga torceduras extrañas. Parece que los puntos más cercanos en las muestras adyacentes deben estar alineados.

---

Gracias por todas las respuestas aquí .. esta parte del proyecto se pusieron un poco retrasada, por lo que no he probado todas las respuestas. Me aseguraré de arrojar algunas imágenes aquí y marcar una respuesta cuando vuelva a trabajar en esto.

Answer 1

Lo que realmente está tratando de calcular es el par de puntos que minimiza la distancia entre los puntos que se encuentran en 2 círculos diferentes en 3 dimensiones. El método que debe emplear para encontrar la solución exacta (como en casi todos los problemas de optimización) es representar la distancia como una función de todos los puntos posibles y tomar su derivada con respecto a las variables independientes y establecer las expresiones resultantes en 0 Como tiene 2 círculos, tendrá 2 variables independientes (es decir, el ángulo de un punto en un círculo y uno en el otro círculo). Una vez que haya resuelto las ecuaciones de minimización, también habría encontrado los puntos en los círculos que satisfarán su restricción. (Básicamente, encontrará los ángulos en los círculos para el par de puntos que está buscando.)

He encontrado paper en línea (en this site) que realiza rigurosamente los cálculos pero el resultado final es la resolución de una ecuación polinomial de octavo orden. Puede intentar simplificar las ecuaciones y encontrar una solución menos exacta que satisfaga sus necesidades.

También hay un paper que dice tener un algoritmo mucho más rápido para encontrar la distancia entre dos círculos en 3d; sin embargo, no puedo ver el contenido y, por lo tanto, no puedo decir si también te da el par de puntos que satisfacen esa condición.

ACTUALIZACIÓN: Después de volver a leer su pregunta, veo que a pesar de que está buscando una manera de encontrar el par de puntos más cercano en dos círculos en 3 dimensiones, creo que debe prestar más atención al propiedades de la curva NURBS que está tratando de extruir el polígono 2D a lo largo. Usted menciona que la orientación del círculo en un punto dado de la curva se especifica mediante el vector tangente en ese punto. Sin embargo, hay más en las curvas 3D que solo el vector tangente; existe el normal (o curvatura) vector que apunta hacia el centro de curvatura de la curva en un punto dado y luego está el vector de torsión que básicamente especifica la cantidad de "elevación" de la curva desde el plano dado por la tangente y los vectores normales. Todos estos definen un (lo que se llama) marco Frenet. Puede leer más sobre esto en el Wikipedia article.

Mi sospecha es que puede lograr el efecto que desea uniendo los puntos de círculos consecutivos que se encuentran a lo largo de la dirección del vector normal de la curva 3D subyacente. De esta forma, tendrá torsión solo cuando la curva esté realmente torcida, es decir, cuando el vector de torsión no sea cero y el vector normal también cambie de dirección. En otras circunstancias, esto debería satisfacer su necesidad real.

Probablemente no necesite el exceso de encontrar los puntos más cercanos en círculos consecutivos.

Answer 2

¿No es solo cuestión de construir la línea entre los dos centros de los círculos/esferas y encontrar la intersección de la línea y los círculos? Las soluciones que están más cerca son (a menos que el círculo se interseque, entonces la respuesta depende de cómo quiera interpretar ese caso).

Answer 3

Sí, a menos que los círculos estén en el mismo plano o planos paralelos, creo que la única manera de hacerlo es encontrar un mínimo en la ecuación de la distancia entre dos puntos en el círculo.

http://www.physicsforums.com/showthread.php?t=123168

Ese vínculo muestra cómo obtener la ecuación de cada círculo en el espacio 3D, a continuación, reducir al mínimo para la fórmula de la distancia entre esas ecuaciones. Aunque no es bonita, con suerte alguien inventará algo más inteligente.

Answer 4

Por lo que describes, es suficiente seleccionar un punto en el perímetro del primer círculo y encontrar el punto en el perímetro de cada círculo a lo largo de la más cercana a la seleccionada para el círculo anterior; esto restringirá por completo la poligonalización, sin torsiones, y debería ser mucho más fácil de resolver que el caso general: simplemente encuentre el punto en el plano que contiene el segundo círculo más cercano al seleccionado en el primero, e interseque la línea que pasa ese punto y el centro del segundo círculo con el perímetro del segundo círculo.

Sin embargo, esto podría no ser tan satisfactorio para una poligonalización del cilindro extruido como mantener el área del polígono lo más constante posible, y para hacer eso se requerirá cierta torsión entre círculos adyacentes.

Answer 5

Creo que con los dos puntos más cercanos es posible que aún tenga torceduras extrañas ... Un ejemplo extremo: supongamos que ambos círculos tienen la R = 1. Si el centro del primer círculo es O, y está sentado en el plano XY, y el centro del segundo círculo está sentado en X = 1, Y = 0, Z = 0.01, y está ligeramente inclinado en la dirección creciente de X, el más cercano los puntos en los dos círculos seguramente obtendrán el "giro extraño" que estás tratando de evitar. Dado que los puntos más cercanos no te darán el giro extraño en caso de que el segundo círculo esté en X = 0, Y = 0, Z = 0.01 y esté igualmente inclinado, entonces en algún momento las afirmaciones "se alinearán con dos puntos más cercanos en dos círculos" y "no se han visto torceduras extrañas" ya no se corresponden entre sí.

Suponiendo que esto puede ocurrir dentro de la restricción de NURBS, aquí hay otra idea. Al principio, tome los tres puntos en la curva NURBS: dos que pertenecen a los centros de sus círculos, y el tercero exactamente entremedio. Dibuja un avión entre los tres. Este plano cruzará los dos círculos en 4 puntos. Dos de estos puntos estarán en el mismo "lado" de la línea que conecta los centros de los círculos: son sus puntos de alineación.

Para los siguientes puntos de alineación, tomará el punto de alineación del "círculo anterior" y dibujará el plano entre el centro del "círculo anterior", este punto de alineación y el centro del "círculo nuevo". De esto obtienes el "siguiente punto de alineación" basado en la intersección con el otro círculo.

Siguiente paso - "círculo anterior" = "círculo nuevo", y el "círculo nuevo" - su próximo de acuerdo con la curva NURBS.

Si se cruzan los radios desde los centros de los círculos a los puntos de alineación seleccionados, sabrá que la imagen se verá un poco fea: ese es el escenario donde con el algoritmo de "punto más cercano" aún se torcería .

Creo que las coordenadas del punto en el círculo que es intersección con el plano que pasa por su centro deberían ser fáciles de calcular (es un punto en la línea hecha por la intersección de los dos planos, uno del círculo y el plano objetivo, a la distancia R del centro).

No tengo la prueba rigurosa para afirmar completamente o negar lo anterior, pero espero que ayude en absoluto, y creo que debería ser lo suficientemente rápido para verificar, en comparación con el cálculo de los puntos del armario en los dos círculos. . (Si hay algún defecto en mi lógica, las correcciones en los comentarios son bienvenidas).

Answer 6

Extienda los círculos a los planos (utilizando los puntos centrales y las normales). Si los aviones son paralelos, entonces cualquier punto servirá. Si los planos no son paralelos, se cruzan en una línea. Construye el avión a través de los dos centros de los círculos perpendiculares a la línea. Los dos círculos se cruzan con este nuevo plano en cuatro puntos. Estos cuatro puntos son los dos puntos más cercanos y los dos puntos más lejanos de los círculos.

Answer 7

El hilo here, mencionado en otra respuesta, da la fórmula de parametrización para un círculo 3D: P = R cos (t) u + R sin (t) nxu + c, donde u es un vector unitario del centro del círculo a cualquier punto en la circunferencia; R es el radio; n es un vector unitario perpendicular al plano yc es el centro del círculo, t va de 0 a 2pi, y por nxu quiero decir "n cruz u". Parametrice un círculo de esta manera, y otro similar con un parámetro diferente, digamos s. Entonces cada punto Pt en el primer círculo tendrá coordenadas en la variable t, y cada punto Ps en el segundo círculo tendrá coordenadas en la variable s.

Escriba la función de distancia d (s, t) entre Ps y Pt de la manera habitual (o mejor, el cuadrado de la distancia euclidiana para no tener que meterse con la raíz cuadrada cuando tome derivadas). La gráfica de esta función d de dos variables es una superficie sobre un cuadrado de 2pi por 2pi en el plano s, t, y su mínimo es lo que busca. Puede determinarlo con los métodos de cálculo estándar, p. como se explica here.