kleine Geometrieaufgabe. Schlaue Lösung gesucht.

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