AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Programmierung allgemein Programmieren allgemein Abstandsberechung in einem offenen Netz

Abstandsberechung in einem offenen Netz

Ein Thema von Flips · begonnen am 25. Feb 2009 · letzter Beitrag vom 26. Feb 2009
Antwort Antwort
Flips

Registriert seit: 17. Feb 2005
Ort: Sankt Wendel
491 Beiträge
 
Delphi 7 Professional
 
#1

Abstandsberechung in einem offenen Netz

  Alt 25. Feb 2009, 18:25
Hi,
nehmen wir an ich habe ein 2D-Netz in folgender Form, 8 * 8 Knoten:
Code:
o o o o o o o o
o o o o o o o o
o o o o o o o o
o x o o o o y o
o o o o o o o o
o o o o o o o o
o o o o o o o o
o o o o o o o o
Die Knoten sind horizontal und vertikal miteinander verbunden.
Dieses Netz soll offen sein, d.h. die Knoten links außen sind mit den Knoten rechts außen verbunden, ebenso die Knoten oben mit den Knoten unten.

In einem offenen Netz wäre der Abstand von X und Y -> 5
In einem geschlossenen Netz wäre er 3.

Wenn ich das Netz nun als 2D-Array programmiere und den Abstand via Pythagoras berechne, dann ist das in einem geschlossenen Netz ja ziemlich einfach.
Aber wie mache ich das in einem offenen Netz? Ich komme einfach nicht drauf.

Danke,
lg Flips
Philipp F.

Geändert von mkinzler (11. Aug 2010 um 09:18 Uhr) Grund: Auf Wunsch von TE korrigiert
  Mit Zitat antworten Zitat
Benutzerbild von jfheins
jfheins

Registriert seit: 10. Jun 2004
Ort: Garching (TUM)
4.579 Beiträge
 
#2

Re: Abstandsberechung in einem offenen Netz

  Alt 25. Feb 2009, 18:33
Hmmm ...

ich würd es wohl so machen, dass ich das manuell prüfe. Ich bezweifele dass es da eine Möglichkeit gibt die wesentlich schneller ist ...

Delphi-Quellcode:
function Distance(A, B: TPoint) : Single;
var
  dx, dy: Cardinal;
const
  Meshsize = 8;
begin
  dx = Abs(A.X - B.X);
  dy = Abs(A.Y - B.Y);

  dx = ifthen(dx > (Meshsize / 2), Meshsize - dx, dx);
  dy = ifthen(dy > (Meshsize / 2), Meshsize - dy, dy);

  Result := Phythagoras(dx, dy);
end;
So in etwa
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu

Registriert seit: 11. Okt 2003
Ort: Elbflorenz
39.439 Beiträge
 
Delphi 11 Alexandria
 
#3

Re: Abstandsberechung in einem offenen Netz

  Alt 25. Feb 2009, 18:36
Delphi-Quellcode:
inner := ABS(X - Y) + 1;
outer := (8 - Y + X) mod 8 - 1;

abstand := Min(inner, outer)
x und y = mit 0 bassiertem Index (also 0..7)

ds wäre jetzt der Abstand in einer Richtung (hoff ich mal)
und wenn du so jeweils den Abstand in X- und Y-Richtung so ausrechnest und dieser verrechnest, dann sollte sich der absolute Abstand bestimmen lassen
Garbage Collector ... Delphianer erzeugen keinen Müll, also brauchen sie auch keinen Müllsucher.
Delphi-Tage 2005-2014
  Mit Zitat antworten Zitat
Benutzerbild von Sir Rufo
Sir Rufo

Registriert seit: 5. Jan 2005
Ort: Stadthagen
9.454 Beiträge
 
Delphi 10 Seattle Enterprise
 
#4

Re: Abstandsberechung in einem offenen Netz

  Alt 25. Feb 2009, 21:04
Wie wäre es mit Horizonterweiterung?
Code:
. . . . . . . .|. . . . . . . .|. . . . . . . .
. . . . . . . .|. . . . . . . .|. . . . . . . .
. . . . . . . .|. . . . . . . .|. . . . . . . .
. . . . . . . .|. . . . . . . .|. . . . . . . .
. . . . . . . .|. . . . . . . .|. . . . . . . .
. . . . . . . .|. . . . . . . .|. . . . . . . .
. . . . . . Y .|. . . . . . Y .|. . . . . . y .
. . . . . . . .|. . . . . . . .|. . . . . . . .
---------------+-------+-------+---------------
. . . . . . . .|o o o o|o o o o|. . . . . . . .
. . . . . . . .|o o o o|o o o o|. . . . . . . .
. . . . . . . .|o o o o|o o o o|. . . . . . . .
. . . . . . . .|o X o o|o o o o|. . . . . . . .
. . . . . . . .|o o o o|o o o o|. . . . . . . .
. . . . . . . .|o o o o|o o o o|. . . . . . . .
. . . . . . Y .|o o o o|o o Y o|. . . . . . y .
. . . . . . . .|o o o o|o o o o|. . . . . . . .
---------------+-------+-------+---------------
. . . . . . . .|. . . . . . . .|. . . . . . . .
. . . . . . . .|. . . . . . . .|. . . . . . . .
. . . . . . . .|. . . . . . . .|. . . . . . . .
. . . . . . . .|. . . . . . . .|. . . . . . . .
. . . . . . . .|. . . . . . . .|. . . . . . . .
. . . . . . . .|. . . . . . . .|. . . . . . . .
. . . . . . y .|. . . . . . y .|. . . . . . y .
. . . . . . . .|. . . . . . . .|. . . . . . . .
Code:
+-------+-------+-------+
|       |       |       |
|   A  |   B  |   C  |
|       |       |       |
+-------+---+---+-------+
|       | 1 | 2 |       |
|   D  +---E---+   F  |
|       | 3 | 4 |       |
+-------+---+---+-------+
|       |       |       |
|   G  |   H  |   I  |
|       |       |       |
+-------+-------+-------+
Zur Betrachtung benötigst du nur die Quadranten, die der Lage von X im Quadrant E am nächsten sind.
X in 1 => A,B,D,E
X in 2 => B,C,E,F
usw.
Berechne nun alle möglichen Strecken zwischen XY und nimm das Minimum.

cu

Oliver
Kaum macht man's richtig - schon funktioniert's
Zertifikat: Sir Rufo (Fingerprint: ‎ea 0a 4c 14 0d b6 3a a4 c1 c5 b9 dc 90 9d f0 e9 de 13 da 60)
  Mit Zitat antworten Zitat
Cyf

Registriert seit: 30. Mai 2008
407 Beiträge
 
Lazarus
 
#5

Re: Abstandsberechung in einem offenen Netz

  Alt 25. Feb 2009, 21:09
Wie wärs mit rekursiven Backtracking, bis die kürzeste Strecke gefunden ist.
Man kann einen Barbier definieren als einen, der alle diejenigen rasiert, und nur diejenigen, die sich nicht selbst rasieren.
Rasiert sich der Barbier?
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu

Registriert seit: 11. Okt 2003
Ort: Elbflorenz
39.439 Beiträge
 
Delphi 11 Alexandria
 
#6

Re: Abstandsberechung in einem offenen Netz

  Alt 25. Feb 2009, 21:16
@Sir Rufo: im Prinzip wird sowas bei meiner Rechnung schon teilweise gemacht (nach rects um einen Quadranten erweitert.)

Code:
0123456789
  X  Y

(Y - X) = innerL
(6 - 2) = 4
[3-4-5-6 > 4]

10 - (Y - X) = outerL
10 - (6 - 2) = 6
[7-8-9-0-1-2 > 6]
ansonsten ist ja Länge des Quadranten = innerL + outerL

[add]
@Cyf: 'ne manuell vorberechnte Tabelle, mit allen lösungen wäre das schnellste ... muß man sich dann nur noch schnell die richtige Lösung raussuchen (über 'nen 2-dimensionales Array recht leicht)
Garbage Collector ... Delphianer erzeugen keinen Müll, also brauchen sie auch keinen Müllsucher.
Delphi-Tage 2005-2014
  Mit Zitat antworten Zitat
Benutzerbild von inherited
inherited

Registriert seit: 19. Dez 2005
Ort: Rosdorf
2.022 Beiträge
 
Turbo Delphi für Win32
 
#7

Re: Abstandsberechung in einem offenen Netz

  Alt 25. Feb 2009, 21:18
@Cyf: Das nennst du dann Bogotrace und deiner Signatur gerecht
Nikolai Wyderka

SWIM SWIM HUNGRY!
Neuer Blog: hier!
  Mit Zitat antworten Zitat
Benutzerbild von sx2008
sx2008

Registriert seit: 15. Feb 2008
Ort: Baden-Württemberg
2.332 Beiträge
 
Delphi 2007 Professional
 
#8

Re: Abstandsberechung in einem offenen Netz

  Alt 26. Feb 2009, 03:08
Zitat von Flips:
... und den Abstand via Pythagoras berechne
Ich glaube nicht, dass das in deinem Fall die richtige Rechenmethode ist.
Code:
o o o o o o o o
o o o o o o o o
o o o x o o o o
o o o o o o y o
o o o o o o o o
o o o o o o o o
o o o o o o o o
o o o o o o o o
Wie gross ist hier der "Abstand" von x nach y?
Ein Kästchen nach Süden und drei nach Osten macht 4.
Die Reihenfolge der Züge ist egal, es sind immer mindestens 4 Züge notwendig.

Oder wenn eine diagonale Bewegung erlaubt ist:
Diagonal nach Süd-Ost plus zwei nach Osten macht 3.
  Mit Zitat antworten Zitat
Flips

Registriert seit: 17. Feb 2005
Ort: Sankt Wendel
491 Beiträge
 
Delphi 7 Professional
 
#9

Re: Abstandsberechung in einem offenen Netz

  Alt 26. Feb 2009, 21:42
Hey wow, hab das Thema kurz außer acht gelassen und schon soviele Vorschläge^^ Danke euch
Hab jetzt die Variante von jfheins genommen, geht wunderbar

Und nochwas zu sx2008 Beitrag:
Ähm doch doch, die Entfernung soll nicht in Einheiten bezüglich des Netzes berechnet werden, sondern als wäre das Netz in ein Koordinatensystem eingebettet. Sodass zwischen zwei Punkten horizontal und vertikal der dimensionslose Abstand "1" ist, und somit diagonal der Abstand Wurzel 2.
Philipp F.
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 16:08 Uhr.
Powered by vBulletin® Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2021 by Daniel R. Wolf