Dijkstra mittels Image Darstellen und Ecken + Kanten verknüpfen

[Nathaniel]

Hallo!

ich bin gerade dabei ein kleines Programm zu schreiben womit ich schon relativ weit fortgeschritten bin (anbei Screenshot), allerdings fällt mir jetzt erst auf, dass ich an einer Sache nicht gedacht habe und jetzt damit Probleme habe...

Das Problem liegt viel weniger darin den Algorithmus zu implementieren (da ich noch gar nicht an der Stelle bin) sondern, dass ich das ganze graphisch darstellen möchte.

ZIEL:

Ich möchte nur dann eine Kante hinzufügen, wenn der erste Klick (setzt die MoveTo Koordinate in den Knoten) IN dem Knoten erfolgt. Sonst passiert nichts. Nunja, daraus folgt ja, dass irgendwo alle Koordinaten der Knoten gespeichert werden müssen

--> Deswegen habe ich mir ein dynamisches Array gebaut mit 4 Komponenten (x1, x2, y1, y2). Nun bin ich dabei gewesen mir eine Funktion zu schreiben, welche prüft ob die neuen Koordinaten (von MouseDown {x,y} , also von der neuen Kante) innerhalb von den Koordinaten liegen, die im Array gespeichert sind.

Und hier ist das Problem. Ich habe ja mehrere Knoten im Array gespeichert und somit auch mehrere Koordinaten. Gibt es eine geschickte Methode im Array diese Koordinaten zu suchen die am nächsten den Koordinaten der Ecke zusammenpassen?

Ich hoffe ich hab mein Problem einigermaßen verständlich geschildert, bei Fragen sonst fragt!

Danke!

[Furtbichler]

1. Hat Dijkstra nur einen Algorithmus entwickelt?
2. Du verwendest wohl eine geklautes Windows 7.

[himitsu]

Dijkstra ... Algorithmus ... Ich denk du suchst was für die Koordinatensuche/-Koordinatenverwaltung und nicht für den Algo? :gruebel:

Nein, da gibt's im Delphi natürlich nichts fertiges, für sowas spezielles.

Aber du wirst doch wohl selber dein Array / deine Liste durchsuchen können, dir jeweils die Entfernung ausrechnen und dir dabei das Nächste merken können?

[Nathaniel]

Zitat:

Zitat von Furtbichler (Beitrag 1175602)

1. Hat Dijkstra nur einen Algorithmus entwickelt?
2. Du verwendest wohl eine geklautes Windows 7.

1. Nein (war das die Frage?)
2. Nein, ich verwende Parallels und habe eine lizenzisierte Studentenversion von der Uni aus kostenlos bekommen, allerdings noch nicht aktiviert.
3. Was bringt mir jetzt dein Beitrag in Bezug auf das Problem?

Zitat:

Dijkstra ... Algorithmus ... Ich denk du suchst was für die Koordinatensuche/-Koordinatenverwaltung und nicht für den Algo?

Richtig, es geht viel mehr darum, deswegen habe ich den Topic Name noch mit dem Vermerk beschrieben und den Hinweis gegeben:

Zitat:

Das Problem liegt viel weniger darin den Algorithmus zu implementieren (da ich noch gar nicht an der Stelle bin) sondern, dass ich das ganze graphisch darstellen möchte.

Zitat:

Aber du wirst doch wohl selber dein Array / deine Liste durchsuchen können, dir jeweils die Entfernung ausrechnen und dir dabei das Nächste merken können?

Ja das hatte ich vor gehabt, allerdings gestaltet sich das etwas schwierig, denn : Ein Kreis besteht ja aus einer Fläche, die von vier Koordinaten aufgespannt ist (x1,y1, x2, y2) . Wir kennen jetzt nur die vier Koordinaten von dem Kreis (die ja in meinem dyn. Array gespeichert sind) und die ZWEI neuen Koordinaten die ausgehend von der Kante kommen per Mouse Klick.

Jetzt hatte ich mir eine Funktion schreiben wollen, ob die neuen Koordinaten IN einem Kreis liegen. Also müssen doch:

1. x_neu, y_neu <= x2_alt, y2_alt
2. x_neu, y_neu >= x2_alt, y2_alt

sein oder habe ich einen Denkfehler?

[jfheins]

Das kommt jetzt drauf an, wie du deine Knoten gespeichert hast.

Wenn du sie als Mittelpunktskoordinaten und Radius speicherst, kannst du ja einfach den Abstand des Klicks zum Mittelpunkt errechnen und mit dem Radius vergleichen.
Hast du Sie als 4 Koordinaten gepeichert (x1,y1, x2, y2) musst du dir erst den Mittelpunkt und den Radious ausrechnen.
Btw.: Mit den vier Koordinaten speicherst du eine allg. Ellipse. Falls alle Knoten Kreise sind, ist das ein bisschen unschön...

Ach übrigens kannst du ja eine Klasse für die Knoten machen und eine für die Kanten. Und dann jeder Klasse Koordinaten spendieren und eine Zeichenmethode. Und vll. auch eine Hittest-Methode oder so.

[himitsu]

Zitat:

Zitat von Nathaniel (Beitrag 1175624)

Jetzt hatte ich mir eine Funktion schreiben wollen, ob die neuen Koordinaten IN einem Kreis liegen. Also müssen doch:

1. x_neu, y_neu <= x2_alt, y2_alt
2. x_neu, y_neu >= x2_alt, y2_alt

sein oder habe ich einen Denkfehler?

Fast.

Es gibt ja gewisse Kreisfunktionen, womit man aus X und Y den Radius/Abstand berechnet ... und du willst ja die Abstände vergleichen.

Hier (

Delphi-Quellcode:

x_neu, y_neu  <= x2_alt, y2_alt

) wird ja der Compiler meckern, denn wie soll er das vergleichen?
Aber wenn du nur je einen Abstandswert hast (

Delphi-Quellcode:

abstand_neu  <= abstand_alt

), dann würde es gehn.

Wobei jfheins auch ein paar schöne Ansätze genannt hat.

[Nathaniel]

Ertsmal danke für euere Antworten! :thumb:

Zitat:

Hier (x_neu, y_neu <= x2_alt, y2_alt ) wird ja der Compiler meckern, denn wie soll er das vergleichen?

Das war nur als Pseudo Code gemeint, intern würde ich natürlich jede Koordinate einzeln vergleichen also:

Delphi-Quellcode:

checkIfConnected(x:integer; y: integer):boolean;
begin 

for i:= 0 to xxx( Anzahl der Kreise) do 
  begin
    checkIfConnected:= (x >= Coordinates[i].x1_coor) AND (y >= Coordinates[i].y1_coor) AND (x<= Coordinates[i].x2_coor) AND (y<=    Coordinates[i].y2_coor)
// Coordinates[i] ist mein dynamisches Array für die Koordinaten
  end;
end;

Mit sowas in der Art würde ich in Kauf nehmen, dass der Benutzer nicht ganz genau im Kreis klicken muss um die Funktion auf True zu setzen, allerdings wäre das meine, zugegebener Maßen nicht schönste Idee. :|

Zitat:

Es gibt ja gewisse Kreisfunktionen, womit man aus X und Y den Radius/Abstand berechnet ... und du willst ja die Abstände vergleichen.

Ich möchte eigentlich nur prüfen ob die neuen Koordinaten in einem Kreis liegen.

Zitat:

Wenn du sie als Mittelpunktskoordinaten und Radius speicherst, kannst du ja einfach den Abstand des Klicks zum Mittelpunkt errechnen und mit dem Radius vergleichen.

Das ist eine schöne Idee! Den Radius habe ich als Konstante gespeichert , bei der Ellipsenzeichnung habe ich folgende Prozedur:

Delphi-Quellcode:

CCircle=25;
Image.Canvas.Ellipse(x-CCircle,y-CCircle,x+CCircle,y+CCircle);

Delphi-Quellcode:

Btw.: Mit den vier Koordinaten speicherst du eine allg. Ellipse. Falls alle Knoten Kreise sind, ist das ein bisschen unschön...

Ich kenn leider keine andere Methode einen Kreis in einem Image zu zeichnen :( Gibt es da eine Kreisfunktion?

Zitat:

Ach übrigens kannst du ja eine Klasse für die Knoten machen und eine für die Kanten. Und dann jeder Klasse Koordinaten spendieren und eine Zeichenmethode. Und vll. auch eine Hittest-Methode oder so.

Da ich noch keine Erfahrung mit Klassen hatte und diese erst demnächst in der Vorlesung behandelt werden, werde ich wohl die Methode mit dem Radius und dem Mittelpunkt probieren.

EDIT:

Es funktioniert jetzt, danke für die Mithilfe. Hier der Code:

Delphi-Quellcode:

function checkIfConnected(x,y:integer):boolean;
begin
  index:=0;
  while (index<array_length) and (Result=false) do
  begin
    Result:= (x >= Coordinates[index].x1_coor) AND
      (y >= Coordinates[index].y1_coor) AND (x<= Coordinates[index].x2_coor)
      AND (y<= Coordinates[index].y2_coor);
    inc(index);
  end;
end;

[Furtbichler]

Zitat:

Zitat von Nathaniel (Beitrag 1175624)

Was bringt mir jetzt dein Beitrag in Bezug auf das Problem

Das Du zumindest die Frage präziser formulierst.
Und, das Du dein Windows mal registrieren könntest.

[himitsu]

Zitat:

Delphi-Quellcode:

function checkIfConnected(x,y:integer):boolean;
begin
  index:=0;
  while (index<array_length) and (Result=false) do
  begin
    Result:= (x >= Coordinates[index].x1_coor) AND
      (y >= Coordinates[index].y1_coor) AND (x<= Coordinates[index].x2_coor)
      AND (y<= Coordinates[index].y2_coor);
    inc(index);
  end;
end;

Wo ist index deklariert? (sag aber bitte nicht "global" oder sowas)

Und du mußt Result auch noch initialisieren, denn so ist er quasi zu Anfang mit einem Zufallswert belegt.

Delphi-Quellcode:

function checkIfConnected(x,y:integer):boolean;
var
  index: Integer;
begin
  Result:=False;
  index:=0;
  while (index<array_length) and (Result=false) do
  begin
    Result:= (x >= Coordinates[index].x1_coor) AND
      (y >= Coordinates[index].y1_coor) AND (x<= Coordinates[index].x2_coor)
      AND (y<= Coordinates[index].y2_coor);
    inc(index);
  end;
end;

Delphi-Quellcode:

function checkIfConnected(x,y:integer):boolean;
var
  index: Integer;
begin
  Result:=False;
  for index := 0 to array_length - 1 do
  begin
    if (x >= Coordinates[index].x1_coor) AND (y >= Coordinates[index].y1_coor) 
      AND (x<= Coordinates[index].x2_coor) AND (y<= Coordinates[index].y2_coor) then
    begin 
      Result := True;
      Break;
    end;
  end;
end;

oder gleich ein paar neuere Features nutzen, also wenn du die Koordinaten auch gleich/zusätzlich als

Delphi-Quellcode:

coor: TRect

anbietest.

Delphi-Quellcode:

function checkIfConnected(x, y: Integer): Boolean;
var
  i: Integer;
begin
  for i := array_length - 1 downto 0 do
    if Coordinates[i].coor.Contains(Point(x, y)) then
      Exit(True);
  Result := False;
end;

function checkIfConnected(p: TPoint): Boolean;
var
  i: Integer;
begin
  for i := array_length - 1 downto 0 do
    if Coordinates[i].coor.Contains(p) then
      Exit(True);
  Result := False;
end;

prozedual (alt) / oop-iger (neu): :
PtInRect / TRect.Contains
PtInCircle

Nja, und daß "Listen" auch einige Vorteile haben, gegenüber "einfachen" Arrays, braucht man ja nicht mehr zu erwähnen.

[Sir Rufo]

Zitat:

Zitat von Nathaniel (Beitrag 1175645)

Zitat:

Es gibt ja gewisse Kreisfunktionen, womit man aus X und Y den Radius/Abstand berechnet ... und du willst ja die Abstände vergleichen.

Ich möchte eigentlich nur prüfen ob die neuen Koordinaten in einem Kreis liegen.

Zitat:

Wenn du sie als Mittelpunktskoordinaten und Radius speicherst, kannst du ja einfach den Abstand des Klicks zum Mittelpunkt errechnen und mit dem Radius vergleichen.

Das ist eine schöne Idee! Den Radius habe ich als Konstante gespeichert , bei der Ellipsenzeichnung habe ich folgende Prozedur:

Delphi-Quellcode:

CCircle=25;
Image.Canvas.Ellipse(x-CCircle,y-CCircle,x+CCircle,y+CCircle);

Delphi-Quellcode:

Btw.: Mit den vier Koordinaten speicherst du eine allg. Ellipse. Falls alle Knoten Kreise sind, ist das ein bisschen unschön...

Ich kenn leider keine andere Methode einen Kreis in einem Image zu zeichnen :( Gibt es da eine Kreisfunktion?

Wieviele Informationen benötigst du denn in deinem Aufruf?

Delphi-Quellcode:

Image.Canvas.Ellipse(x-CCircle,y-CCircle,x+CCircle,y+CCircle);

Ich sehe da nur die Mittelpunkt-Koordinaten und den Radius (und der ist ja konstant).

Wozu speicherst du also die Eckkoordinaten der Ellipse?

[Nathaniel]

Zitat:

Wieviele Informationen benötigst du denn in deinem Aufruf?

Delphi-Quellcode:

Image.Canvas.Ellipse(x-CCircle,y-CCircle,x+CCircle,y+CCircle);

Ich sehe da nur die Mittelpunkt-Koordinaten und den Radius (und der ist ja konstant).
Wozu speicherst du also die Eckkoordinaten der Ellipse?

Ich hoffe ich habe deine Anmerkung richtig verstanden.
1) Der Aufruf Image.Canvas.Ellipse benötigt 4 Koordinaten: Start X , Start Y , Ende X , Ende Y (Ausgehend vom Mausklick, welcher X,Y liefert). Da es sich um einen Kreis handelt, ist natürlich die linke Seite mit der rechten identisch nur das die Vorzeichen vertauscht sind.

2) Ich speichere die Eckkoordinaten in einem Array um darauffolgend zu prüfen, ob eine Kante die der Benutzer zeichnen möchte, IN dem Kreis (Waypoint) ist.

@himitsu:

Danke für diese tolle und schönere Alternativmöglichkeit! Ich werde wohl die Rectangle Methode in Betracht ziehen, in der ich die Koor. X und Y an die Funktion gebe. Top Hilfe vielen Dank :thumb:


@Furtbichler:

Anscheinend bist du der einzige der die Fragestellung überhaupt nicht verstanden hat, da von den anderen passende Lösungsvorschläge gekommen sind. Aber um jetzt keinen unnötigen Konflikt (worauf ich gar keine Lust habe) zu erzeugen, sag ich dir folgendes: Ich werde deinen Tipp für die Zukunft berücksichtigen. Danke das du so freundlich bist und bleib wie du bist. Damit machst du dir sicherlich viele Freunde in deinem Leben! :thumb:

Greets

[Sir Rufo]

Zitat:

Zitat von Nathaniel (Beitrag 1175680)

Zitat:

Wieviele Informationen benötigst du denn in deinem Aufruf?

Delphi-Quellcode:

Image.Canvas.Ellipse(x-CCircle,y-CCircle,x+CCircle,y+CCircle);

Ich sehe da nur die Mittelpunkt-Koordinaten und den Radius (und der ist ja konstant).
Wozu speicherst du also die Eckkoordinaten der Ellipse?

Ich hoffe ich habe deine Anmerkung richtig verstanden.
1) Der Aufruf Image.Canvas.Ellipse benötigt 4 Koordinaten: Start X , Start Y , Ende X , Ende Y (Ausgehend vom Mausklick, welcher X,Y liefert). Da es sich um einen Kreis handelt, ist natürlich die linke Seite mit der rechten identisch nur das die Vorzeichen vertauscht sind.

2) Ich speichere die Eckkoordinaten in einem Array um darauffolgend zu prüfen, ob eine Kante die der Benutzer zeichnen möchte, IN dem Kreis (Waypoint) ist.

Warum du das gemacht hast ist mir schon klar, aber ich wollte eigentlich darauf hinaus, dass es unsinnig/überflüssig/umständlich ist diese Eckkoordinaten zu speichern.

Du begründest das damit, dass du für das Zeichnen des Kreises diese 4 Eckpunkte benötigst, in Wirklichkeit benutzt du aber den Kreis-Mittelpunkt in Verbindung mit dem Radius.
Jetzt sind diese Eckkoordinaten (auf ein mal) nur noch für die Prüfung zuständig ... allerdings eine Prüfung die auf ein Rechteck und nicht auf einen Kreis prüft.

Den Abstand zwischen 2 Punkten ermittelt man mit:

Delphi-Quellcode:

function DistanceBetweenPoints( const pt1, pt2 : TPoint ) : Extended;
begin
  Result := Sqrt( Sqr( pt1.x - pt2.x ) + Sqr( pt1.y - pt2.y ) );
end;

Ist dieser Abstand kleiner oder gleich dem Radius, dann ist der Punkt im Kreis.

Ich hoffe es wird jetzt klarer, warum die Eckkoordinaten unsinnig/überflüssig/umständlich sind.

BTW: Die Kommentare von Furtbichler lagen mir auch auf der Zunge, aber er war einfach nur schneller. Und nur weil himitsu mit einem Schuss ins Blaue ins Schwarze getroffen hat, sollte man nicht davon ausgehen, dass man sich verständlich ausgedrückt hat.

[Nathaniel]

In Ordnung, das Anliegen wäre dann geklärt.
Danke.

[jus]

Ist zwar offtopic, doch wie erkennt man, das windows nicht aktiviert wurde? :oops:

Lg,
Jus

[Sir Rufo]

im ersten beitrag hatte der te ein screenshot vom gesamten bildschirm und unten rechts in der ecke hat windows ihn verpetzt ;)