Gibt es eine direkte Verbindung zwischen 2 Pixeln

[Flogo]

Hi :hi:
Ich hab mich heute an einer A*-Umsetzung versucht und bekomme auch relativ gute Ergebnise. Die Ergebnispfade sind bei mir Arrays of TPoint, die ich jetzt vereinfachen will. Aus einer Kette von vielleicht 50 Punkten, will ich jetzt die "Schlüsselpunkte" herausfinden, d.h ich will solange den Punkt i aus der Liste löschen, solange eine direkte Verbindung zum Punkt i+1 noch möglich ist. Und genau da ist mein Problem:
Wie schaffe ich es ohne einen riesen Rechenaufwand festzustellen, ob die Verbindung zwischen 2 Punkten frei ist?

Ich hoffe das hat jetzt jemand verstanden ...

[StefanDP]

vom prinzip müsst des ja so gehen

Code:

funktion checke(feld: TPoint): boolean
wenn (feld nicht-möglich/erlaubt)
  ergebnis = false
sonst wenn (feld  = ziel)
  ergebnis = true
sonst
  result := checke(f1) or checke(f2) or checke(f3) // alle umliegenden felder

[Flogo]

Das Problem ist, dass ich ja nicht nochmal alle Felder untersuchen will - ich weiß ja dass es einen Weg gibt - sondern nur die, die auf der direkten Linie zwischen zweit Punkten liegen. Und das ist eben leider nicht immer eindeutig:
http://www.Anyxist.de/florian/Pixel.JPG
Also müsste die Frage wahrscheinlich eher so heißen:
Wie komme ich am schnellsten an die Koordinaten von allen Pixeln, die auf der Linie liegen

[Nicodius]

Zitat:

ob die Verbindung zwischen 2 Punkten frei ist?

... einfach die nachpar pixel um den einen prüfen ;)
if cancas.pixels[x+1,y+1] = clwhite(oder halt die "leere farbe" oder halt "nicht die punktfarbe der punkte

then


und das in ner schleife ;)

[Nikolas]

Was ist denn genau die Aufgabe die du damit lösen willst? Ich hab den Hintergrund nicht ganz verstanden, aber mein Ansatz wäre zu versuchen, eine Art Funktion für diese Pixel aufzustellen:
Vom Pixel A(0,0) zum Pixel B(10,20) sähe das dann so aus:

f(x)=[(20-0)/(10-0)]*x. // Steigungsdreieck wie aus der 8. Klasse

Und dann

Delphi-Quellcode:

for i:= A.x to B.x do
Pixel[A.x+i,A.y+f(i)].color:=ClLiegtdrauf.

Nur beim Runden gibts Probleme.

[Nicodius]

wie ichs verstanden habe mag e nur wissen ob eine linie existiert ... da genügt ein schwarzer pixel in z richtung und x länge ;)

[omata]

Moin,

dafür ist etwas Vektorrechnung erforderlich...

Ich habe hier mal die Berechnung für 3D-Punkte angegeben, wenn du nur 2D-Punkte hast lässt du einfach die dritte Dimenstion auf Null.

Delphi-Quellcode:

type
  TPoint3D = packed record
    X: Longint;
    Y: Longint;
    Z: Longint;
  end;

  :

function Point3D(X, Y, Z: Integer): TPoint3D;
begin
  Result.X := X;
  Result.Y := Y;
  Result.Z := Z;
end;

function PunktAufGerade(P1, P2, P3:TPoint3D):boolean;

  function subP(P1, P2:TPoint3D):TPoint3D;
  begin
    Result.X:=P1.X - P2.X;
    Result.Y:=P1.Y - P2.Y;
    Result.Z:=P1.Z - P2.Z;
  end;

  function skalar(a, b:integer):integer;
  begin
    if b = 0 then
      Result:=0
    else
      Result:=a div b;
  end;

var a, b:TPoint3D;
    sX, sY, sZ:integer;
begin
  a:=subP(P2, P1);
  b:=subP(P3, P1);

  sX:=skalar(a.X, b.X);
  sY:=skalar(a.Y, b.Y);
  sZ:=skalar(a.Z, b.Z);

  Result:=    (sX = sY)
          and (sX = sZ);
end;

procedure TForm.ButtonClick(Sender: TObject);
var a, b, c:TPoint3D;
begin
  a:=Point3D(3, 0, 4);
  b:=Point3D(1, 1, 1);
  c:=Point3D(-1, 2, -2);
  if PunktAufGerade(a, b, c) then
    showmessage('auf der Gerade')
  else
    showmessage('nicht auf der Gerade');
end;

hier wird getestet, ob die drei Punkte auf einer Geraden liegen.


MfG
Thorsten

[nailor]

da gibt so einen freakigen algo, der testet, auf welche felder man kommt, wenn man von A nach B will. der schaut immer, ob man eher rechts oder eher oben muss (angenommen man muss nach rechts oben), geht dann dorthin und testet weiter.

auf den namen komm ich leider nicht. das mit dem steigungsdreieck ist ne übergangslösung, die allerdings funktionieren sollte.

[dizzy]

Zitat:

Zitat von Flogo

Ich hab mich heute an einer A*-Umsetzung versucht und bekomme auch relativ gute Ergebnise [...] die ich jetzt vereinfachen will.

Den Algo hatter schon ;)

[maximov]

Eine mögliche lösung wäre es, die heuristik (ziel strecken schätzung) über zu bewerten, sodass die kantenkosten an gewicht verlieren. So kannst du dich der luftlinie annähern und es werden trotzdem noch schwere hindernisse umgangen. Auf dem resultierenden pfad kannst du dann die punkte mit gleichem delta-vektor streichen...

[choose]

Hallo nailor,

Zitat:

Zitat von nailor

da gibt so einen freakigen algo, [..] auf den namen komm ich leider nicht.

wenn ich Dich richtig verstehe, suchst Du nach dem bresenham Algorithmus.

[Flogo]

habs grad nur überflogen aber ich glaube dieser Bresenham Algo ist das, wonach ich gesucht habe.
Ich werde aber wahrscheinlich trotzdem Toxmans ( :hi: ) Variante nehmen, weil es bei mir nicht so auf Genauigkeit, sondern eher auf Geschwindigkeit ankommt.

@maximov:
delta-vektor? Habichnicht, kennichnicht, wasissndas?

Thx@all

[choose]

Zitat:

Zitat von Flogo

weil es bei mir [..]eher auf Geschwindigkeit ankommt.

Der Bresenham-Algorithmus ist deshalb so verbreitet, weil er a) sehr performant ist (innere Schleife kommt ohne Division oder Multiplikation aus) und b) jeden Punkt nur einmal betrachtet, aber auch keine "Lücken" lässt, was bei Toxmans Ansatz bei großen Steigungen der Fall sein könnte. Wählte man hingegen eine kleinere "Schrittlänge" könnten Punkte nach Toxmans Lösung mehrfach betrachtet werden...

Zitat:

Zitat von Flogo

delta-vektor? [..] wasissndas?

Könnte man als eine "Verallgemeinerung" der Variante von Toxman betrachten... Statt pro x-Einheit delta y-Einheiten zurückzulegen (eindimensionaler Vektor) könnte man auch pro gedachter Einheit dx x-Einheiten und dy y-Einheiten zurücklegen.
Wählt man die Größe der gedachten Einheit zur Problemstellung geeignet (z.B. ganze Längeneinheiten oder Unterteilung in n Intervalle), ist dieser Ansatz für viele Anwendungsfälle geeignet und entgeht auch den oben genannten Einwenden zum größten Teil, hat aber immer noch Probleme mit einigen Grenzfällen.

[Flogo]

:oops:

Ich muss zugeben, ich hab den Alorithmus nur überflogen und das sah so komliziert aus, dass ich dachte der ist zwar genau, braucht aber auch dementsprechend Rechenleistung. Ich werd ihn mir jetzt nochmal genauer anschauen.
Danke!

[nailor]

das ist der, den ich meinte ;)