Interpolieren

[Gunnar Bittersmann]

@@otternase:

nuqneH

-vorweg: ich bin Anfänger in Sachen JavaScript-

Das tut erstmal wenig zur Sache. Erstmal solltest du dir Gedanken machen, WAS du eigentlich berechnen willst.

es sollen dazu drei x,y,z Vektoren aus der gegebenen Liste gesucht werden, die das kleinste Dreieck um x_s, y_s aufspannen

Ich glaube nicht, dass du das willst.

Bsp.:
[latex]\left( \begin{matrix} x_S \ y_S \end{matrix} \right) = \left( \begin{matrix} 0.1 \ 0 \end{matrix} \right), \quad \left( \begin{matrix} x_1 \ y_1 \end{matrix} \right) = \left( \begin{matrix} 0 \ 0 \end{matrix} \right), \quad \left( \begin{matrix} x_2 \ y_2 \end{matrix} \right) = \left( \begin{matrix} 1000 \ -0.0001 \end{matrix} \right), \quad \left( \begin{matrix} x_3 \ y_3 \end{matrix} \right) = \left( \begin{matrix} 1000 \ 0.0001 \end{matrix} \right), \quad \left( \begin{matrix} x_4 \ y_4 \end{matrix} \right) = \left( \begin{matrix} 1 \ -1 \end{matrix} \right), \quad \left( \begin{matrix} x_5 \ y_5 \end{matrix} \right) = \left( \begin{matrix} 1 \ 1 \end{matrix} \right)[/latex]

Das Dreieck (x1, y1), (x2, y2), (x3, y3) hat die Fläche 1/10; das Dreieck (x1, y1), (x4, y4), (x5, y5) hat die Fläche 1. Willst du wirklich das kleinere der beiden, obwohl zwei seiner Punkte weit entfernt von (xS, yS) liegen?

Dann kannst du dir Gedanken machen, WIE du es berechnen willst. Wie hoch ist die Anzahl n deiner Punkte? Genügt dir eine gute Lösung (weniger Rechenaufwand) oder willst du die beste?

Ein Algorithmus für beste Lösung könnte so aussehen:

Für alle [latex]\tbinom{n}{3} = \tfrac{1}{6} n (n-1)(n-2)[/latex] Kombinationen von 3 der n Punkte:
Berechne die Bewertung des entstehenden Dreiecks
Wenn Bewertung besser als bisher gefundenes Optimum setze Optimum = aktuelles Dreieck

Der Algorithmus hat eine Laufzeit von O(n³), sollte also auch bei großen n noch praktikabel sein.

Die Frage ist nur, wie die Berwertungsfunktion aussehen soll.

Qapla'