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?

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 von Furtbichler:

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 von Nathaniel:

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 (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 (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!

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);

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 von Nathaniel:

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 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 von Nathaniel:

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);

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?
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?