Distanz von Punkt A zu Punkt B

Ich habe zwei Punkte, deren Koordinaten sind mir bekannt.
Was ich suche, ist die Distanz dieser beiden Punkte und zwar schnell.
Mir ist der Satz des Pythagoras natürlich bekannt, mein Problem ist, dass diese Operation ca 3.000.000 machen muss, und dies in 100 ms. Sicherlich klappt es nicht, aber ich brauche einen möglichst schnelleren Algorithmus, der Haken bei Euklidischen Entfernung ist ganz klar der Overhead von zwei Potenzen und eine Wurzelberechnung, wobei am Ende eh ein Int beim rumkommen muss.

Eine Alternative, die ich noch testen muss ist die "Manhattan Distance", mir geht es nicht um präzise Angaben (wie auch mit Int 😄), aber wenn ein Punkt die maximale Entfernung von 5 hat, sprich Punkt A (0,0) und Punkt B(5,5), soll die maximale Entfernung auch 5 betragen, bei der Manhattan Entfernung wäre sie jedoch 10.
Und nein, einfach halbieren klappt bei Manhattan nicht 🙂

Ich überlege auch, ob es Sinn macht, die Potenzen zu cachen, da ich ja zu beginn die maximale Entfernung weiß, kann ich diese einmal berechnen, evtl auch die Wurzeln

Hallo Seikilos,

genau, mach dir einfach eine Entfernungstabelle.

herbivore

Ja, ich denke auch, dass dies eine gute Idee, ist, wäre mir ohne den Thread hier nicht eingefallen 🙂

Vielleicht hilft der Thread ja noch jemandem mal

Hm, naja, ich krieg doch nicht die Werte die ich suche.
Hab mal ein Bild angehängt, ich brauche eigentlich die Entfernung, die Grau markiert ist, also 5 Sektoren (von mir aus auch 4).

Mal überlegen

Hallo Seikilos,

Math.Max (x2-x1, y2-y1)

herbivore

Hi!

Die Wurzel von der euklidischen Entfernung könntest Du einfach weglassen und zum Ausgleich die maximale Entfernung (5) quadrieren.

Ansonsten würde ich vorschlagen, dass du erstmal einen Ansatz implementierst und dann mit einem Profiler nachmisst, wie schnell oder langsam die Sache ist, bevor du dich auf die Optimierung stürzt, denn:
Premature optimization is the root of all evil!

In Spielen fallen auch immens viele Multiplikationen an (Matrizen-Rechnung) und die schaffen es meistens auch über 100ms pro Frame (10 FPS) zu bleiben 😉.

Mfg NeuroCoder

Werden in Spielen die Matrixmultiplikationen nicht an die Graphikhardware weitergegeben und dort von integrierten Schaltungen erledigt?

Im Moment arbeitet die vorkalkulierte Matrix super.

Nun bin ich an einem anderen Problem dran, siehe Bild.

Das schwarze Kästchen hat eine Reichweite von n, ich kenne die exakte Pixelposition des Kästchens, und auch in welchem Sektor er sich befindet.
Aber was mir gerade nicht klar ist, wie ich nun die Menge der Sektoren finde, die auf dieser Radius Linie liegen. Wenn n kleiner der Sektor größe ist, sind das die 8 umliegenden Sektoren, aber so fällt mir kein weg ein.

Hm eventuell das den Kreis umspannende Rechteck nach Sektoren einzeln absuchen.
Wobei das is nicht gut, man kann ja nicht die Sektorkoordinate checken, sondern muss quasi die Sektor umgebende Fläche prüfen.

Jemand eine bessere Idee?

Original von Seikilos
Wenn n kleiner der Sektor größe ist, sind das die 8 umliegenden Sektoren, ...

Nicht unbedingt: Wenn nämlich der Kreis-Mittelpunkt ziemlich weiter links unten in einem Quadrat ist, dann können es auch weniger sein (z.B. für n = 0.75*Sektorgröße).

Eine Lösung hab ich zwar leider nicht, aber vl. hilft dir ja folgende Überlegung weiter:

• Wenn n zwischen e1 (Strecke zwischen Kreismittelpunkt und Eckpunkt der am wenigsten weiter vom Kreismittelpunkt entfernt ist) und e1 (Strecke zwischen Kreismittelpunkt und Eckpunkt der am weitesten vom Kreismittelpunkt entfernt ist) ist, dann ist der Kreis im Sektor, ansonsten nicht
• Optimierung: z.B. Im linken-oberen-Viertel ist der linke-obere-Eckpunkt am weitstens entfernt (e2), der rechte-untere am wenigsten weit (e1) -> analog für die 3 anderen Kreis-Viertel
• Du brauchst nicht alle Segmente innerhalb es "umgeschriebenen Rechtsecks" prüfen: es reicht wenn du dir das 1. Segment mit Kreis irgendwie ausrechnest (z.B. suchst du dir den, der in der gleichen Reihe, aber rechts vom Mittelpunkt ist [kann man noch weiter optimieren, wenn du 'n' in die Berechnung miteinbeziehst]). Wenn du eines hast, brauchst du immer nur die links, rechts, oben und unteren Segmente prüfen. Wenn eines davon ebenfalls ein Kreis-Segment beinhaltet, prüfst du wieder links,rechts, unten und oben => Rekursion.

Kleines Bsp. zum besseren Verständis:

Vom Kreis-Mittelpunkt einfach bei der X-Koordinate 'n' dazuaddieren -> Somit weisst du, in welchem Segment mit sicherheit ein Kreis-Teil liegt (dazu brauchst du die Modulo-Operation). [Segment 16]

Jetzt prüfst du das linke Segment [15]mittels oberen beschriebenen Verfahren -> Keine Segmetn mit Kreis-Teil
Das rechte Segment [17] ist ebenfalls kein gesuchtes Segment
Das obere [10] ist eines. Also prüfst du ab dort weiter:

links [9] ist eines -> von dort aus weiterprüfen ...
rechts [11] ist keines
oben [3] st eines -> von dort ebenfalls weiterprüfen ...
unten [16]: ist bereits bekannt, dass es ein gesuchtes Segment ist -> dort nicht mehr weiterprüfen

usw.

mfg