¿Cómo calcular el punto más cercano de una línea y curva? .. o curva y curva?

Question

Teniendo en cuenta los puntos de una línea y una curva de bezier cuadrática, ¿cómo se calcula el punto más cercano?

Answer 1

Solo quiero darte algunas pistas, en el caso del segmento Q.B.Curve //: para obtener un cómputo lo suficientemente rápido, creo que primero deberías pensar en usar una especie de 'caja delimitadora' para tu algoritmo. Say P0 es el primer punto de la QB Curva, P2 el segundo punto, P1 del punto de control, y P3P4 el segmento entonces:

1. distancia Compute de P0, P1, P2 a P3P4
2. si P0 o P2 es el punto más cercano -> este es el punto más cercano de la curva de P3P4. fin: =).
3. si P1 es el punto más cercano y Pi (i = 0 o 1) el segundo punto más cercano, la distancia entre PiPC y P3P4 es una estimación de la distancia que busca que sea sea lo suficientemente preciso, según sus necesidades.
4. si necesita ser más preciso: calcule P1 ', que es el punto en el Q.B.curve el más cercano de P1: lo encuentra aplicando la fórmula BQC con t = 0.5. -> distancia de PiP1 'a P3P4 es una estimación aún más precisa, pero más costosa.
5. Tenga en cuenta que si la línea definida por P1P1 'interseca P3P4, P1' es el punto más cercano de QBC de P3P4.
6. si P1P1' no se cruza P3P4, entonces estás de suerte, hay que ir por el camino difícil ...

Ahora bien, si (y cuando) necesita una precisión:

pensar usando un algoritmo de dividir y conquistar en el parámetro de la curva: que es el más cercano a P3P4 ?? P0P1 'o P1'P2 ??? si es P0P1 '-> t está entre 0 y 0.5, entonces calcule Pm para t = 0.25. ¿Cuál es el más cercano a P3P4? P0Pm o PmP1 '?? si es PmP1 '-> calcular Pm2 para t = 0.25 + 0.125 = 0.375, ¿cuál es el más cercano? PmPm2 o Pm2P1 '??? etc. ¡llegará a una solución precisa en poco tiempo, como 6 iteraciones y su precisión en t es 0.004! puede detener la búsqueda cuando la distancia entre dos puntos se vuelva inferior a un valor determinado. (y no hay diferencia entre dos parámetros, ya que para un pequeño cambio en el parámetro, los puntos pueden estar muy lejos) , de hecho, el principio de este algoritmo es aproximar la curva con segmentos cada vez más precisos.

Para el caso curva/curva, primero los "recuadro" también para evitar cálculos inútiles, así que primero use el segmento/segmento computarizado, luego (tal vez) el cálculo segmento/curva, y solo si es necesario el cálculo curva/curva.

Para curvas/curvas, dividir y conquistar también funciona, es más difícil de explicar, pero es posible que lo resuelva. : =)

espera que usted pueda encontrar su buen equilibrio de velocidad/precisión con esto: =)

Editar: Creo que he encontrado para el caso general una buena solución :-) Usted debe recorrer en el (interior) Triángulos delimitadores de cada BQC Entonces tenemos Triangle T1, puntos A, B, C que tienen el parámetro 't' tA, tB, tC. y Triangle T2, puntos D, E, F, que tienen el parámetro tD, tE, tF. Inicialmente tenemos tA = 0 tB = 0.5 tC = 1.0 y lo mismo para T2 tD = 0, tE = 0.5, tF = 1.0 La idea es llamar a un procedimiento recursivo que dividirá T1 y/o T2 en rectángulos más pequeños hasta que están bien con la precisión alcanzada. El primer paso es calcular la distancia desde T1 a T2, haciendo un seguimiento de los segmentos que fueron los más cercanos en cada triángulo. Primer 'truco': si en T1 el segmento es AC, entonces detiene la recursividad en T1, el punto más cercano en la Curva 1 es A o C. si en T2 el segmento más cercano es DF, entonces detiene la recursividad en T2, el punto más cercano Curve2 es D o F. Si detuvimos la recursividad para ambos -> distancia de retorno = min (AD, AF, CD, CF). entonces si tenemos recursividad en T1, y el segmento AB es el más cercano, el nuevo T1 se convierte en: A '= AB = punto de Curva uno con tB = (tA + tC)/2 = 0.25, C = viejo B. lo mismo vale para T2: aplicar recursividad si es necesario y llamar al mismo algoritmo en T1 nuevo y T2 nuevo. Detener el algoritmo cuando la distancia encontrada entre T1 y T2 menos la distancia encontrada entre las T1 y T2 anteriores está por debajo de un umbral. la función puede parecer ComputeDistance (curveParam1, A, C, shouldSplitCurve1, curveParam2, D, F, shouldSplitCurve2, previousDistance) donde los puntos almacenan también sus parámetros t.

tenga en cuenta que la distancia (curva, segmento) es solo un caso particular de este algoritmo, y que debe implementar la distancia (triángulo, triángulo) y la distancia (segmento, triángulo) para que funcione. Que te diviertas.

Answer 2

El punto en el que las normales partido es su punto más cercano. Quiero decir, dibuja una línea ortogonal a la línea. .si esa línea también es ortogonal a la curva, entonces el punto de intersección es el punto más cercano

Answer 3

1.Simple bad method - por iteración ir por punto desde la primera curva e ir por punto desde la segunda curva y obtener mínimo 2 .Determinar la función matemática de la distancia entre curvas y el límite de calcificación de esta función como:

| Fcur1 (t) -Fcur2 (t) | -> 0

Fs es vector.

creo que podemos calcular la derivada de esto para determinar extremums y obtener más cercanos y más alejados puntos

pienso en esto un poco más tarde, y la respuesta post completo.

Answer 4

Existe un artículo científico con respecto a esta cuestión desde INRIA: Computing the minimum distance between two Bézier curves (PDF here)

Answer 5

formular su problema en términos de análisis estándar: Usted tiene una cantidad para reducir al mínimo (distancia), por lo que usted formula una ecuación para este cantidad y encontrar los puntos donde las primeras derivadas son cero. Parametrice con un solo parámetro usando el parámetro de la curva p, que está entre 0 para el primer punto y 1 para el último punto.

En el caso de línea, la ecuación es bastante simple: Obtenga las coordenadas x/y de la ecuación de la spline y calcule la distancia a la línea dada mediante ecuaciones vectoriales (producto escalar con la línea normal).

En el caso de la curva, la solución analítica podría ser bastante complicada. Es posible que desee utilizar una técnica de minimización numérica como Nelder-Mead o, dado que tiene un problema continuo 1D, bisección simple.

Answer 6

Una vez escribí una herramienta para hacer una tarea similar. Las splines de Bezier son típicamente polinomios cúbicos paramétricos. ¡Para calcular el cuadrado de la distancia entre un segmento cúbico y una línea, este es solo el cuadrado de la distancia entre dos funciones polinomiales, en sí mismo solo otra función polinómica! Tenga en cuenta que dije el cuadrado de la distancia, no la raíz cuadrada.

Esencialmente, para cualquier punto en un segmento cúbico, se podría calcular el cuadrado de la distancia desde ese punto a la línea.Este será un polinomio de sexto orden. ¿Podemos minimizar ese cuadrado de la distancia? Sí. El mínimo debe ocurrir cuando la derivada de ese polinomio es cero. Así que diferencia, obteniendo un polinomio de 5º orden. Use su herramienta de búsqueda de raíz favorita que genera todas las raíces numéricamente. Jenkins & Traub, lo que sea. Elija la solución correcta de ese conjunto de raíces, excluyendo cualquier solución que sea compleja, y solo elija una solución si se encuentra dentro del segmento cúbico en cuestión. Asegúrese de excluir los puntos que corresponden a los máximos locales de la distancia.

Todo esto puede realizarse de manera eficiente y no es necesario utilizar un optimizador iterativo además de un buscador de raíz polinomial, por lo que no es necesario utilizar herramientas de optimización que requieran valores de inicio, encontrando solo una solución cerca de ese valor inicial.

Por ejemplo, en la figura 3-d muestro una curva generada por un conjunto de puntos en 3-d (en rojo), luego tomé otro conjunto de puntos que estaban en un círculo afuera, calculé el más cercano apunte en la curva interna de cada una, dibujando una línea hacia esa curva. Estos puntos de distancia mínima fueron generados por el esquema descrito anteriormente.

Answer 7

En el caso de una curva de Bézier y una línea de

Hay tres candidatos para el punto más cercano a la línea:

1. El lugar en el segmento de curva de Bézier que es paralelo a la línea (si tal lugar existe),
2. Un extremo del segmento de la curva,
3. El otro extremo del segmento de la curva.

Pruebe los tres; la distancia más corta gana.

En el caso de las dos curvas de Bézier

depende de si desea que el resultado analítico exacto, o si un resultado numérico optimizado es lo suficientemente bueno.

resultado analítico

Dados dos curvas de Bézier Un (t) y B (s), puede derivar ecuaciones para su orientación local A ' (t) y B ' (s). Los pares de puntos para los que A ' (t) = B' (s) son candidatos, es decir, el (t, s) para los que las curvas son localmente paralelo.No he comprobado, pero asumir que A ' (t) - B' (s) = 0 se pueden resolver analíticamente. Si sus curvas son parecidas a las que muestra en su ejemplo, debe haber solo una solución o ninguna solución para esa ecuación, pero podría haber dos (o infinitamente muchas en el caso en que las curvas sean idénticas pero se traduzcan, en cuyo caso puede ignorar esto porque el ganador siempre será uno de los puntos finales del segmento de la curva).

En un enfoque similar al del contorno de la caja de línea curva anterior, pruebe cada uno de estos pares de puntos, más los puntos finales del segmento de la curva. La distancia más corta gana.

resultado numérico

Digamos que los puntos de las dos curvas de Bézier se definen como Un ( t) y B (s ). Desea minimizar la distancia d (t, s) = | Un (t ) - B (s ) |. Es un simple problema de optimización de dos parámetros: encontrar el s y t que minimizan d (t, s) con las limitaciones 0 ≤ t ≤ 1 y 0 ≤ s ≤ 1 .

Desde d = SQRT ((xA - xB) ² + (yA - yB) ²), también puede simplemente minimizar la función f (t, s) = [d (t, s)] ² para guardar un cálculo de raíz cuadrada.

Hay numerous ready-made methods para tales problemas de optimización. Escoge y elige.

---

Tenga en cuenta que en los dos casos anteriores, nada de orden superior de las curvas de Bézier cuadráticas puede dador más de un mínimo local, así que esto es algo a tener en cuenta. Según los ejemplos que da, parece que sus curvas no tienen puntos de inflexión, por lo que esta preocupación puede no aplicarse en su caso.