Función para devolver una lista de puntos en una curva de Bezier con la misma longitud de arco

Question

Alguien en algún lugar ha tenido que resolver este problema. Puedo encontrar muchos sitios web excelentes que explican este problema y cómo resolverlo. Aunque estoy seguro de que están bien escritos y tienen sentido para los magos de las matemáticas, ese no soy yo. Y aunque podría entender de una manera vaga, no entiendo cómo convertir esa matemática en una función que pueda usar.

Así que te lo ruego, si tienes una función que puede hacer esto, en cualquier idioma, (seguro incluso fortran o diablos 6502 ensamblador) - por favor, ayúdame.

• prefieren una analítica de solución iterativa

EDIT: La intención de especificar que es un Bézier cúbica que estoy tratando de trabajar con ellos.

Answer 1

Lo que está pidiendo es el inverso de la función de longitud del arco. Entonces, dada una curva B, usted quiere una función Linv (len) que devuelva una t entre 0 y 1 tal que la longitud del arco de la curva entre 0 y t es len.

Si tiene esta función, su problema es realmente fácil de resolver. Deje B (0) ser el primer punto. Para encontrar el siguiente punto, simplemente calcula B (Linv (w)) donde w es la "longitud de arco igual" a la que se refiere. Para obtener el siguiente punto, simplemente evalúe B (Linv (2 * w)) y así sucesivamente, hasta que Linv (n * w) sea mayor que 1.

He tenido que lidiar con este problema recientemente. He encontrado o encuentro algunas soluciones, ninguna de las cuales es satisfactoria para mí (pero tal vez sean para ti).

Ahora, esto es un poco complicado, así que déjenme simplemente darle el enlace al código fuente primero: http://icedtea.classpath.org/~dlila/webrevs/perfWebrev/webrev/raw_files/new/src/share/classes/sun/java2d/pisces/Dasher.java. Lo que quieres es en la clase LengthIterator. No debería tener que mirar otras partes del archivo. Hay un montón de métodos que se definen en otro archivo. Para llegar a ellos simplemente corta todo desde/raw_files/hasta el final de la URL. Así es como lo usas. Inicializa el objeto en una curva. Luego, para obtener el parámetro de un punto con longitud de arco L desde el comienzo de la curva, simplemente llame a next (L) (para obtener el punto real simplemente evalúe su curva en este parámetro, usando el algoritmo deCasteljau o la sugerencia de zneak). Cada llamada subsiguiente de next (x) te mueve una distancia de x a lo largo de la curva en comparación con tu última posición. luego devuelve un número negativo cuando te quedas sin curva.

Explicación del código: así que necesitaba un valor t tal que B (0) a B (t) tuviera longitud LEN (donde se conoce LEN). Simplemente aplané la curva. Entonces, simplemente subdivida la curva recursivamente hasta que cada curva esté lo suficientemente cerca de una línea (puedes probar esto comparando la longitud del polígono de control con la longitud de la línea que une los puntos finales). Puede calcular la longitud de esta sub-curva como (controlPolyLength + endPointsSegmentLen)/2. Agregue todas estas longitudes a un acumulador y detenga la recursión cuando el valor del acumulador sea> = LEN. Ahora, llame a la última subcurva C y deje que [t0, t1] sea su dominio. Usted sabe que la t que desea es t0 < = t < t1, y conoce la longitud desde B (0) a B (t0) - llame a este valor L0t0. Entonces, ahora necesita encontrar una t tal que C (0) a C (t) tenga longitud LEN-L0t0. Este es exactamente el problema con el que comenzamos, pero a una escala menor. Podríamos usar recursividad, pero sería terriblemente lento, así que en su lugar usamos el hecho de que C es una curva muy plana. Pretendemos que C es una línea, y calculamos el punto en t usando P = C (0) + ((LEN-L0t0)/longitud (C)) * (C (1) -C (0)). Este punto no se encuentra realmente en la curva porque está en la línea C (0) -> C (1), pero está muy cerca del punto que queremos. Entonces, solo resolvemos Bx (t) = Px y By (t) = Py. Esto es solo encontrar raíces cúbicas, que tiene una solución de fuente cerrada, pero acabo de usar el método de Newton. Ahora tenemos el t que queremos, y podemos simplemente calcular C (t), que es el punto real.

Debo mencionar que hace unos meses hojeé un papel que tenía otra solución para esto que encontró una aproximación a la parametrización natural de la curva. El autor ha publicado un enlace aquí: Equidistant points across Bezier curves