Interpolieren

[otternase]

Hallo

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

Gibt es für folgende Problemstellung eine Lösung in JavaScript bzw. in einer JavaScript Library?

Gegeben ist eine Liste von Vektoren x,y,z. x,y sind dabei nicht irgendwie regelmaessig (kein Grid), sondern "frei verteilt".
Für ein Koordinatenpaar x_s,y_s soll jetzt der z-Wert durch lineare Interpolation bestimmt werden, es sollen dazu drei x,y,z Vektoren aus der gegebenen Liste gesucht werden, die das kleinste Dreieck um x_s, y_s aufspannen und in dieser Ebene soll z_s bestimmt werden (ich hoffe, ich drücke mich da verständlich aus?)

Ich denke, dass ein solches Problem doch auch schon andere vor mir hatten und es daher schon Lösungen dafür geben müsste, oder?

Danke!
Markus

[LX]

Hallo, Markus!

Ein ähnliches Problem hatte ich bereits bei dem Versuch, Clickmaps mit Canvas darzustellen. Leider war die mathematisch korrekte Lösung nicht performant genug, so dass ich stattdessen eine Näherungslösung verwende. Bedauerlicherweise habe ich die erste Lösung nicht aufgehoben, sonst könnte ich sie Dir jetzt schreiben.

Die Lösung sieht aber in etwa so aus, dass Du eine Funktion benötigst, die die jeweilige Entfernung der x/y Werte eines Vektor-Objekts misst und damit die Liste Deiner Objekte sortierst; davon nimmst Du jetzt die ersten 3 und berechnest das Mittel ihrer z-Werte.

Gruß, LX

[Gunnar Bittersmann]

@@LX:

PENIS

nuqneH

Die Lösung sieht aber in etwa so aus, dass Du eine Funktion benötigst, die die jeweilige Entfernung der x/y Werte eines Vektor-Objekts misst und damit die Liste Deiner Objekte sortierst

Nö, „in etwa“ ist weit von einer brauchbaren Lösung entfernt.

Bsp. Für de Punkt[latex]\left( \begin{matrix} x_S \ y_S \end{matrix} \right) = \left( \begin{matrix} 0 \ 0 \end{matrix} \right)[/latex] könnte die Liste der nächsten Punkte so aussehen:

[latex]\left( \begin{matrix} x_1 \ y_1 \ z_1 \end{matrix} \right) = \left( \begin{matrix} 1 \ 0 \ 1 \end{matrix} \right), \quad \left( \begin{matrix} x_2 \ y_2 \ z_2 \end{matrix} \right) = \left( \begin{matrix} 1.1 \ -0.1 \ 0 \end{matrix} \right), \quad \left( \begin{matrix} x_3 \ y_3 \ z_3 \end{matrix} \right) = \left( \begin{matrix} 1.1 \ 0.1 \ 0 \end{matrix} \right), \quad \left( \begin{matrix} x_4 \ y_4 \ z_4 \end{matrix} \right) = \left( \begin{matrix} -2 \ -0.1 \ 0 \end{matrix} \right), \quad \left( \begin{matrix} x_5 \ y_5 \ z_5 \end{matrix} \right) = \left( \begin{matrix} -2 \ 0.1 \ 0 \end{matrix} \right)[/latex]

davon nimmst Du jetzt die ersten 3

Autsch. (xS, yS) liegt überhaupt nicht im Dreieck (x1, y1), (x2, y2), (x3, y3).

Das gesuchte Dreieck wäre in diesem Fall (x1, y1), (x4, y4), (x5, y5).

und berechnest das Mittel ihrer z-Werte.

Nein, auch das nicht.

Qapla'

[Gunnar Bittersmann]

@@Gunnar Bittersmann:

nuqneH

PENIS

Ich war’s nicht, ich schwöre.

Grmpf, lass nie deinen Rechner ungesichert, wenn Kollegen in der Nähe sind!

Qapla'

[Gunnar Bittersmann]

@@Gunnar Bittersmann:

nuqneH

und berechnest das Mittel ihrer z-Werte.

Nein, auch das nicht.

Bsp.: Das für [latex]\left( \begin{matrix} x_S \ y_S \end{matrix} \right) = \left( \begin{matrix} 0.01 \ 0.01 \end{matrix} \right)[/latex] gefundene Dreieck sei

[latex]\left( \begin{matrix} x_1 \ y_1 \ z_1 \end{matrix} \right) = \left( \begin{matrix} 0 \ 0 \ 0 \end{matrix} \right), \quad \left( \begin{matrix} x_2 \ y_2 \ z_2 \end{matrix} \right) = \left( \begin{matrix} 1 \ 0 \ 1 \end{matrix} \right), \quad \left( \begin{matrix} x_3 \ y_3 \ z_3 \end{matrix} \right) = \left( \begin{matrix} 1 \ 1 \ 2 \end{matrix} \right)[/latex]

Der Mittelwert der z-Werte wäre 1. (xS, yS) liegt aber sehr nahe an (x1, y1), also sollte auch zS nahe bei z1 = 0 liegen.

OP: „in dieser Ebene [des Dreiecks] soll z_s bestimmt werden“.

Gesucht ist also der Schnittpunkt der Geraden [latex]\vec r_1 = \left( \begin{matrix} x_S \ y_S \ 0 \end{matrix} \right) + k_1 \vec{e_z}[/latex] mit der Ebene [latex]\vec r_2 = \left( \begin{matrix} x_1 \ y_1 \ z_1 \end{matrix} \right) + k_2 \left( \begin{matrix} x_2 - x_1 \ y_2 - y_1 \ z_2 - z_1 \end{matrix} \right) + k_3 \left( \begin{matrix} x_3 - x_1 \ y_3 - y_1 \ z_2 - z_1 \end{matrix} \right)[/latex]

Qapla'

[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'

[Gunnar Bittersmann]

@@Gunnar Bittersmann:

nuqneH

Die Frage ist nur, wie die Berwertungsfunktion aussehen soll.

Der Flächeninhalt ist offensichtlich nicht geeignet, womöglich aber der Umfang.

Qapla'

[Wouzhuo]

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

???

O(n³) in Javascript ist doch wohl eher nicht empfehlenswert. Da reichen ja schon 1000 Vektoren und gute Nacht ist.

[Gunnar Bittersmann]

@@otternase:

nuqneH

Möglicher Algorithnus:

1. verschiebe das Koordinatensystem so, dass der Punkt S(xS, yS) im Ursprung liegt, rechne die Koordinaten aller Punkte in Polarkoordinaten um

2. sortiere die Punkte nach aufsteigendem Radius ➝ Liste A

3. wähle die ersten 3 Punkte aus der Liste P ➝ Liste B

4. wenn der Punkt S (Urprung) innerhalb des aus den Punkten der Liste B gebildeten Dreiecks liegt, nimm dieses

andernfalls:

5. solange die Liste C leer ist:

5.1. wähle den nächsten Punkt P aus der Liste A

5.2 bilde alle Dreiecke, die sich aus dem Punkt P und jeweils 2 Punkten der Liste B bilden lassen und bei denen der Punkt S (Urprung) innerhalb liegt ➝ Liste C

6. wähle aus der Liste C dasjenige Dreieck mit dem kleinsten Umfang.

Qapla'

[Gunnar Bittersmann]

@@Gunnar Bittersmann:

nuqneH

Oops, die Fußnoten vergessen.

1. verschiebe das Koordinatensystem so, dass der Punkt S(xS, yS) im Ursprung liegt, rechne die Koordinaten aller Punkte in Polarkoordinaten um
2. sortiere die Punkte nach aufsteigendem Radius ➝ Liste A
3. wähle die ersten 3 Punkte aus der Liste P ➝ Liste B

Das deckt sich mit LX’ Ansatz, „dass Du eine Funktion benötigst, die die jeweilige Entfernung der x/y Werte eines Vektor-Objekts misst und damit die Liste Deiner Objekte sortierst; davon nimmst Du jetzt die ersten 3“.

4. wenn der Punkt S (Urprung) innerhalb des aus den Punkten der Liste B gebildeten Dreiecks liegt, nimm dieses
   andernfalls:

Die Fallunterscheidung hatte LX vergessen.

Die Prüfung sollte sich in Polarkoordinaten einfach einfach erledigen lassen: Eine der beiden Differenzen des Arguments eines Punkt des Dreiecks zu den Argumenten der beiden anderen Punkte (bei gleichem Drehsinn!) muss kleiner oder gleich π (180°) sein, die andere größer oder gleich π; wobei nicht bei beiden das Gleichheitszeichen gelten darf.

Qapla'

[Gunnar Bittersmann]

@@Gunnar Bittersmann:

nuqneH

5. solange die Liste C leer ist:

5.1. wähle den nächsten Punkt P aus der Liste A

5.2 bilde alle Dreiecke, die sich aus dem Punkt P und jeweils 2 Punkten der Liste B bilden lassen und bei denen der Punkt S (Urprung) innerhalb liegt ➝ Liste C

Da fehlt noch eine Kleinigkeit:

5.3. Füge Punkt P zur Liste B hinzu

Qapla'

[Gunnar Bittersmann]

@@Gunnar Bittersmann:

nuqneH

Möglicher Algorithnus:

Bleibt zu erwähnen, dass dieser Algorithmus zur erwähnten Kategorie zählt, die eine gute Lösung finden, aber nicht notwendigerweise die beste.

Bsp.: in Polarkoordinaten: [latex]P_1(1,0), P_2(1, \tfrac{2}{3} \pi), P_3(1, \tfrac{4}{3} \pi), P_4(1.001, \pi)[/latex]

Der Algorithmus gibt das Dreieck P₁P₂P₃ mit einem Umfang von 3 · √3 ≈ 5.196 aus, obwohl das Dreieck P₁P₂P₄ mit knapp über 3 + √3 ≈ 4.732 einen kleineren Umfang hat.

Qapla'