kurse:ef05a-2021:kurven:distance-to-bezier [https://fginfo.ksbg.ch Fachgruppe Informatik der KSBG]

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== 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):

{{:kurse:ef05a-2021:kurven:pasted:20211215-092429.png}} {{:kurse:ef05a-2021:kurven:pasted:20211215-120427.png}} {{:kurse:ef05a-2021:kurven:pasted:20211215-113709.png}}

{{kurse:ef05a-2021:kurven:bezier-distance.zip}}
===== Mögliche Ansätze =====

Code zum Starten: {{kurse:ef05a-2021:kurven: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:
<code maxima>
/* 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));
</code>

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

Maxima online: http://maxima.cesga.es/
===== Abschätzung des Rechenaufwands =====
Dazu soll jeder Pixel eines 500x500 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.


===== Anwendung: Herz =====
<code python>
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])];
</code>


{{:kurse:ef05a-2021:kurven:pasted:20220106-090342.png}}