kleine Geometrieaufgabe. Schlaue Lösung gesucht.

**micky_ficky** · 17.08.2009, 23:15

hm, mal ne ganz doofe Idee, aber wenn du deinen Startpunkt (F) den Punkt der bei Drehung des Startpuntks um 70° in Drehrichtung entsteht (F') hast, dürfte es das schnellste sein, die quadratischen Abstände aller Punkte sowohl zu F als auch zu F' zu berechnen (d(A,B) ist im folgenden der Euklidische Abstand zwischen A und B)
d1(i)=(d(P(i),F))²
d2(i)=(d(P(i),F'))²
dann berechnest noch den Abstand von F zu F'
d0 = d(F,F')

Jetzt gehst einfach her und sortierst alle Punkte aus die nicht im gewünschten Bereich liegen (Pseudocode):
j=0
for i
if d1(i) < d0 AND d2(i) < d0
sort_array(j,1) = i
sort_array(j,2) = d1(i)
j=j+1
end if
end for

Dann musst dein sort_array nur noch aufsteigend nach der 2. Spalte sortieren lassen (sortiertes array ist dann sorted_array). dann ist sorted_array(1,1) das i das zum besten Punkt gehört.

Der Rechenaufwand is recht gering da du nur Additionen und Multiplikationen(hoffe der Controller hat n Multiplizierwerk, sonst wirds knifflig), ne kurze Schleife (da wenige Punkte), 2 Vergleiche pro Punkt und n Sort-Algorithmus (der ja extrem fix ist) brauchst.

Wenn du ne wirklich optimale Lösung suchst oder dein Controller kein Multiplizierwerk hat wirds schwieriger.
Es dürfte theoretisch möglich sein die Abstandsberechnung wegzulassen und das ganze nur mit ifs zu machen, aber das is fummelig.
Wenn du ne halbwegs schöne Lösung suchst müsste das obere nahe am Optimum sein. Funktioniert übrigens für alle Vorgabewinkel (bei dir 70°) solang se strikt kleiner als 180° sind. Ist dann auch eindeutig (solang die Punkte paarweise verschieden sind).

MfG
Daniel

**Besserwessi** · 17.08.2009, 23:38

Die Version mit dem Skalar und Vektorprodukt dürfte noch etwas schneller sein. Da braucht man nur 4 Multiplicationen und 2 Additionen, und bei rund der Hälfte der Werte könnte man schon nach der Hälfte aufhöhren weil die Drehung in die Falsche Richtung geht.

Die Berechnung der Abstände braicht ein klein wenig mehr: Für die Differenzen braicht man schon 4 Subtraktionen. Dann 4 Quadrate (wie Multiplicationen) und dann noch 2 Summen. Ohne Multiplications hardware ist der Unterschied aber wohl klein.

**micky_ficky** · 18.08.2009, 00:08

Hab die Beiträge zur Kreuz-/Skalarproduktlösung überlesen, hast recht da spar ich mir 2 Subtraktionen pro Abstand (das Weglassen von Berechnungen ginge bei meiner Version genauso).

Man könnte dann auch immer den aktuellen cos-Wert mit dem bisher kleinsten vergleichen und den dann auf den aktuellen Wert setzen falls dieser kleiner ist. So würde man einiges an Zeit sparen falls nicht extrem viele Register auf dem µC vorhanden sind (man muss nicht jeden Wert in den Speicher schreiben, und dann beim Sortieren wieder abrufen. Sortieren fällt dann auch ganz weg und Speicherzugriffe brauchen bei µCs meine ich auch immer n paar Takte).