Distanz zu einer Bezierkurve

Die Distanz eines Punktes $P$ zu einem geometrischen Objekt $q$ ist definiert als die kleinstmögliche Distanz $\overline{QP}$ mit $Q \in q$.

Im Falle einer Bezierkurve $p(t)$ suchen wir den Parameter $t$, der die Distanz zu einem gegebenen Punkt minimiert.

Will man diese Berechnung für unseren Christbaum brauchen, ist die Genauigkeit sekundär. Auf 1% genau reicht bereits. Ziel ist es, möglichst schnell auf diese Genauigkeit zu kommen.

Naive, ungenaue Methode: 2min (auf guter Maschine), dann genauere Methode, immer noch 2min, dann analytisch (20 sec):

bezier-distance.zip

Code zum Starten: bezier-distance.zip

• $n$ Punkte auf der Kurve wählen, Distanz ist gleich der minimalen Distanz zu diesen Punkten.
• Quadrierte Distanz $f(t)$ minimieren. $f(t)$ ist ein Polynom vom Grad 6.

Um die Koeffizienten dieses Polynoms zu berechnen nehmen wir die Hilfe von Maxima (Mathematik-Programm) und einem Python-Code in Anspruch:

/* Maxima Code zur Berechnung der Koeffizienten von f */
/* Bezier Polynom */
p(t,a,b,c,d):=(1-t)^3*a+3*(1-t)^2*t*b+3*(1-t)*t^2*c+t^3*d;
 
/* Quadrierte Distanz-Funktion */
d2(t):=(p(t,ax,bx,cx,dx)-x)^2+(p(t,ay,by,cy,dy)-y)^2;
 
/* Alles ausmultiplizieren */
f:expand(d2(t));
 
/* Koeffizienten der Potenzen von t extrahieren: */
string(create_list(factor(coeff(f,t,i)), i, 0,6));

And down the rabbit hole: https://en.wikipedia.org/wiki/Real-root_isolation

Maxima online: http://maxima.cesga.es/

Dazu soll jeder Pixel eines 500×500 Pixel grossen Fensters mit einer Farbe eingefärbt werden, deren Farbton proportional zur Distanz zu einer gegebenen Bezierkurve ist. Dabei sollen benötigte Zeit und Qualität des Bildes verglichen werden.

pts = [Vector([0.5,0.7]), Vector([0.5,1.1]), Vector([1, 1.1]), Vector([1,0.7]),\
       Vector([1,0.7]), Vector([1, 0.3]), Vector([0.5,0.2]), Vector([0.5,0])];