Algorithm to draw sine wave on 2d grid

Question

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.

Answer 1

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.