Pixelkoordinaten einer Linie

[jfheins]

Zitat von Nikolas:

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

sqr quadriert, die Wurzelfunktion war sqrt

[Torpedo]

Ich habe das ganze einfach im Taschenrechner eingegeben und ableiten lassen (dauert ganz schön lange...) dann auf 0 gesetzt und auf lambda auflösen lassen.
Dann ist die oben genannte Formel rausgekommen. Habe es auch durchgetestet. Ich kann die Punkte drehen und plazieren wie ich will, es scheint immer zu stimmen.
Den Abstand zur Geraden rechne ich aus, indem ich noch einen Vektor vom Punkt P4 auf der Geraden (den ich mit Lambda ausgerechnet habe) zum untersuchten Punkt erstelle und den Betrag berechne:
abstand := sqrt(sqr(p3.x-p4.x)+sqr(p3.y-p4.y));

Als Quellcode: (nur schnell runtergetippt, nicht getestet!)

Delphi-Quellcode:

function Abstand (const p1, p2, p3: TPoint): double;
var
  p4: TPoint;
  lambda: double;
begin
  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)));
  p4.x := p1.x+lambda*(p2.x-p1.x);
  p4.y := p1.y+lambda*(p2.y-p1.y);
  Result := sqrt(sqr(p3.x-p4.x)+sqr(p3.y-p4.y));
end;

Kann sein dass Delphi hier mit Integer rechnet (wegen TPoint), dann kommt das falsche raus. Ansonsten sollte es stimmen.

[Nikolas]

sqr...sqrt...kann doch mal passieren...

Genau so hatte ich mir das vorgestellt. Wobei die Variante mit den Geraden auch noch per Hand einfach zu berechnen ist.
Du ignorierst aber noch das Lambda aus [0,1] sein muss. Wenn Lambda nicht in diesem Intervall liegt, müsstest du irgendeinen Fehler zurückgeben, z.B. den Abstand auf -1 setzen, dass klar ist, dass der Punkt auf keiner noch so breiten Linie liegt. Aber ein bischen Arbeit soll der Fragensteller auch noch haben.
Welchen Taschenrechner hast du da drauf losgelassen? So ein kleines Rechnzentrum wie den Ti 92 Voyage?

[Torpedo]

Habe 10 Minuten den TI 89 Titanium rechnen lassen. Als er dann immer noch nicht fertig war habe ich die Testversion von Derive6 runtergeladen und es damit lösen lassen (weniger als 1 Sekunde ).

[calculon]

Delphi-Quellcode:

function Abstand (const p1, p2, p3: TPoint): double; 
var 
  p4: TPoint; 
  lambda: double; 
begin 
  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))); 
  p4.x := p1.x+lambda*(p2.x-p1.x); 
  p4.y := p1.y+lambda*(p2.y-p1.y); 
  Result := sqrt(sqr(p3.x-p4.x)+sqr(p3.y-p4.y)); 
end;

Zitat von Torpedo:

Kann sein dass Delphi hier mit Integer rechnet (wegen TPoint), dann kommt das falsche raus. Ansonsten sollte es stimmen.

Ja, ist so, so geht es:

Delphi-Quellcode:

function Abstand (const x1, y1, x2, y2, x3, y3: Integer): double;
var
  x4, y4: double;
  lambda: double;
begin
  lambda := (sqr(x1)-x1*(x2+x3)+x2*x3+(y1-y2)*(y1-y3))/(sqr(x1)-2*x1*x2+sqr(x2)+sqr((y1-y2)));
  x4 := x1+lambda*(x2-x1);
  y4 := y1+lambda*(y2-y1);
  Result := sqrt(sqr(x3-x4)+sqr(y3-y4));
end;

Funktioniert super! Jetzt hab' ich noch'n Verständnisproblem. Die Abweichung von 0 wird hier mathematisch angegeben. Kann ich die Werte in Pixel umrechnen? Wie kann ich Toleranzen definieren?

Bsp.:
P1(0,0), P2(200,200); P3(100,101)

Die function liefert: 0,707..

Das heißt der Punkt liegt mathematisch (numerisch) nicht exakt zwischen P1 und P2, jetzt hab' ich aber keine pixelmäßige Vorstellung der Abweichung (heißt das ca. 70% eines Pixels Abweichung?).

[edit]
Hab's jetzt so und funktioniert wunderbar. Nochmals ein drittes Dankeschön an die ganzen Antworten!

Delphi-Quellcode:

function TSpieler.FreieSicht(const x1,y1,x2,y2,dicke,spielernummer: Integer): boolean;
var
x3, y3: integer;
x4, y4, lambda: double;
begin
  x3 := mdaten.daten[spielernummer].X;
  y3 := mdaten.daten[spielernummer].Y;
  lambda := (sqr(x1)-x1*(x2+x3)+x2*x3+(y1-y2)*(y1-y3))/(sqr(x1)-2*x1*x2+sqr(x2)+sqr((y1-y2)));
  x4 := x1+lambda*(x2-x1);
  y4 := y1+lambda*(y2-y1);
  // edit: (Danke für den Hinweis @Nikolas)

  {if not (((x3 >= x1) and (x3 <= x2)) or ((x3 <= x1) and (x3 >= x2))) then
    begin
      result := false;
      exit;
    end;} // <-- nö, passt au no net

  { muss mal doch genauer überlegen, wie man die Eingrenzung durchführen muss; }

  // /edit
    if round(sqrt(sqr(x3-x4)+sqr(y3-y4))) <= dicke then
      result := true
    else
      result := false;  
end;

[/edit]

Gruß

Calculon
--

[Nikolas]

Zitat:

Funktioniert super!

Das glaube ich nicht. Du solltest wenigstens versuchen, zu verstehen, was du machst, wenn du anstatt selbst zu rechnen Copy-Paste machst.

schau mal was rauskommt, wenn deine Linie durch 0/0 und 50/50 gegeben ist und teste mal den Punkt 100/100...

Zitat:

Das heißt der Punkt liegt mathematisch (numerisch) nicht exakt zwischen P1 und P2, jetzt hab' ich aber keine pixelmäßige Vorstellung der Abweichung (heißt das ca. 70% eines Pixels Abweichung?).

Ja, das heisst es. (wobei 70% eines Pixels eher ein Flächenmaß ist. genauer: der Punkt liegt etwa 70% einer Pixelbreite von der Geraden (nicht Strecke!) entfernt)

Zitat:

Wie kann ich Toleranzen definieren?

och komm. Das wurde schon mehrmals explizit erklärt. Was soll denn diese Toleranz bedeuten? (einfach mal in Worten formulieren)