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.