¿Cómo se calcula el punto más cercano en 2 curvas?

Dados los puntos de una línea y una curva bezier cuadrática, ¿cómo se calcula el punto más cercano? .... De manera similar, dados los puntos de 2 curvas, ¿cómo se obtiene el punto más cercano?

Aquí está mi intento. Los siguientes algoritmos están lejos de ser perfectos , pero son simples y creo que debería comenzar con esto, verificar si funcionan en su situación y cambiar a algo más rápido y / o más preciso más adelante.

La idea es la siguiente:

• Muestra la curva de Bézier, encuentra el punto más cercano en esa muestra
• Muestree un vecindario alrededor del punto encontrado, encuentre un nuevo punto más cercano
• Continúa hasta que el punto ya no cambie mucho

Algoritmo de distancia de la curva de Bézier a la línea

La curva de Bézier se parametriza mediante una función que F(t)utiliza un conjunto de puntos de control y un parámetro variable t. El número de puntos generadores no es importante.

La línea está parametrizada por dos puntos Ay B.

1. Deje SAMPLES = 10, por ejemplo,

2. Comience con t0 = 0yt1 = 1

3. Dejar dt = (t1 - t0) / SAMPLES

4. Si dt < 1e-10(o cualquier otra condición de precisión que le parezca adecuada), el algoritmo está terminado y la respuesta esF(t0) .

5. Calcule una lista de SAMPLES + 1puntos en la curva de Bézier:

   • L[0] = F(t0)
   • L[1] = F(t0 + dt)
   • L[2] = F(t0 + 2 * dt)
   • ...
   • L[SAMPLES] = F(t0 + SAMPLES * dt)

6. Encuentre qué punto Lcon índice ies el más cercano a la línea. Utilice cualquier método de distancia punto / línea que conozca, por ejemplo, la distancia cuadrada ||AB^L[i]A||² / ||AB||²donde ^denota el producto cruzado y ||…||es la distancia.

7. Si i == 0, establecer i = 1; si i == SAMPLES, estableceri = SAMPLES - 1

8. Dejar t1 = t0 + (i + 1) * dtyt0 = t0 + (i - 1) * dt

9. Regrese al paso 3.

Algoritmo de distancia de la curva de Bézier a la curva de Bézier

Esta vez tenemos dos curvas Bézier, parametrizadas por F(t)y G(t).

1. Deje SAMPLES = 10, por ejemplo,

2. Comenzar con t0 = 0, t1 = 1, s0 = 0ys1 = 1

3. Dejar dt = (t1 - t0) / SAMPLES

4. Dejar ds = (s1 - s0) / SAMPLES

5. Si dt < 1e-10(o cualquier otra condición de precisión que le parezca adecuada), el algoritmo está terminado y la respuesta esF(t0) .

6. SI esta es la primera ejecución del ciclo:

   6.1. Calcule una lista de SAMPLES + 1puntos F( ver arriba ).

   6.2. Calcule una lista de SAMPLES + 1puntos G.

   6.3. Encuentra qué par de puntos están más cerca uno del otro.

   6.4. Actualización t0, t1, s0, s1como se ha visto anteriormente.

7. ELSE : alternativamente, calcule una lista de puntos en F OR una lista de puntos en G, luego encuentre qué punto en Festá más cerca G(s0)y actualice t0y t1, O qué punto de Gestá más cerca F(t0)y actualice s0y s1.

8. Regrese al paso 3.

Cuestiones

Por diseño, estos algoritmos siempre convergerán a un mínimo local. Sin embargo, no hay garantía de que converjan a la mejor solución. En particular, el algoritmo de curva de Bézier no es muy bueno en absoluto, y en el caso de que dos curvas estén cerca una de la otra en muchos lugares, desafortunadamente puede perderse la solución de lejos.

Pero como dije, antes de comenzar a pensar en soluciones más robustas, primero debe experimentar con esas simples.

1) Traslade todo a un eje, de modo que en lugar de tener que calcular la longitud de un punto, la 'línea', la 'línea' es, por ejemplo, el eje Y.

Entonces, dada una curva bezier, diría que depende del número de puntos de control.

Si hay tres, (inicio, 'control' y finalización), haría algún tipo de escaneo (digamos un par de porcentajes y luego refine entre los más cercanos (con un enfoque 'binario').

Más puntos probaría la pareja más cercana al (Eje ​​Y traducido).

Estoy seguro de que un matemático puede darle la solución exacta (en matemáticas), pero si desea encontrar la solución / a en un videojuego, podría estar mejor con una solución ligeramente correcta, ya que la solución real podría contener varias respuestas ( Ni siquiera estoy hablando de poder de procesamiento).

Algunas respuestas de la página del blog Algorithmist , que encuentra correctamente el punto más cercano en la curva bezier cuadrática dada.

Demostración .

Para la curva de Bezier: caso de línea recta, la forma más precisa de encontrar la respuesta es hacer lo siguiente:

1. Transforme el problema para que la línea recta siempre sea horizontal en Y = 0. Esto se hace multiplicando todos los puntos de control por una matriz afín apropiada. (Supongo que está familiarizado con la representación de transformaciones afines del plano con matrices 3x3 con 3 entradas fijas).
2. Inspeccione las coordenadas Y de los puntos de control. Si no todos tienen el mismo signo, puede haber una intersección con la línea. Calcule las raíces de la parte Y de la curva de Bezier. Puede usar cualquier método de búsqueda de raíz para polinomios, hay muchos en la literatura. Por ejemplo, google "marcha convexa del casco": este es un método razonablemente bueno para los polinomios utilizados en las curvas de Bézier. Cada raíz que encuentre es un valor de tiempo de una intersección con la línea, donde la distancia es cero: su trabajo está hecho.
3. Si todas las coordenadas Y tienen el mismo signo, calcule la derivada de la parte Y de la curva de Bezier. Puede ignorar las coordenadas X de los puntos, ya que no hacen ninguna diferencia: la línea objetivo es horizontal. Encuentra las raíces de esa derivada. Estos son los valores de tiempo en los que la curva está localmente más cerca de la línea.
4. Evalúe explícitamente la curva de Bezier para todas las raíces que haya encontrado en el paso anterior e informe la raíz que proporciona la distancia más pequeña desde la línea. También debe verificar los puntos finales, ya que pueden proporcionar una distancia menor que cualquier raíz.