Approximativement une liste de points avec une courte liste de courbes de Bézier

Question

J'ai une liste de (x, y) points. Je sais comment faire une liste de courbes de Bézier qui traversent tous ces points et qui ont un premier dérivé continu (et second, bien que moins important). Cependant, la liste avec laquelle je me retrouve est beaucoup trop longue. Je préférerais approximer les points que j'ai si cela me permet de réduire le nombre de courbes que j'ai. Je voudrais pouvoir passer un paramètre de la proximité d'une approximation ou d'un nombre maximum de courbes, de préférence les premières. La raison pour laquelle je veux ceci est que le résultat final aura une interface graphique où les utilisateurs peuvent éditer les courbes de Bézier, et il n'est pas critique que les courbes traversent exactement chaque point, tant qu'elles sont proches. Plus de courbes rend plus difficile à éditer.

EDIT: Plus d'informations sur le but de cette. J'essaie de faire un logiciel de retouche d'image. Quand quelqu'un charge un bitmap, je veux être capable de tracer une ligne centrale. Potrace est ce que je voudrais utiliser pour tracer le contour d'une forme, mais cela ne fonctionnera pas pour tracer des traits. J'ai pu identifier beaucoup de points le long de la ligne centrale, et je veux transformer ces données en une liste de courbes de Bézier connectées. La raison pour laquelle je ne veux pas faire une spline de Bézier est qu'il y aura trop de points de contrôle pour que cela soit facile à éditer. "Trop" n'est pas un terme facile à définir, mais j'aimerais pouvoir passer un paramètre pour limiter le nombre de courbes. Soit une fonction qui minimise la distance entre les courbes et les points en fonction d'un nombre maximal de courbes, soit une fonction qui minimise le nombre de courbes en fonction d'un écart maximal par rapport aux points.

Answer 1

Plusieurs approches existent pour réaliser ce que vous voulez faire:

1) Utiliser algorithme RDP pour réduire le nombre de points, puis créer une liste des courbes de Bézier passant à travers les points restants. 2) Utiliser des algorithmes d'ajustement de courbe (par exemple, l'algorithme de Schneider) pour produire plusieurs courbes de Bézier connectées à la continuité G1 (tangente). Vérifiez la mise en œuvre de l'algorithme Schneider dans ce link.

3) Utiliser le raccord le moins carré avec B-spline pour produire une seule courbe B-spline. Du point de vue de la mise en œuvre, l'approche 1 est probablement la plus facile pour vous car vous savez déjà comment créer des courbes de Bézier en interpolant une liste de points. L'approche 3 sera beaucoup plus difficile à implémenter et vous devrez probablement convertir la courbe B-spline en courbes de Bézier afin de les utiliser au niveau de l'interface utilisateur. Veuillez vous référer à ce SO article pour une discussion détaillée.