Pixelkoordinaten einer Linie

[Nikolas]

Zitat:

Erstmal studiere ich Informatik,

oh. tschuldige. Aber affin linear klingt einfach lustiger. Alternativ auch einfach Geradengleichung.

Zitat:

Hm.. Lambda ist doch der Faktor, mit dem der Richtungsvektor multipliziert bzw. verlängert wird. Wenn der bei P1 startet und nicht negativ ist, kann der erhaltene Punkt doch immer entweder zwischen den zwei Punkten oder darauf, oder hinter dem 2. Punkt liegen, oder?

Ja, das stimmt. Welchen Wert hat den Lampda kurz vor, bei und hinter dem zweiten Punkt?

So und da ich hier nicht nur meckern will, kommt hier mein Vorschlag:

(Da du nichts über dein Alter geschrieben hast, kann es sein, dass du die Lösung noch nicht verstehst, das ganze ist auf Abiniveau)

Du beginnst mit dem Vorschlag von torpedo und stellst so eine Parametergleichung auf. Jetzt kannst du jeden Punkt auf der Geraden durch einen Wert von lambda bezeichnen. Jetzt nimmst du dir den satz von Pythagoras und bestimmst den Punkt auf der Geraden, der am nächsten zum untersuchten Punkt liegt.
Jeder Punkt ist als (a,b)+p*(v,w) darstellbar, dein untersuchter Punkt liege bei (x,y). Jetzt also schnell d=sqrt( (a+p*v-x)^2 + (b+p*w-y)) nach p abgelitten, Null setzen, und deinen MinimalAbstand finden. Jetzt testest du, ob der Parameter zwischen Null und Eins liegt. Warum, kann dir Torpedo erlären. Wenn du also so einen Punkt gefunden hast, schaust du nach, ob der Abstand an dieser Stelle kleiner als ein vorher von dir festgelegter Wert ist, z.B. 2Px. In diesem Fall liegt dein Punkt auf der Geraden, sonst nicht. Hier hast du den Vorteil, dass du recht exakt einstellen kannst, wie weit dein Punkt von der Geraden entfernt sein darf, und immer noch drauf liegt. Wenn du diesen Wert änderst, könntest du z.B. auch auf dickere Linien testen, was mit den anderen Verfahren nicht möglich ist, da sie ihr Augenmerk auf die mathematische Exaktheit gelegt haben.

Die Rechnung oben mit dem Ableiten und Nullsetzen ist nicht allzu schön, da du noch eine quadratische Gleichung lösen musst, (glaube ich), den Code könnte ich dir aber geben, da ich sowas für meine Physikengine berechnen musste.




Alternativ kannst du das gleiche Verfahren auch auf Mittelstufen Niveau fahren, ohne das es am ergebniss etwas ändert:

Du stellst eine Geradengleichung wie 3of8 auf (f(x)=mx+c). Jetzt nimmst du eine weitere Gerade auf, die durch den zu betrachtenden Punkt geht, aber die Steigung -1/m hat. (g(x)=-1/m*x+d)
Diese Gerade verläuft senkrecht durch die erste Gerade. (einfach mal ausprobieren). Jetzt berechnest du den Schnittpunkt der Geraden und überprüfst, ob er zwischen den beiden Punkten liegt, die die erste Gerade definieren. (einfach Kontrollieren, ob sein x (und y) wert zwischen den Werten der Punkte liegt)
Falls er nicht drauf liegt, bist du hier fertig und der zu betrachtende Punkt liegt nicht zwischen den Punkten.
Sonst: Dieser Punkt ist der Punkt auf der geraden, der den kleinsten Abstand zum untersuchten Punkt hat. Diesen Abstand kannst du einfach mit dem Pythagoras berechnen. Dieser Wert, den du jetzt in der Hand hällst, ist der Abstand des Punkts zu Geraden. Wenn der Punkt mathematisch exakt auf der Linie sein soll, testest du den Wert auf Gleichheit mit Null, wenn du eine breitere Linie hast, einfach darauf, ob er kleiner als die halbe Linienbreite ist. Damit hast du ein auf die Linienbreite anpassbares Verfahren auf Mittelstufen Niveau. (Nur für senkrechte und waagrechte Linien musst du eine Sonderbehandlung einbauen, aber die ist wirklich einfach)

[calculon]

Zitat:

Die Frage ist nur, ob die Antwort zum Problem passt. Leider wurde es nicht genau beschrieben.
Interessant ist doch, ob es hier um Pixel oder Punkte geht. (Integer oder real) die vorgeschlagenen verfahren laufen auf das zweite herraus, wobei der Borg nicht erklärt hat, wann eine Gleichung wahr ist, also wann zwei Zahlen gleich sind.

Es geht um Pixel (Integer).

Zitat:

Zitat von Nikolas

Wenn das Ganze also ein Zeichenprogramm werden soll, wird man mit den Verfahren nicht glücklich, da sie alles sehr genau nehmen.

Es geht um ein Spiel.

Meine Function sieht nun so aus und scheint zu funktionieren:

Delphi-Quellcode:

function TSpieler.FreieSicht(x1,y1,x2,y2,nummer:integer):boolean; 
var 
m: double; // <-- Steigungskonstante 
x3, y3: integer; // <-- Spielerkoordinaten 
begin 
  x3 := mdaten.daten[nummer].X; 
  y3 := mdaten.daten[nummer].Y; 

  // Wenn P1 und P2 senkrecht stehen: 
  if (x1 = x2) and (x3 = x1) then 
    begin 
      if ((y3 >= y1) and (y3 <= y2)) or ((y3 <= y1) and (y3 >= y2)) then 
        begin 
          result := true; // innerhalb der Strecke [P1P2] 
        end 
        else 
        begin 
          result := false; // außerhalb der Strecke [P1P2] 
        end; 
      exit; 
    end; 

  m := (y2-y1)/(x2-x1); // Berechnung der Steigung 

  if (y3 = round(x3 * m + y1)) then 
    begin 
      if ((x3 >= x1) and (x3 <= x2)) or ((x3 <= x1) and (x3 >= x2)) then 
        begin 
          result := true; // innerhalb der Strecke [P1P2] 
        end 
        else 
        begin 
          result := false; // außerhalb der Strecke [P1P2] 
        end; 
      exit; 
    end 
    else 
    begin 
      result := false; 
      exit; 
    end; 
end;

Das mit den Vektoren werd' ich mir mal auch genauer anschauen. Auf jeden Fall Danke für die Hilfe!

Gruß

Calculon
--

[3_of_8]

Delphi-Quellcode:

function TSpieler.FreieSicht(x1,y1,x2,y2,nummer:integer):boolean;
var
m: double; // <-- Steigungskonstante
x3, y3: integer; // <-- Spielerkoordinaten
begin
  x3 := mdaten.daten[nummer].X;
  y3 := mdaten.daten[nummer].Y;

  // Wenn P1 und P2 senkrecht stehen:
  if (x1 = x2) and (x3 = x1) then
    Result:=y3 >= y1) and (y3 <= y2)) or ((y3 <= y1) and (y3 >= y2)
  else begin
    m := (y2-y1)/(x2-x1); // Berechnung der Steigung
    Result:=((x3 >= x1) and (x3 <= x2)) or ((x3 <= x1) and (x3 >= x2)) 
      and (y3 = round(x3 * m + y1));
  end;
end;

Das finde ich etwas einfacher. ;)

[Torpedo]

Zitat:

Zitat von Nikolas

Ja, das stimmt. Welchen Wert hat den Lampda kurz vor, bei und hinter dem zweiten Punkt?

Ah genau, daran habe ich gar nicht gedacht ;)
Je näher an Punkt 1, desto näher ist Lambda bei 0 und je näher bei Punkt 2, desto näher ist es bei 1.
Grund: Der Richtungsvektor hat seinen Startpunkt in P1 und die Spitze in P2. Also wenn man ihn mit 1 multipliziert bleibt er gleich lang und zeigt weiterhin auf P2. Wenn man ihn mit 0 multipliziert schrumpft er auch auf 0 und bleibt beim Startpunkt P1.

[Nikolas]

hast du damit auch mal ein paar Testläufe gemacht? Also, wenn dein Spieler bei 0/0 steht, nach 100/100 schaut, und du den Punkt 49/50 testest?

Delphi-Quellcode:

x3 := mdaten.daten[nummer].X;
  y3 := mdaten.daten[nummer].Y;

Nur so: vielleicht solltest du 'Daten' eher in 'Position' umbenennen, sonst wirds unübersichtlich.

[calculon]

Zitat:

Zitat von Nikolas

hast du damit auch mal ein paar Testläufe gemacht? Also, wenn dein Spieler bei 0/0 steht, nach 100/100 schaut, und du den Punkt 49/50 testest?

Ich weiß, was du meinst, das Problem wird später behandelt ;-) Am coolsten wäre es halt schon, wenn der Funktion die Dicke der Linie (Canvas.Pen-mäßig in Integer) mitgegeben werden könnte...

Zitat:

Zitat von Nikolas

Nur so: vielleicht solltest du 'Daten' eher in 'Position' umbenennen, sonst wirds unübersichtlich.

Daten umfasst mehr als nur die Positionen.

Gruß

Calculon
--

[Nikolas]

Zitat:

Am coolsten wäre es halt schon, wenn der Funktion die Dicke der Linie (Canvas.Pen-mäßig in Integer) mitgegeben werden könnte...

Dann könntest du einfach meine Version umsetzen...

[Hawkeye219]

Hallo,

um noch einmal zur Ausgangsfrage nach einer "virtuellen" Linie zurückzukommen: der folgende Code verwendet die GDI-Funktion LineDDA, um alle Punkte der Linie zu ermitteln. Für jeden Punkt wird die Funktion HitTest aufgerufen, die den Abstand zwischen dem Testpunkt und dem aktuellen Punkt der Linie mit einem Schwellwert vergleicht. Wird der Schwellwert für mindestens einen Punkt unterschritten, war der Test erfolgreich.

Delphi-Quellcode:

type
  PHitInfo = ^THitInfo;
  THitInfo = record
    px, py   : Integer;
    accuracy : Integer;
    hit      : Boolean;
  end;

procedure HitTest (X, Y: Integer; lpData: LParam);  stdcall;
begin
  with PHitInfo(lpData)^ do
    if (Sqr(px - X) + Sqr(py - Y) <= Sqr(accuracy)) then
      hit := True;
end;

// P1, P2 beschreiben die Linie
// x, y sind die Koordinaten des zu testenden Punktes
// accuracy ist eine (optionale) Empfindlichkeit für den Test (0=exakt)
function LineHit (const P1, P2: TPoint;  x, y: Integer;  accuracy: Integer = 0): Boolean;
var
  Info : THitInfo;
begin
  Info.px := x;
  Info.py := y;
  Info.accuracy := accuracy;
  Info.hit := False;
  LineDDA(P1.X, P1.Y, P2.X, P2.Y, @HitTest, Integer(@Info));
  Result := Info.hit;
end;

Das Laufzeitverhalten dürfte schlechter als das der bereits vorgestellten Lösungen sein. Falls eine große Anzahl von Linien überprüft werden muß, sollte man vielleicht einen bounding box test vorschalten.

Gruß Hawkeye

[Torpedo]

Habe jetzt mal das mit den Vektoren und der Differenzialrechnung durchgerechnet:

Delphi-Quellcode:

lambda := (sqr(p1.x)-p1.x*(p2.x+p3.x)+p2.x*p3.x+(p1.y-p2.y)*(p1.y-p3.y))/(sqr(p1.x)-2*p1.x*p2.x+sqr(p2.x)+sqr((p1.y-p2.y)));

Scheint auch zu funktionieren. Das ist dann Lambda für den Punkt auf der Geraden, der P3 am nächsten ist.

[Nikolas]

könntest du das mal ausführlicher hinschreiben? Mich wundert besonders die Wurzel aus einzelnen Koordinaten.