@@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:

nuqneH

Die Frage ist nur, wie die Berwertungsfunktion aussehen soll.

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

Qapla'

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:

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:

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:

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'