Streckenlänge ohne Wurzel berechnen

Hallo,

Kurze Frage:

Wenn man eine Strecke hat, die von (x1, y1) nach (x2, y2) geht, ist jemandem von euch eine simple Näherungsberechnung der Länge dieser Strecke bekannt?

Die exakte Länge ist ja Wurzel_aus(x2-x1^2 + y2-y1^2) (jaja, die Klammern). Ich würde aber gerne die Wurzel vermeiden.

Manhattandistanz dagegen ist mit einem Fehler von bis zu 1,4 doch wieder etwas zu grob.

Gibt es vielleicht etwas dazwischen, das mit den Grundrechenarten funktioniert und ein bißchen genauer ist? Ich habe schon gesucht, aber nichts gefunden...

Z.

@zaeld

Wieso muss es ohne Wurzel gehen?

@zaeld
Das Heron-Verfahren ist ein Rechenverfahren zur Berechnung einer Näherung der Quadratwurzel x einer Zahl a>0.
Wikipedia: Heron-Verfahren
http://wikis.zum.de/qed/Heron-Verfahren

@zaeld
Darf ich fragen welcher Mathematikkurs das ist? Ist das noch Abi oder schon Studium?

So wie ich das verstehe fällt mir da nur ein auf einem Graphen die Punkte als diagonale Eckpunkte eines Quadrates zu sehen und die Seitenlänge von selbigem durch die 3 Potenz zu teilen. So bekommst du auch einen Näherungswert. Da man das Feld ja auch mit Quadraten füllen kann und deine Strecke eine Konstante Steigung aufweist (x1 y2 - x2 y3 - x3 y3 usw) teilt sie ja genau ein Graphenquadrat in 2 gleichschenkelige Dreiecke, da müsste doch mit nem Pytagoras was zu machen sein? Wo bei man dabei ja quadriert und und mir grade nicht einfällt wie mein beim Umformen die Wurzel umgeht...
Bei mir ist das schon bisschen her, aber gibts nicht auch noch die Möglichkeit mit nem Zirkel da was zu machen? Tangenz und so?

Viel glück beim lösen!

@Rho-ny-theta

Rho-ny-theta schrieb:Wieso muss es ohne Wurzel gehen?

@kammerjäger

kammerjäger schrieb:Darf ich fragen welcher Mathematikkurs das ist? Ist das noch Abi oder schon Studium?

Keine Übungsaufgabe, aus dem wirklichen Leben :-)

Ich muß (bzw. möchte) mit dem Rechner einen Pfeil malen. Der besteht aus drei Teilen: Der eigentliche Strich und an einem Ende kommen im 45°-Winkel die beiden Striche für die Pfeilspitze dran. Start- und Zielpunkt des langen Strichs bekomme ich, aber die beiden Endkoordinaten für die Spitzenstriche muß ich selber daraus herleiten. Die kann man aus der Grundlinie herleiten, aber da die immer gleich lang sein sollen (egal wie lang die Grundlinie ist), muß ich kurz gesagt durch die Länge der Grundlinie teilen.

Da das ganze in einer Zeichenroutine stattfindet (nach jeder Mausbewegung muß neu gemalt werden) und dabei potentiell sehr viel gezeichnet werden muß, will ich aufwendige Berechnungen, z.B. irgendwelche Schleifen für Näherungsverfahren oder Koordinatensystemtransformationen (Drehen) vermeiden.

Wenn ich die Manhattandistanz verwende, geht es zwar prinzipiell, aber die Größe der Pfeilspitze ändert sich doch deutlich.

kammerjäger schrieb:So wie ich das verstehe fällt mir da nur ein auf einem Graphen die Punkte als diagonale Eckpunkte eines Quadrates zu sehen und die Seitenlänge von selbigem durch die 3 Potenz zu teilen.

Ich kann das Verfahren leider nicht so recht nachvollziehen. Wo kommt da eine dritte Potenz her? Und wenn die Linie nicht genau diagonal ansteigt?

Z.

@zaeld
Hmm, das ist schwierig hier ohne Stift und Zettel zu erklären....

Ich gehe aber davon aus die Pfeilspitzen sollen im 45° Winkel zum Pfeil stehen. An der Stelle wo sie beginnen sollen sich nen Quadrat denken. Der "Pfeil" teilt dieses Quadrat in 2 Dreiecke. Dann mit dem Pytagoras die Kathete berechnen und die halbe Strecke ist der Startpunkt von deier Spitze! Anders kann ich das ohne was auf nen Zettel zu malen nicht erklären :D

@kammerjäger

kammerjäger schrieb:Hmm, das ist schwierig hier ohne Stift und Zettel zu erklären....

Jo, verstehe ich.

kammerjäger schrieb:Dann mit dem Pytagoras die Kathete berechnen

Dafür brauche ich aber wieder die Wurzel.

Na ich habe hier möglicherweise noch einen anderen Ansatz, ich setze mich gleich nochmal an den Tisch und konstruiere ein bißchen...

Z.

Benutz die Wurzel und probier erstmal aus, ob das ueberhaupt zu langsam ist. Heutzutage sollte eine Wurzel eigentlich schon umsonst sein. 'premature optimization' und so.

Als wir noch in Hoehlen lebten hat man Tabellen vorberechnet oder eine schicke approximation von 1/sqrt(x) berechnet (Wikipedia: Fast inverse square root#Overview of the code, sehr coole Erklaerung hier http://h14s.p5r.org/2012/09/0x5f3759df.html). Aber vermutlich nicht so wichtig weil Berechnungen heute nichtmehr das groesste Bottleneck darstellen.

Ich weiß nicht wirklich was einfacher zu berechnen ist. Aber würde es nicht mit Winkelfunktionen funktionieren. Die könnte man taylor entwickeln und der Fehler wäre nicht zu groß, da man mit Reduktionsformeln die Winkel ja in den Bereich -Pi/4 bis Pi/4 drücken kann.

@McNeal

McNeal schrieb:Benutz die Wurzel und probier erstmal aus, ob das ueberhaupt zu langsam ist. Heutzutage sollte eine Wurzel eigentlich schon umsonst sein. 'premature optimization' und so.

Hm, das wäre dann die einzige Stelle, wo ich dann eine Mathe-Library verwenden müßte, und die arbeitet dann wohl auch noch mit Floating-Point-Zahlen, sodaß dann noch eine Konvertierung dahin und wieder zurück fällig wird. Auch nicht so schön.

Eine Idee habe ich noch: Bei der Manhattandistanz ist der Fehler mit 1,4 am größten, wenn die Linie genau diagonal verläuft. Ich könnte einfach linear berechnen, wie diagonal die Linie liegt und die Größe entsprechend der Diagonalität von 1 bis 1,4 skalieren.

Danke erstmal für die Hinweise.

Z.

@zaeld

Was für ein Programm benutzt du denn und wozu soll das alles gut sein?

@zaeld

Konvertierung in float und zurueck sollte nun wirklich auch kein Problem darstellen. Welche Programmiersprache verwendest du denn? Und warum probierst du nicht einfach aus ob es tatsaechlich so langsam ist, dass man einen Grund hat um zu optimieren.

Ich glaube du unterschätzt die Rechenleistung.

Ich bin auch immer auf Perfomance aus, aber die Länge von etwas bei jeder Koordinatenänderung der Maus zu berechnen ist nichts.

Mess mal die Millisekunden mit und ohne Wurzel.

@zaeld
Diese rationalen Näherungsformeln für den arctan(x)
Wikipedia: Arkustangens und Arkuskotangens#cite ref-3

haben doch einen sehr kleinen Fehler. Wenn du damit Winkel berechnest also arctan(y/x), dann eine Näherungsformel für den Sinus zB. x-x³/6 benutzt sollte es doch besser sein als Manhatten Metrik. Also insgesamt

Länge = y/sin(arctan(y/x))

Keine Ahnung, hab jetzt nicht abgeschätzt wie groß der Fehler insgesamt ist ( x-x³/6 hat eine relative Abweichung von unter 0,5% auf -Pi/4 bis Pi/4).

Aber wie gesagt hab nicht wirklich viel Ahnung davon, was beim Programmieren Sinn macht.

Ich kenne mich mit dem Thema ziemlich gut aus (ich habe u.a. mal eine komplette Floatingpoint-Bibliothek in Assembler implementiert). Ohne allzu weit auszuholen: Sofern Du wirklich die Floatingpoint-Quadratwurzel vermeiden willst (was möglicherweise trotz des Overheads die effizienteste Variante sein könnte), dürfte eine Lookup-Table mit einer anschliessenden festen Zahl (u.U. genügen sehr wenige) von Newton-Iterationen das schnellste Verfahren für eine Näherungslösung sein. Es gibt auch einen Shift-and-Add-Algorithmus, der sogar ohne Division auskommt (auf den sich im Endeffekt alle Quadratwurzel-Algorithmen -- auch die mit Division -- zurückführen lassen), aber der ist bei vorhandener Hardware-Division meist langsamer als Newton-basierte Verfahren. Bei Interesse kann ich das näher erläutern.

Möglicherweise reicht Dir dieses Verfahren: http://netstorage.iar.com/SuppDB/Public/SUPPORT/000419/AN-G-002.pdf . Das ist in gewisser Weise eine Extremform des von mir o.g. Verfahrens: Statt mit einer Lookup-Table wird mit einem festen Anfangswert und 3 Iterationen gerechnet. Mit einer Lookup-Table geht's bei Bedarf genauer und/oder schneller.

@uatu

uatu schrieb:Möglicherweise reicht Dir dieses Verfahren: http://netstorage.iar.com/SuppDB/Public/SUPPORT/000419/AN-G-002.pdf .

Super, genau so etwas habe ich gesucht! (Ganz genau sollte ja eigentlich keine Iteration drin sein, aber egal, reicht völlig aus.)

@Rho-ny-theta
@McNeal

McNeal schrieb:Welche Programmiersprache verwendest du denn? Und warum probierst du nicht einfach aus ob es tatsaechlich so langsam ist, dass man einen Grund hat um zu optimieren.

Ist C++ mit Qt, und es geht um das Malen eines Widgets, in dem recht viele Objekte vorkommen können. Derzeit habe ich aber nicht so viele Objekte, daß ich das sinnvoll messen könnte, und die nur für die Messung künstlich zu erzeugen, ist mir gerade zu aufwendig.

Da gäbe es dann zwar noch andere Beschleunigungsmethoden, aber wie gesagt will ich nicht für eine einzige Stelle im Programm eine Mathe-Lib verwenden...

Danke für die Tips!

Z.

@zaeld

Generell wuerd ich dir empfehlen zuerst mal einen funktionierenden Prototypen zusammenzubauen und dann zu schauen, ob das zum Problem wird. Ich hab schon soviele Optimierungen gebaut, die alle voellig nutzlos waren und kann wirklich nur deutlichst davon abraten zu frueh zu optimieren.

Die heutigen CPUs crunchen dir die numerischen Teile so schnell weg, dass es nicht mehr offensichtlich ist, wo die Bottlenecks sind. Im Zweifel schluckt der DLL call zum Linien zeichnen mehr als die gesamte Rechenarbeit oder das ganze ist Cache/Memory limitiert, z.B. wird die Rasterisierung einer Linie soviele cache misses produzieren, dass man da locker ein paar sqrts verstecken kann. Optimierung auf dieser Ebene ist heute nicht mehr so einfach wie frueher.

zaeld schrieb:Da gäbe es dann zwar noch andere Beschleunigungsmethoden, aber wie gesagt will ich nicht für eine einzige Stelle im Programm eine Mathe-Lib verwenden...

Gibts dafuer auch einen Grund? Ich sehe jetzt keinen Vorteil das #include<cmath> wegzulassen, zumal die schon sehr fundamental ist.

Man kann auch die Wurzel mit einem Algorithmus annäherungsweise lösen.
Wikipedia: Heron-Verfahren

@Foss: Ich hab' ja Verständnis dafür, wenn jemand z.B. nicht alle 8900 Beiträge im Auftriebskraftwerk-Thread liest, bevor er irgendwas postet, aber solange alle Beiträge noch auf eine Seite passen, wie hier, ist es schon eine ganz gute Idee, die vorhergehenden Beiträge zu lesen. ;)