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