Hur många rutor korsar linjen?

Säg att vi har ett koordinatsystem som är indelat i rutor för varje heltal. Vi har bara positiva värden och x-max och y-max är 4, d.v.s. vi har 16 rutor. Vi ritar sedan in en rät linje och vill ta reda på hur många rutor den korsar, hur gör man det på ett effektivt sätt?

Linjens start- och slutpunkt har vi, men vill bara veta generellt hur man löser detta.

För lite information

Vad mer behöver man/du?

De tva punkernas talpar

Du behöver veta var linjen börjar och slutar, inte bara vilka två rutor utan också var i rutorna den börjar/slutar: du kan få helt olika svar beroende på om linjen börjar/slutar i ett hörn eller mitt i rutorna.

Sedan bör du ha klart för dig exakt vad du menar med "korsa". Tänk dig en linje som börjar i en ruta och slutar i rutan precis till höger om startrutan. Har den linjen korsat två rutor? Eller inga? Eller kanske en? För min del känns "inga" som rätt svar, men "två" kan vara lika rätt.

Förstår vad ni menar, var nog väldigt fel av mig att anta att ni skulle tänka att det var alla rutor linjen låg på. Löste det iaf med en DDA algoritm för intresserade.

Ta ut två koordinater (x1,y1) (x2,y2).
Lutningen på linjen är kvoten av delta y genom delta x.
Dvs k = (y2 - y1)/(x2 - x1)

Eller grafiskt genom att tänka dig att lutningen som en trappa och räkna hur många rutor i y-leds för varje steg i x-led.