kleine Geometrieaufgabe. Schlaue Lösung gesucht.

[yaro]

Hallo Leute,
ich muss für mein Projekt eine kleine Geometrieaufgabe lösen und wollte sie euch nicht vorenthalten =)
Lösungen sollte es ziemlich viele geben, und ich suche die, die am wenigstens rechenleistung braucht.
Ich selber habe in 10 min 2 Lösungen gefunden, denke aber, dass es noch bessere gibt.
Naja, hier die Aufgabe:
Man hat eine strecke, die um einen Punkt (ein Ende dieser Strecke) gedreht wird. Somit beschreibt das andere Ende der Strecke einen Kreis.
Auf diesem Kreis sind Punkte. Ich möchte den kleinsten Winkel herausfinden, den die sich drehende Strecke braucht um einen dieser Punkte zu berühren. Dabei muss man beachten, dass die Strecke sich definiert entweder im oder gegen den Uhrzeigersinn dreht. Der maximale Winkel darf nicht höher als 40° sein. Wenn es keinen gibt, der kleiner als 40° ist, dann ist es eben so =)

Ich habe im Anhang eine Zeichnung hinzugefügt, um es etwas deutlicher zu machen.

Gruß, Yaro

[loonquawl]

Mir ist die Aufgabe unklar...

Ist die Anfangsposition des Zeigers nicht bekannt, oder wechseln die Punkte ihre Position, oder wie? Ansonsten P(1..i)-Z, Modulo360(oder 2Pi), Minimum suchen.

[SprinterSB]

Am einfachsten bildet man den Umfang auf das Intervall [0,1) ab und hat dort eine ziemlich einfache Arithmetik:

Zwei Zahlen werden addiert, indem man sie zusammenzählt und die Vorkommastellen wegwirft.

Winkel bzw. Punkte auf der Kreislinie stehen also so im Zusammenhang mit den Zahlen in [0,1):

0° -> 0
60° = pi/3 -> 1/6
90° = pi/2 -> 1/4
...
360° = 2 pi -> 1 = 0


Eine Drehung um 40° enstpricht einer Addition von 1/9, eine Drehung um -40° einer Addition von -1/9 bzw. Subtraktion von 1/9.

Um den nächsten Punkt zu finden, musst du nur nach der nächstgrößeren Zahl suchen. Problem ist, daß bei diesen zyklischen Werten keine vernünftige Ordnungrelation besteht.

Steht dein Ding zB bei 0.9, dann ist der nächstgrößerer Wert dein Ergebnis. Allerdings reicht 0.9+1/9 über die 1 hinaus, so daß es zu einem Überlauf kommt. Daher sind auch noch die Werte 1=0...1/9-0.1=0.9+1/9 in die Überlegung einzubeziehen.

[yaro]

Anfangsposition bekannt. Punkte auch bekannt.

[loonquawl]

Wenn sowohl die Punkte, alsauch der Zeiger am Anfang bekannt sind, sehe ich keine Geometrie-Aufgabe, sondern nur eine Optimisierung eines Algorithmus - und dafür wären ein paar Ranbedingungen interessant - in welcher Sprache wird das realisiert, sind die Punkte in x/y Koordinaten oder in radians, oder in Grad definiert, oder noch anders, beispielsweise in +-180°, Ist der Zeiger in der selben Art definiert....





Ansonsten P(1..i)-Z, Modulo360(oder 2Pi), Minimum suchen.

[Netzman]

Wenn die Punkte fix & deren Winkel bekannt ist, ist es glaube ich am schnellsten die Punkte in einem Array nach Winkel zu sortieren und zur Laufzeit mit Binary Search den nächsten Punkt zu suchen.

mfg

[yaro]

edit:
@Sprinter: Habe wohl gleichzeitig mit dir geschreiben, sodass ich deinen Beitrag übersprungen habe.
Soweit ich das verstanden habe, muss ich dazu den Winkel kennen, unter dem die Punkte auftauchen, ich kenne aber nur die Koordinaten der Punkte. Um den Winkel herauszufinden müsste ich dann noch zusätzliche Rechnungen durchführen. Das ist es ja, was ich vermeiden will.
Korrigier mich bitte, wenn ich dich nicht richtig verstanden habe.

Gruß, Yaro

[yaro]

Alles findet im Kartesischen Koordinatensystem statt, Koordinaten der Punkte sind bekannt. Winkel zu den Punkten sind nicht bekannt.
Ich schreibe in C.

Gruß, Yaro

[loonquawl]

Genügt es da nicht, abs(xp-xz)+abs(yp-yz) zu rechnen und den Punkt mit dem kleinsten Wert auszuwählen?

sorry für die Antwort-als-Edit, wusste nicht, dass du schon geantwortet hast.

ccw/cw Entscheidung bringt mich auch immer zum Weinen, da interessiert mich die Lösung sehr :-)

[yaro]

Es gibt nicht viele Punkte, höchstens 4 insgesammt oder so.
Das Problem ist eben, dass man nicht ganz so leicht herausfinden kann, ob ein Winkel sich im oder gegen den Uhrzeigersinn befindet. (Den winkel kann man ja mit dem Cosinussatz berechnen.)

Gruß, Yaro

[Besserwessi]

Wenn die Zahl der Punkte recht groß ist, könnte es am schnellsten gehen, das koordinatensystem zu drehen, so das der Startpunkt des Zeigers auf einer Achse ist (z.B. x > 0, y =0). Das Drehen geht per Drehmatirx recht schnell. Die dichtesten Punkte sind dann die mit positivem x und dem kleinsten Betrag für y. Die Grenze von 40 grad müßet man dann ggf. noch extra testen.

[yaro]

@loonquawl: Es genügt leider nicht, denn es ist wichtig, dass der Punkt sich in Drehrichtung befindet. Er kann nochso nah sein, wenn er nicht in Drehrichtung ist, dann ist er für mich nicht von Bedeutung.

@Besserwessi: Das wäre eine gute Idee, aber es lohnt sich nicht für die paar Punkte 2 Winkelfunktionen zu berechnen (die brauchen relativ lange). Ich kann sie auch nicht besonders viel schneller machen, denn der Winkel, unter dem ein Punkt auftauchen kann, kann von 0,0001° bis ca 40° groß sein. (das mit den 40° war ein flüchtigkeitsfehler von mir, eigentlich sind es 70°, aber das ist für die Rechnung nicht besonders wichtig).

Ich poste gleich mal meine bevorzugte Lösung (ist mir als zweites eingefallen, nachdem die erste nicht ganz so schön war)

Gruß, Yaro

[yaro]

Hier meine bevorzugte Lösung:
Bezeichnungen finden sich auf der beigefügten Zeichnung.
Beispiel in der Zeichnung ist für Drehung gegen den Uhrzeigersinn.

Ab dem Punkt F bis zum Punkt F' sind Punkte, die im annehmbaren Bereich liegen. Die Strecke r zeigt vom mittelpunkt des Kreises zum Punkt F.
Der Punkt F' entsteht durch Drehung des Punktes F um 70° mithilfe einer Drehmatrix (um einen festen Wert drehen braucht kaum Rechenzeit)
Zu dier Strecke r wird die Normale(Orthogonale) t bestimmt (eigentlich wird nur ihre Steigung bestimmt). Dann wird die Steigung der geraden durch F und F' bestimmt, diese Gerade heißt s. Außerdem wird noch die Steigung der Geraden, die durch F und den Punkt P geht bestimmt (zu jedem relevanten Punkt P[i]) diese Gerade heißt g.
Nun schaut man sich dei Steigungen der Geraden an. Damit der Punkt P im annehmbaren Bereich liegt, muss (bei Drehung gegen den Uhrzeigersinn) die Steigung von g größer sein als die von t und kleiner als die von s. Aufpassen muss man beim "Überlauf", wenn t eine positive und s eine negative Steigung hat, aber das ist kein großes Problem. Der nächste Punkt ist der, dessen Steigung am nächsten an der von t dran ist.

Gruß, Yaro

[Besserwessi]

Um die Drehung zu berechnen braucht man keine Winkelfunktionen. Das kann man gleich mit den koordinatenwerden des Startwinkels machen. Der Witz dieser Lösung besteht ja gerade darin, das man zu Laufzeit gar keine Winkelfunktion braucht. Nur eventuell einmal vorweg für die 40 Grad.

[Besserwessi]

Die Wohl kürzeste Lösung ist wohl einfach die Quadrate der Abstände zu berechenen. Der kürzeste Abstand ist auch der kleinste Winkel.

[yaro]

Der Startwinkel ist immer unterschiedlich.
Das zweite habe ich allerdings nicht wirklich verstanden... wieso Quadrate? Außerdem würde man dann ja die Drehrichtung nicht berücksichtigen.

Gruß, Yaro

[Besserwessi]

Die Quadrate der Abstände sind schneller zu berechnen, da spart man sich die Wurzel.

Das mit der Drehrichtung hatte ich übersehen. Das läßt sich aber auch realtiv leicht testen: Wenn man die Vektoren gedanklich mit einer 0 als 3 te komponente zu einem 3 D Vektor erweitert, kann man das Kreuzprodukt der Vektoren berechenen und kriegt so den Sinus des Winkels mal der Längen der Vektoren. Die Längen sollten wohl konstant sein und stören daher nicht weiter. Das könnte man auch gleich als ersten Test nutzen. Statt des Abstandes kann man auch ähnlich das skalarprodukt berechenen: je größer das ist, desto kleiner der Winkel.

Wenn man als bezeichnungen Sx,Sy für die Startposition und Px,py für die Koordinaten wählt, dann also etwa so:
A = Sx*Px+Sy*Py ( = L^2 * cos Winkel)
B = Sx*Py-Sy*Px ( = L^2 * sin Winkel)
Suche nach maximalem Wert von A mit B >0 (oder B<0 bei anderer Drehrichtung). Die Bedingung < 40 Grad kann man dann auch leicht auf A oder B zurückführen.

[SprinterSB]

edit:
@Sprinter: Habe wohl gleichzeitig mit dir geschreiben, sodass ich deinen Beitrag übersprungen habe.
Soweit ich das verstanden habe, muss ich dazu den Winkel kennen, unter dem die Punkte auftauchen, ich kenne aber nur die Koordinaten der Punkte. Um den Winkel herauszufinden müsste ich dann noch zusätzliche Rechnungen durchführen. Das ist es ja, was ich vermeiden will.

Ja, die Koordinaten würde man von kartesisch nach polar wandeln. In Polarkoordinaten ist's trivial.


Alles findet im Kartesischen Koordinatensystem statt, Koordinaten der Punkte sind bekannt. Winkel zu den Punkten sind nicht bekannt.
Ich schreibe in C

Zur Berechnung des Winkels gibt's in C die atan2-Funktion, die auch den Quadranten berücksichtigt.

Wenn du solche Funktionen nicht verwenden kannst/darfst (zB auf AVR ist das übel) dann solltest du darauf hinweisen, ansonsten ist's hier Lesen ausm Kaffeesetz.

Für den Cosinus des Winkels hast du
cos(phi) = x1*x2 + y1*y2

An nächsten an deinem Punkt liegt derjenige mit dem größten Cosinus-Wert.

Die Orientierung bekommst du mit
sin(phi) = x1*y2 - x2*y1
wobei das Vorzeichen abhängig ist von dem Rotationssinn den du gerne hättest.

Bei 4 Punkten vergibst du dir nix. Ergo: Such aus allen Punkten deren sin das richtige Vorzeichen hat, denjenigen mit dem ghrößten cos-Wert.

Pro Punkt brauchst du höchstens 4 Multiplikationen, 2 Subtraktionen und 2 Vergleiche. Es geht aber auch mit 3 Multiplikationen wenn die wesentlich teurer sein sollten als ne Strichrechnung.

[yaro]

@besserwessi:das mit den Quadraten ist mir nun auch klar =). Und das mit dem Kreuzprodukt ist eine richtig richtig gute Idee! Ich habe die Vektorrechnung hier komischerweise außer Acht gelassen, obwohl sie eigentlich perfekt zu dem Problem passt!
Mit dem Kreuzprodukt schmeiße ich alle Werte über 180° raus, und mit dem Skalarprodukt fische ich mir dann das mit dem kleinsten Winkel raus, und kann damit auch gleich den Winkel berechnen. (ist ja eigentlich das selbe wie cosinussatz)

@sprinter: Ich kann/darf alle Funktionen verwenden, um schnellstmöglich am Ziel anzukommen.
ich habe gerade geguckt, atan2 braucht ca. 2800Takte auf einem 8bit AVR, ich glaube das wird nicht der schnellste Weg sein.
Auch dir danke für die Rechnung (ist ja genau das Selbe wie bei Besserwessi), nur wäre die Rechnung leichter zu verstehen, wenn du erwähnt hättest, dass sie sich auf das kreuzprodukt und das Skalarprodukt bezieht... Hab deinen Post zuerst gelesen und erstmal ein Weilchen gebraucht, um das zu verstehen, denn cos(phi) ist nicht gleich x1*x2 + y1*y2, sondern man müsste es erst durch das Quadrat der Längen teilen, um den richtigen Wert herauszubekommen (wenn man nicht am Einheitskreis arbeitet, wovon du wahrscheinlich ausgingst).

Nochmal danke euch beiden, diese Lösung ist deutlich eleganter als die, die ich mir zurechtgebastelt hatte.

Gruß, Yaro

[SprinterSB]

Auch dir danke für die Rechnung (ist ja genau das Selbe wie bei Besserwessi), nur wäre die Rechnung leichter zu verstehen, wenn du erwähnt hättest, dass sie sich auf das kreuzprodukt und das Skalarprodukt bezieht... Hab deinen Post zuerst gelesen und erstmal ein Weilchen gebraucht, um das zu verstehen, denn cos(phi) ist nicht gleich x1*x2 + y1*y2, sondern man müsste es erst durch das Quadrat der Längen teilen, um den richtigen Wert herauszubekommen (wenn man nicht am Einheitskreis arbeitet, wovon du wahrscheinlich ausgingst).

Eine Rotation wird nicht ausgeführt.

Die Länge des Stabes oder was auch immer spielt keine Rolle; du kannst die cos- und sin-Werte einfach als mit l² skaliert betrachten.

Bei der cos-Betrachtung ist nach x0*xn+y0*yn zu sortieren -> Skaleninvariant

Bei der sin-Betrachtung ist zu testen ob x0*yn < y0*xn -> Skaleninvariant

Ob man das als Kreuz-/Skalarprodukt interpretieren ist Geschmackssache. Man kann ebenso die x-Werte als l*sin(phi) und die y-Werte als l*cos(phi) betrachten (oder umgekehrt) und die Formeln als Additionstheoreme für sin(phi-phi_n) bzw cos(phi-phi_n) ansehen.

[micky_ficky]

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]

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]

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).

[micky_ficky]

Wird das Thema hier mal beendet, das neue Fragen kommen können?

MfG
Daniel

[Manf]

Ja, ist hiermit beendet.