¿Qué algoritmo determina la cercanía de un punto a una curva de Bezier?

Question

Deseo determinar cuándo un punto (posición del mouse) está activado o cerca de una curva definida por una serie de puntos de control B-Spline.

La información que tendré para B-Spline es la lista de n puntos de control (en coordenadas x, y). La lista de puntos de control puede ser de cualquier longitud (> = 4) y definir una B-spline que consta de (n-1)/3 curvas cúbicas de Bezier. Las curvas de Bezier son todas cúbicas. Deseo establecer un parámetro k, (en píxeles) de la distancia definida para estar "cerca" de la curva. Si la posición del mouse está dentro de k pixeles de la curva, entonces necesito devolver verdadero, de lo contrario, falso.

Hay un algoritmo que me da esta información. Cualquier solución no necesita ser precisa: estoy trabajando con una tolerancia de 1 píxel (o coordenada).

He encontrado que las siguientes preguntas parecen ofrecer algo de ayuda, pero no responden mi pregunta exacta. En particular, la primera referencia parece ser una solución solo para 4 puntos de control, y no tiene en cuenta el factor de proximidad que deseo definir.

Position of a point relative to a Bezier curve

Intersection between bezier curve and a line segment

EDIT: Una curva de ejemplo:

e, 63.068, 127.26 
    29.124, 284.61 
    25.066, 258.56 
    20.926, 212.47 
     34, 176 
    38.706, 162.87 
    46.556, 149.82 
    54.393, 138.78 

La descripción del formato es: "Cada borde se le asigna un atributo pos, que consiste en una lista de Ubicaciones 3n + 1. Estos son puntos de control B-spline: los puntos p0, p1, p2, p3 son la primera spline de Bezier, p3, p4, p5, p6 son los segundos, etc. Los puntos están representados por dos enteros separados por una coma , representante resentir las coordenadas X e Y de la ubicación especificada en puntos (1/72 de pulgada). En el atributo pos, la lista de puntos de control puede estar precedida por un punto de inicio ps y/o un punto final pe. Estos tienen la representación posición habitual con un "s", o "e" prefijo, respectivamente "

Edit2: explicación adicional de la ". E" punto (y s si está presente)

En el atributo pos, la lista de puntos de control puede estar precedida por un punto de inicio ps y/o un punto final pe. Estos tienen la representación de posición habitual con un prefijo "s" o "e", respectivamente. el punto está presente si hay una flecha en p0. En este caso, la flecha es de p0 a ps, donde ps está realmente en el límite del nodo La longitud y dirección de la punta de flecha viene dada por el vector (ps -p0) Si hay no hay flecha, p0 está en el límite del nodo. De manera similar, el punto pe designa una flecha en el otro extremo del borde, que se conecta al último punto de spline.

Answer 1

Puede hacer esto de manera analítica, pero se necesita un poco de matemática.

Una curva de Bezier se puede expresar en términos del Bernstein Basis. Aquí usaré Mathematica, que proporciona un buen soporte para las matemáticas involucradas.

Así que si usted tiene los puntos:

pts = {{0, -1}, {1, 1}, {2, -1}, {3, 1}}; 

El eq. para la curva de Bezier es:

f[t_] := Sum[pts[[i + 1]] BernsteinBasis[3, i, t], {i, 0, 3}]; 

Tenga en cuenta que estoy usando la base Bernstein por conveniencia, pero cualquier representación paramétrica de la curva de Bezier haría.

que da:

ahora para encontrar la distancia mínima a un punto (digamos {3, -1}, por ejemplo) hay que minimizar la función:

d[t_] := Norm[{3, -1} - f[t]]; 

Para hacer eso, necesitas un algoritmo de minimización. Tengo uno a mano, por lo que:

NMinimize[{d[t], 0 <= t <= 1}, t] 

da:

{1.3475, {t -> 0.771653}} 

Y eso es todo.

HTH!

Editar En cuanto a su edición "B-spline con que consiste en (n-1)/3 curvas cúbicas de Bezier."

Si construyó una representación B-spline por partes, debe repetir en todos los segmentos para encontrar los mínimos. Si se unió a las piezas en un parámetro continuo, entonces este mismo enfoque lo hará.

Editar

la solución de su curva. Desprecie el primer punto porque I Realmente no entendí de qué se trata.

Lo resolví usando BSplines estándar en lugar de las funciones de mathematica, en aras de la claridad.

Clear["Global`*"]; 
(*first define the points *) 
pts = {{ 
     29.124, 284.61}, { 
     25.066, 258.56}, { 
     20.926, 212.47}, { 
     34, 176}, { 
     38.706, 162.87}, { 
     46.556, 149.82}, { 
     54.393, 138.78}}; 

(*define a bspline template function *) 

b[t_, p0_, p1_, p2_, p3_] := 
        (1-t)^3 p0 + 3 (1-t)^2 t p1 + 3 (1-t) t^2 p2 + t^3 p3; 

(* define two bsplines *) 
b1[t_] := b[t, pts[[1]], pts[[2]], pts[[3]], pts[[4]]]; 
b2[t_] := b[t, pts[[4]], pts[[5]], pts[[6]], pts[[7]]]; 

(* Lets see the curve *) 

Show[Graphics[{Red, Point[pts], Green, Line[pts]}, Axes -> True], 
ParametricPlot[BSplineFunction[pts][t], {t, 0, 1}]] 

. (! Girada por espacio de pantalla de ahorro)

(*Now define the distance from any point u to a point in our Bezier*) 
d[u_, t_] := If[(0 <= t <= 1), Norm[u - b1[t]], Norm[u - b2[t - 1]]]; 

(*Define a function that find the minimum distance from any point u \ 
to our curve*) 
h[u_] := NMinimize[{d[u, t], 0.0001 <= t <= 1.9999}, t]; 

(*Lets test it ! *) 
Plot3D[h[{x, y}][[1]], {x, 20, 55}, {y, 130, 300}] 

Esta parcela es la (mínimo) la distancia desde cualquier punto en el espacio a nuestra curva (por supuesto el valor sobre la curva es cero):

Answer 2

En primer lugar, renderice la curva en un mapa de bits (blanco y negro) con su algoritmo favorito. Luego, cuando lo necesite, determine el píxel más cercano a la posición del mouse con información del this question. Puede modificar la función de búsqueda para que regrese la distancia, de modo que pueda compararla fácilmente con sus requisitos. Este método te da la distancia con tolerancia de 1-2 píxeles, lo que hará, supongo.

Answer 3

Definición: distancia de un punto a un segmento de línea = distancia desde el punto original hasta el punto más cercano st enfermo en el segmento.

Asunción: se conoce algo para calcular la distancia desde un punto a un segmento (por ejemplo, calcular la intersección con el segmento de la normal al segmento que pasa por el punto original.Si la intersección está fuera del segmento, escoger el punto final más cerca del segmento)

1. utiliza el deCasteljau algo y subdividir el cúbicas hasta llegar a un buen suficiente de cadena de margarita de segmentos lineales. Supplementary info"aplanamiento de la curva de Bezier" sección
2. considere el mínimo de las distancias entre su punto y los segmentos resultantes como la distancia desde su punto a la curva. Repita para todas las curvas en su conjunto.

Refinamiento en el punto 2: no calcule la distancia real, pero el cuadrado de la misma, obteniendo la distancia cuadrada mínima, es suficiente: guarda una llamada/segmento sqrt.

esfuerzo de cálculo: empíricamente una curva cúbica con una extensión máxima (es decir, cuadro delimitador) de 200-300 resultados en aproximadamente 64 segmentos de línea cuando aplanada para una tolerancia máxima de 0,5 (aprox suficientemente bueno para el ojo desnudo).

1. Cada paso deCasteljau requiere 12 divisiones por 2 y 12 incorporaciones.
2. Evaluación de uniformidad - 8 multiplicaciones + 4 adiciones (si usa la distancia TaxiCab para evaluar una distancia)
3. la evaluación de la distancia punto a segmento requiere un máximo de 12 multiplicaciones y 11 adiciones, pero esto será un caso raro en el contexto del aplanamiento de Bezier, esperaría un promedio de 6 multiplicaciones y 9 adiciones.

Por lo tanto, asumiendo un caso muy malo (100 segmentos rectos/cúbicos), termina en encontrar su distancia con un costo de aproximadamente 2600 multiplicaciones + 2500 adiciones por cúbico considerado.

Aviso legal:

1. no me pida una demostración de los números en la evaluación esfuerzo de cálculo anterior, voy a responder con "Use the source-code" (nota: la ejecución de Java).
2. otros enfoques pueden ser posibles y tal vez menos costosos.

Saludos,

Adrian Colomitchi