Kartesisches Koordinatensystem, herausfinden welche "Felder" von einer Linie geschnitten werden?
Das Problem kommt von einem Spiel, das ich momentan programmiere. Ich möchte herausfinden, welche Felder auf einem "Schachbrett" von einer Linie geschnitten werden, die von der Mitte eines Feldes a zur Mitte eines Feldes b geht.
Ich habe eine Sammlung von Punkten mit einer x- und y-Koordinate. Nun interpretiert man diese Punkte in einem kartesischen Koordinatensystem, sodass diese nicht direkt auf den eigentlichen Punkten, sondern in der Mitte der Quadrate der ganzen Zahlen liegen.
Siehe Bild für eine bessere Vorstellung.
Nun möchte ich herausfinden, welche Felder von der roten Linie von a nach b geschnitten werden. (Die Beige markierten werden geschnitten und die möchte ich ausfindig machen. Es reicht wahrscheinlich, wenn ich für ein Feld mit bestimmten Koordinaten angeben kann, ob die Linie a nach b dieses Feld schneidet.)
Ich weiß, dass man dafür mathematisch keine Größe der Felder braucht, aber ich komme irgendwie auf keinen Ansatz.
Die Lösung brauche ich nur für natürliche Zahlen und Koordinaten.
Bonus:
Ich möchte Felder, deren Ecken bei einer 45° diagonalen Linie mathematisch nur "berührt" werden nicht mit aufnehmen.
2 Antworten
Ist ja nun schon ein paar Jahre her, aber als ich deine Grafik sah, erschien sofort in meinem Kopf das Wort "Bresenham".
Ich weiss das noch, weil wir mal als Projekt ein 128x128 Display mit grafischen Elementen programmiert haben. Genau da brauchten wir das.
Es geht halt nichts über eine solide Ausbildung. ;-)
Viel Erfolg wünsch ich dir bei deiner.
PS. Für mich ist Morgen. Bin heut früh aufgestanden.
Triviale Kiste: Iteriere über das größere Delta und bestimme mit Hilfe der Geradengleichung die fehlende der Koordinaten.
Scharf nachgedacht: Im Endeffekt ist das nichts anderes als ein Sampling der Gerade mit Quantisierung.
Man kann natürlich auch ein Oversampling machen (Oder in Bezug auf Pixel ein Subpixel Sampling) - Stellen wir uns für den Moment mal vor, unser Kasten wäre in 16 (4x4) Kästchen unterteilt. Wir samplen also 4 mal für einen Kasten. Wir können nun einen Threshold bilden und sagen: Nur wenn ein (großer) Kasten für mehr als 1 Sample getroffen wird (mehr als 1 Unterkästchen), wird er getroffen. Hierdurch entsteht eine weichere Grenze.
Vielen vielen Dank.
Ich studiere tatsächlich auch Informatik (wofür das Projekt auch ist) und hab' davon (noch) nie gehört. Meine Google Anfragen waren auch vergeblich.
Manchmal muss man einfach wissen, wie der Algorithmus heißt.
Bist ein Schatz, danke und schönen Abend.. Morgen?