Brauche Suchbegriffe - Vergleichen von Zahlen

29.04.2015, 13:22

mabusee

Brauche Suchbegriffe - Vergleichen von Zahlen

Hallo,

ich habe ein Problem und überhaupt keine Ahnung an wen ich mich wenden könnte, also probier ich es mal bei Euch.

gegeben:

2,2,2
6,6,6
10,10,10

eingabe:

3,4,3

ausgabe:

6,6,6

Ich suche das nächst höhere Zahlenpaar.

29.04.2015, 13:57

Gast11022013

Auf diesen Beitrag antworten »

Könntest du die Aufgabenstellung vielleicht näher beschreiben?
Zumindest ich kann bisher nichts damit anfangen.

29.04.2015, 16:33

mabusee

Auf diesen Beitrag antworten »

Dabei handelt es sich um Vector Coordinaten. Ich möchte herausfinden, welche Coordinaten aus der Liste am nächsten zu der gesuchten coordinate befinden. Besser kann ich das leider nicht erklären.

edit:
gegeben:

2,2,2
6,6,6
10,10,10

eingabe:

3,4,3

ausgabe:

coordinaten die sich am nächsten zu gesuchten coordinate befindet

29.04.2015, 16:53

HAL 9000

Auf diesen Beitrag antworten »

Wenn "am nächsten" im Sinne von euklidischem Abstand gemeint ist, dann hätte die Antwort auf 3,4,3 aber 2,2,2 statt 6,6,6 lauten müssen. Ein bisschen besser musst du schon erklären was du hier meinst, mit

Zitat:

Original von mabusee
Besser kann ich das leider nicht erklären.

kommst du nicht davon.

29.04.2015, 17:02

mabusee

Auf diesen Beitrag antworten »

Deswegen habe ich das auch im 2. Post korrigiert, ich bin nicht mehr der jüngste und mache das hobbymäßig. Mir fehlen schlichtweg die Vokabeln. Aber so langsam komm ich selber drauf. Ich muss die Entfernung berechnen?

"Abstand zweier Punkte im dreidimensionalen Raum"

Bin ich da richtig?

edit: Ok, da bin ich richtig. Vielen Dank.

29.04.2015, 17:12

HAL 9000

Auf diesen Beitrag antworten »

Nun, wo ist das Problem? Mit

$\begin{align*} \sqrt{(x_1-x_2)^2+(y_1-y_2)^2+(z_1-z_2)^2} \end{align*}$

kannst du den euklidischen Abstand zweier Punkte $\begin{align*} P_1(x_1,y_1,z_1) \end{align*}$ und $\begin{align*} P_2(x_2,y_2,z_2) \end{align*}$ bestimmen. Bei $\begin{align*} n \end{align*}$ Punkten in der Liste tust du das $\begin{align*} n \end{align*}$ -mal, jeweils immer der Abstand zwischen deinem gegebenen Punkt und einem Listenpunkt. Der Listenpunkt mit dem niedrigsten der $\begin{align*} n \end{align*}$ Abstandswerte ist dann der gesuchte Punkt.

So banal würde man vorgehen, sofern die Liste noch nicht sehr lang ist bzw. diese Zuordnung auch nicht sehr oft durchgeführt werden muss.

Ist hingegen die Liste sehr lang und diese Zuordnung dann ebenfalls sehr oft durchzuführen, gibt es effizientere Techniken, als wirklich alle $\begin{align*} n \end{align*}$ Abstände zu berechnen. Augenzwinkern

29.04.2015, 17:19

mabusee

Auf diesen Beitrag antworten »

Die Liste ist nicht lang, nicht mehr als 64 Einträge. Insofern sollte die Methode reichen.

30.04.2015, 14:40

HAL 9000

Auf diesen Beitrag antworten »

Das stimmt. Meine Anmerkung bezog sich auch eher auf Größenordnungen wie $\begin{align*} 10^6 \end{align*}$ Listenpunkte und dann auch $\begin{align*} 10^6 \end{align*}$ Testpunkte: Da braucht man bei durchdachter Organisation durchaus nicht $\begin{align*} 10^6\cdot 10^6 = 10^{12} \end{align*}$ Abstandsberechnungen, sondern deutlich weniger. Augenzwinkern

30.04.2015, 15:58

mabusee

Auf diesen Beitrag antworten »

Jetzt hast Du mich neugierig gemacht. Über welche effiziente Technik sprichst Du? Nicht, dass ich sie brauchen würde aber sicher ist es "worth to know".

30.04.2015, 18:00

HAL 9000

Auf diesen Beitrag antworten »

Man unterteilt den Raumbereich, in dem sich die Listenpunkte befinden, in ein gleichmäßiges dreidimensionales Gitter "passender" Gitterweite. Jeder Listenpunkt gehört dann in ein Gitterelement, und man führt für jedes Gitterelement eine Liste der zugehörigen Punkte, die i.a. jeweils deutlich kürzer als die Gesamtliste sein sollte - eine Frage der Gitterweite.

Will man nun für einen Testpunkt den kleinsten Abstand zu einem der Listenpunkte bestimmen, so genügt es, die Listenpunkte aus demselben Gitterelement sowie der Nachbarelemente zu prüfen - nur falls sich dort gar kein Listenpunkt befindet, muss man auch noch die nächste "Schicht" an Nachbargitterelementen überprüfen usw.

Diese Methode funktioniert natürlich um so besser, wenn die Listenpunkte einigermaßen gleichverteilt über einen gewissen beschränkten Bereich des Raumes liegen. Hab ich mal so ähnlich angewandt zur Simulation von ca. 10 Millionen Scheiben (Dimension 2) bzw. Kugeln (Dimension 3) des SSI-Modells.

30.04.2015, 20:19

mabusee

Auf diesen Beitrag antworten »

Das ist sehr interessant. Diese Vokabeln habe ich gesucht.

Ich habe diese Zeichnung erstellt. Habe ich das richtig verstanden? Dann muss ich mich korrigieren, das muss ich mir näher ansehen.

[attach]37921[/attach]

01.05.2015, 18:00

HAL 9000

Auf diesen Beitrag antworten »

Ja, so in etwa. Durch den regelmäßigen Gitterabstand lässt sich aus den Koordinaten direkt die zugehörige Gitterzelle bestimmen.

Ein Beispiel: Der Einheitswürfel $\begin{align*} [0,1)^3 \end{align*}$ wird in $\begin{align*} 100^3 \end{align*}$ , also eine Million kleine Würfel der Kantenlänge 0.01 unterteilt. In welchem Teilwürfel liegt dann Punkt $\begin{align*} (x,y,z)\in [0,1)^3 \end{align*}$ ?

Antwort: In Gitterelement $\begin{align*} (n_x,n_y,n_z) \end{align*}$ mit $\begin{align*} n_x = \lfloor 100x\rfloor \end{align*}$ , $\begin{align*} n_y = \lfloor 100y\rfloor \end{align*}$ und $\begin{align*} n_z = \lfloor 100z\rfloor \end{align*}$ , also z.B. Punkt (0.3726, 0.0819, 0.9056] liegt dann in Zelle $\begin{align*} (37,8,90) \end{align*}$ , dabei können $\begin{align*} n_x,n_y,n_z \end{align*}$ Werte von 0..99 annehmen.

Neue Frage »

Antworten »

Brauche Suchbegriffe - Vergleichen von Zahlen

Verwandte Themen