Gibt es eine direkte Verbindung zwischen 2 Pixeln

[Flogo]

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