Hi,

folgendes Problem:

Ich habe zwei Koordiaten, z.B.: [10, 10] und [27, 57]. Diese Koordinaten geben Pixel auf dem Bildschirm an.

Nun brauche ich alle Pixel, die zwischen diesen zwei Koordinaten liegen, also eigentlich alle die Punkte die entstehen, wenn man die 2 Koordinaten mit einer Linie verbindet.

Habe zuerst an eine Funktion f(x) gedacht, allerdings gibts da besonders bei einer Parallelen zur Y-Achse große Probleme..

Ich hoffe, ihr habt eine Idee und könnt mir helfen.

Danke + Grüße
Passi

Hallo!

Das über eine Funktion zu machen, erscheint mir aber richtig zu sein. Den Sonderfall, wenn die beiden Punkte exakt übereinander liegen, musst Du halt gesondert behandeln.

Grüße
Christian

Die Lösung nennt sich Vektor-Rechnung ...

Du definierst Die einfach eine Funktion, die einen Vektor zurückgibt und zwar so hier:



für t zwischen 0 und 1.

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Nochmal zu der Funktion, das kann ich glaub ich vergessen, da gibts eigentlich Probleme ab einem 45° Winkel der Strecke, also ab dem Zeitpunkt, ab dem mehr als nur 1 Pixel in Y-Richtung gesetzt werden.

Hm Vektorrechnung. Blöd wenn man das noch nicht in der Schule hatte ..

Kannst Du das bitte mal in eine öm "einfache" Formel fassen? Also ich meine ohne diese "Container", was auch immer die darstellen.. oder einfach ne Formel wie man so nen Container ausrechnet ^^

Danke!

Besonders effizient, wenn du nur gerundete Pixelkoordinaten brauchst (Integer-Koordinaten): Die Bresenham Linie (->Suche)

Passi077 hat folgendes geschrieben:

Nochmal zu der Funktion, das kann ich glaub ich vergessen, da gibts eigentlich Probleme ab einem 45° Winkel der Strecke, also ab dem Zeitpunkt, ab dem mehr als nur 1 Pixel in Y-Richtung gesetzt werden.

Ist mir nach BenBEs Posting auch eingefallen, deswegen ist seine Lösung auch die bessere.

Wenn Du es doch mit einer Funktion machen willst, musst Du das trennen. Ist der Winkel (zwischen x-Achse und Verbindungslinie, positiv gegen Uhrzeigersinn) kleiner 45°, dann verwendest Du eine Funktion f(x), Du gehst also die Pixel auf der x-Achse durch und suchst Dir den entsprechenden y-Wert. Ist der Winkel größer 45°, dann verwendest Du eine Funktion f(y), gehst also die Pixel auf der y-Achse durch und suchst Dir den x-Wert.

Aber wie gesagt: BenBEs Lösung ist deutlich eleganter.

Wenn du die Pixelkoordinaten der Linie möchtest, kriegst du diese mit der Parametrisierung der Linie nicht unbedingt direkt raus: Du musst Werte zwischen 0 und 1 einsetzen; das sind keine Pixelangaben. Wenn du die float-Werte dann noch rundest, kann es evtl. mal vorkommen, dass die Linie Pixellücken hat oder auch mal ein Pixel doppelt dabei ist.
Der Bresenham Linienalgorithmus liefert direkt die Koordinaten der Linie zurück, wie wenn man sie mit Canvas-LineTo gezeichnet hätte. Dank Integer-Arithmetik geht das auch sehr schnell. Falls du die exakten Zwischenwerte willst, dann kommst du nicht drumherum, die Linie zu parametrisieren (siehe Post von BenBE).

Zwischenfrage: Wofür brauchst du die Koordinaten?

Jo dann werd ich mir mal den Bresenham Algorythmus zu Gemüte führen.

Zitat:

Zwischenfrage: Wofür brauchst du die Koordinaten?

Ich hab ein kleines Game, und da wird ein Objekt mit einer Geschwindigkeit von bis zu 10 Pixeln pro Frame bewegt.
Kollisionen werden durch das Auslesen der Pixelfarbe einer Submap festgestellt. Nun ist das Problem, wenn die Geschwindigkeit des Objektes 10 Pixel pro Frame beträgt, und das Hinderniss nur z.B. 5 Pixel dick ist, dann wird diese Kollision nicht registriert.

Die einfachste Lösung die ich gefunden habe, ist einfach jeden abgefahrenen Pixel zu überprüfen.

Hmm. Für die Kollisionserkennung würd ich allerdings nicht den Bresenham Linienalgorithmus verwenden. Wär mir 1. zu mühsam und 2. rechnest du ja vermutlich ohnehin alles in Floatingpoint-Arithmetik; und die Geschwindigkeit ist vielleicht auch nicht immer ganzzahlig. Ich würde pro Frame einfach eine fixe Anzahl Subiterationen durchführen (Subframes erzeugen, die aber nicht angezeigt werden). Ist dann halt eventuell nicht auf das Pixel genau. Geschmackssache

Hi nochmal,

danke für den Tipp mit der Subiteration! So hab ichs nun gemacht!

Ich hoffe nur, das frisst nicht zu viel Performance - aber ich hab den Bresenham Logarithmus mal ausprobiert, der ist arschlahm .

Also Danke nochmal!

Grüße
Passi

Passi077 hat folgendes geschrieben:

Bresenham Logarithmus mal ausprobiert, der ist arschlahm

Der Bresenham Algorithmus ist sehr schnell; schneller als Floatingpoint-Arithmetik. Wenn du auf dem Bildschirm eine Linie siehst, ist die Wahrscheinlich sehr hoch, dass dieser mit dem Bresenham Linien Algorithmus gezeichnet wurde. Der Fehler liegt wohl in deiner Implementation

Hmmm ^^ naja ist nun auch egal, die Subiteration ist auch sehr schnell.

Dafür hab ich grad ein anderes Performance Problem gerade entdeckt...:

Ich arbeite mit den Grafikfunktionen von Delphi (und das ist leider Pflicht, da in der Schule kein DelphiX oder sonst was zur Verfügung steht) und hab ne Map die eine Farbe als transparente Farbe hat.

Unter WindowsXP kein Problem damit, aber unter Windows98 sinkt die Framerate von festen 30 FPS auf unter 10 FPS runter.. lass ich die transparente Farbe weg, läufts auch unter Win98 mit den 30 FPS. Kann man da irgendwas machen oder muss man dann doch mit OpenGL oder DirectX arbeiten?

Hallo!

Da die ursprüngliche Frage dem Topicstatus nach erledigt ist, mache ich hier zu. Neue Fragen bitte in einem neuen Topic stellen.

Grüße
Christian