Pixelkoordinaten einer Linie

[calculon]

Hi Leute,

ich will eine Prüfung durchführen, ob sich zwischen zwei Punkten ein Punkt befindet und habe mir gedacht eine Linie zwischen diesen zwei Punkten zu zeichnen:

Delphi-Quellcode:

image1.canvas.moveto(10,10);
image1.canvas.lineto(20,20);

Kann ich mir die Koordinatenliste aller einzelnen Punkte ausgeben lassen oder gibt es eine Möglichkeit eine "virtuelle" Linie zu erzeugen und deren Koordinaten sich ausgeben zu lassen?

Gruß

Calculon
--

[3_of_8]

Stichwort: Lineare Funktion

Jede Linie (naja, außer einer senkrechten) lässt sich als lineare Funktion darstellen. Eine lineare Funktion ist eine Funktion f(x)=mx+t. Wenn du also zwei Punkte P1(x1|y1) und P2(x2|y2) hast, kannst du m und t folgendermaßen berechnen:

t=y1
m=(y2-y1)/(x2-x1)

Wenn du jetzt einen Punkt P3(x3|y3) hast, musst du nur noch die Koordinaten einsetzen, wenn also folgende Gleichung gilt, liegt P3 auf der Gerade P1P2:
y3=x3*m+t

Wenn du wissen willst, ob P3 auf der Strecke [P1P2] liegt, musst du noch überprüfen, ob x1<=x2<=x3.

Eine Ausname ist, wie gesagt, eine senkrechte Gerade (also mit y1=y2), da musst du überprüfen, ob y3=y1. Bei einer senkrechten Strecke musst du außerdem noch überprüfen ob y1<=y2<=y3.

[calculon]

Vielen Dank für die Lehrstunde! Setze so das um! Muss mal anmerken: :dp:

[Namenloser]

Hi,

ich würde zuerst den Winkel zwischen dem Startpunkt und dem Endpunkt der Linie errechnen. Dann würde ich den Winkel zwischen dem Startpunkt und dem zu Prüfenden Punkt ermitteln und die beiden Winkel vergleichen: Wenn sie nicht überinstimmen, kann auch der Punkt nicht auf der Linie liegen. Wenn der Winkel jedoch überinstimmt, prüfst du, wie weit er vom Anfangs- und Endpunkt der Linie entfernt ist: die Distanz darf bei beiden maximal die Länge der Linie betragen, ansonsten ist er nicht auf der linie.

Achtung: Ich bin nur ein Siebt-(bald Acht-)klässler, kann also durchaus sein, dass es einfachere/schnellere Methoden gibt, um das zu prüfen :wink:

//Edit: da war wohl jemand schneller :/

[Torpedo]

Geht auch mit Vektoren.
Man zieht einfach eine Gerade durch die 2 Punkte und Prüft, ob der 3. Punkt auch auf der Geraden Liegt.

Gerade: [x y] = [p1.x p2.y] + lambda * [p2.x-p1.x p2.y-p2.y]
Das ist die Gerade. Je nachdem welche Zahl man für lambda einsetzt, berechnet man einen anderen Punkt auf der Geraden. Gibt es ein lambda, durch das man den 3. Punkt erhält, liegt dieser auf der Geraden. (Achtung: muss nicht zwischen den Punkten liegen. Kann man später aber mit dem x-Wert überprüfen)

Gleichungssystem:

p3.x = p1.x + lambda * (p2.x-p1.x)
p3.y = p1.y + lambda * (p2.y-p1.y)

Oder kurz:

Delphi-Quellcode:

if (p1.x-p3.x)/(p1.x-p2.x) = (p1.y-p3.y)/(p1.y-p2.y) then -> auf der Geraden

Oder vielleicht auch das, wenn das obere nicht funktionieren sollte:

Delphi-Quellcode:

if abs((p1.x-p3.x)/(p1.x-p2.x)-(p1.y-p3.y)/(p1.y-p2.y))<0.001 then -> auf der Geraden

Keine Ahnung ob das jetzt so stimmt, ist schon etwas her, dass ich das in der Schule gelernt habe, aber müsste schon funktionieren. ;)

[3_of_8]

@NamenLozer: Das geht natürlich auch, aber dafür braucht man deutlich mehr Rechenschritte und Arcus-Sinus/Cosinus usw., ich glaube fast, dass meine Methode einfacher ist. (Und schneller)

[Namenloser]

@3/8: Ja, das habe ich mir schon fast gedacht, dass es auch schneller geht, aber so komischen Kram hatten wir in der Schule leider noch nicht^^. Und wenn wir es dann kriegen, hab ich es wahrscheinlich irgendwie schon so gelernt, ist eigentlich immer so :roll:
Den ganzen sin/cos kram habe ich mir auch selber beigebracht, offiziell haben wir sogar dieses Schuljahr erst Minuszahlen kennen gelernt (Und dann wundern sich alle über Pisa :wall: )

[Nikolas]

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.

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

@ torpedo: ''(Achtung: muss nicht zwischen den Punkten liegen. Kann man später aber mit dem x-Wert überprüfen) ''
Überleg nochmal, was das Lamda eigentlich bedeutet und ob man nicht vielleicht auch nur damit entscheiden kann, ob der Punkt zwischen den beiden andere liegt.

@ 3of8: besuchst du nicht diese Fernuni Hagen und hörst Mathe? In dem Fall solltest du f(x)=mx+c (c<>0) wirklich nicht als lineare Funktion bezeichnen.

@ NamensLozer: ein Sinus/Cosinus dauert etwa 200 Ticks, eine Multiplikation etwa 8, was du brauchst ist aber der asin, der dann schon mal seine 2000 Ticks braucht. Wenn es also anders geht, sollte man die Finger von den Trigonometrischen Funktionen lassen

[Torpedo]

Zitat:

Zitat von Nikolas

@ torpedo: ''(Achtung: muss nicht zwischen den Punkten liegen. Kann man später aber mit dem x-Wert überprüfen) ''
Überleg nochmal, was das Lamda eigentlich bedeutet und ob man nicht vielleicht auch nur damit entscheiden kann, ob der Punkt zwischen den beiden andere liegt.

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

[3_of_8]

Erstmal studiere ich Informatik, die Mathematik, die ich da habe, ist in etwa so, dass ich mich jedes mal freue, wenn ich eine Zahl sehe.

Also für mich ist f(x)=mx+t eine ziemlich lineare Funktion. An der Schule lernt man eine lineare Funktion als f(x)=mx+t kennen. Wenn man das ganze jetzt streng mit Vektorräumen macht, ist es natürlich keine lineare Funktion mehr, da schon das erste Axiom (Homogenität) nicht mehr erfüllt ist. (a*(mx+t)<>m(a*x)+t).

Wir wollen ja nicht gleich mit Kanonen auf Spatzen schießen, indem wir das ganze hier auf Universitätsniveau heben. ;)