I have a 2D grid made of small rectangles that have a horizontal length dx and vertical dy. If I draw a sine wave on the grid, I want to identify all the rectangles for which this line goes through.
Are there any well known algorithms that I could look at? I haven't had much luck online. I am basically trying to do Bresenham's line algorithm, but for an arbitrary sine wave rather than a straight line.
I am doing all this in the context of a Hough transform, where my grid act as an accumulator that counts how many sine waves go through each rectangle.
You have curve equation for parameter t and want to find intersected "cells" - your small rectangles.
When current point is in some rectangle, it's borders are lines x=k*dx, x=(k+1)*dx, y=m*dy, y=(m+1)*dy, where k,m are rectangle "coordinates".
You have to check what border will be intersected first (with smaller t parameter). For sine function it is not needed to check left border. So solve equations
t1 = (k+1)*dx
sin(t2) = m*dy => t2 = arcsin(m*dy)+ 2*Pi*n, Pi-arcsin(m*dy)+ 2*Pi*n
sin(t3) = (m+1)*dy
and choose smallest value from (t1,t2,t3) larger than current t. If t1 is the smallest - you enter right cell, k increases. If t2 is the smallest - you enter bottom cell, 'm' decreases, otherwise upper cell and m increases.
Now you have point of intersection with the next cell, new starting t and continue.
This approach is similar to Amanatides and Woo method to select voxels being intersected by a ray/line.
Emm..OK, seems like overhead for the task of Hough transform, so subdividing into small line segments should work good enough.