Encontrar puntos en una curva bezier basada en la distancia desde otro punto

Question

Tengo una curva de bezier cúbico 3D y un punto de inicio en cualquier punto de la curva y necesito encontrar un segundo punto más abajo de la curva que es una distancia de espacio mundial específica (distancia de arco no distancia) lejos del primer punto.

Otro problema sería si el segundo punto llega al final de la curva y todavía no estaba a la distancia del espacio mundial deseada, en cuyo caso me gustaría que continúe por la tangente hasta que se alcance la distancia.

¿Alguna idea?

Answer 1

Por desgracia, no conozco ninguna ecuación de forma cerrada que le proporcione el (los) punto (s) que desea. Quizás la técnica más simple para aproximarse a ese punto sea cortar recursivamente la curva de Bezier en 2 curvas de Bezier más pequeñas usando de Casteljau's algorithm. La recursividad toca fondo cuando (a) todos los puntos de límite para la curva están demasiado cerca o demasiado lejos del punto dado, o (b) todos los puntos de límite para la curva son "lo suficientemente cerca" de ser igual a la distancia deseada (quizás todos encajen dentro del mismo píxel).

Estoy bastante seguro de que el número máximo de puntos en una curva de Bezier dada que son una distancia lineal dada de un punto dado es de 4 puntos. (Esto puede suceder cuando la curva de Bezier dada tiene una auto intersección).

EDIT:

Tal vez debería leer toda la pregunta antes de saltar con una respuesta, ¿verdad? El segmento de curva de Bezier estándar de "cuatro puntos" se puede ver como una pieza de una curva cúbica infinitamente larga. Puede haber un doblez o bucle o cúspide en un lugar, pero lo suficientemente lejos de esa curva cerrada el camino se aplana para acercarse a 2 rayos rectos, cada uno de los cuales apunta en una dirección arbitraria. Desgraciadamente, la solución anterior solo encuentra puntos que se encuentran en el segmento corto de la curva Bezier. Supongo que quiere los puntos a lo largo de esa curva cúbica infinitamente larga que están a una distancia dada del punto dado, incluso si no están en el segmento corto de la curva Bezier.

== == de Casteljau en reversa

Usted podría funcionar (punto medio recursivo) de algoritmo de Casteljau en sentido inverso, generando un nuevo cuatro puntos de la curva de Bezier "doble" del tamaño de la última en cada iteración, hasta tienes uno lo suficientemente grande como para incluir el (los) punto (s) deseado (s). (Cuando los 4 puntos iniciales están "demasiado cerca" del punto dado, se garantiza que la duplicación eventualmente producirá un segmento de curva con el punto de inicio "demasiado cerca", el punto final "demasiado lejos", y luego puede usar el anterior algoritmo para converger en un punto que está a la distancia deseada del punto dado). Este enfoque depende solo de la suma, la resta, la multiplicación por dos y el promedio, por lo que en principio debería ser relativamente numéricamente robusto. (En realidad, nunca evalúa la fórmula cúbica en ningún lugar t).

== == cero hallazgo

Se puede convertir de la representación de cuatro puntos para la representación polinómica cúbica, y utilizar cualquier algoritmo de búsqueda de raíz para converger en uno de los puntos deseados. El método de Newton debería funcionar bastante bien, ya que las piezas cortas de una curva de Bezier son casi rectas. ¿Podríamos adaptar las ecuaciones de métodos de Newton de Finding the Minimum Distance Between a Point and a Cubic Spline a este problema? Usaré el algoritmo de bisección para simplificar la descripción, aunque eso sea más lento que el método de Newton.

Como siempre, un segmento cúbica curva de Bezier se puede describir como

B(t) = (1-t)^3 * P0 + 3*(1-t)^2*t*P1 + 3*(1-t)*t^2*P2 + t^3*P3. 

(Por desgracia, esta ecuación no siempre es numéricamente robusto - es por eso que muchas personas usan reducir a la mitad recursiva utilizando de algoritmo de Casteljau en su lugar).

Estoy suponiendo que tiene (o puede encontrar) el valor t_given para su punto dado,

x_given = B(t_given).x 
y_given = B(t_given).y 

La distancia entre el punto dado y algún otro punto de la curva está dada por teorema de Pitágoras,

distance2(t) = (x_given - B(t).x)^2 + (y_given - B(t).y)^2. 
distance(t) = sqrt(distance2(t)). 

el punto (s) que buscas están en los ceros de la función

given_distance2 = given_distance^2. 
f(t) = distance2(t) - given_distance2. 

Suponiendo que la distancia dada no es cero, y el punto dado tiene un algoritmo t_given < 1, la bisección correría algo así como

left = t_given 
right = 1 // the endpoint of the given Bezier curve segment 
while(distance2(right) < given_distance2){ 
    right = right*2 
} 

En este punto, el t_left está más cerca del punto dado que la deseada distancia, y t_right está más lejos que la distancia deseada (o tal vez exactamente igual). Dado que tenemos un punto demasiado cerca, y otro punto demasiado lejos, el algoritmo de bisección debería funcionar.

while((abs(f(right) is too big) AND (abs(left - right) is too big)){ 
    // find midpoint 
    midpoint = (t_left + t_right)/2 

A continuación, verificamos: ¿queda el primer segmento ... el punto medio contiene el cero, o el punto medio ... ¿no?

if(f(left)*f(midpoint) < 0) then 
     // throw away right half 
     right = midpoint 
    else 
     // throw away left half 
     left = midpoint 
} 

return(right) 

En este punto, el valor "correcto" es el valor de t, y B (derecha) es el punto correspondiente, tal que la distancia desde ese punto hasta el punto dado original es (aproximadamente) el dado distancia.

Answer 2

Tu declaración del problema necesita un toque más refinado. Específicamente, usted está poco restringido al solicitar un punto B que está N unidades lejos del punto de inicio A. Puede haber múltiples puntos que son N distancia de A.

Dejando de lado lo que le impide muestrear su curva en el conjunto intervalos a lo largo de la curva y luego calcular una distancia lineal de regreso a A. No es óptimo, pero funcionaría. Para manejar varios puntos N a distancia, tendrá que idear una regla. Podría ser tan simple como el primer punto encontrado.