Is there any algorithm which takes edges (given by its two end points), and determines in which cell (or cells) of grid it is?
Grid has fixed dimensions and number of cells. Grid is represented by its cells with matrix. And every cell has list of edges that intersect that cell.
Input is set of pair points, but I can also transform it in just set of points, or any other needed representation. Output should be the mentioned grid with cells who contain list of edges that intersect that cell.
Algorithm should be fast and robust, and by that I mean it covers special (degenerated) cases and that its time complexity is good.
What I want to be able is to use that grid later for search, for example to answer me question like "Which cells does given edge AB(with end points A and B) intersect?" or "Give me all edges that intersect cell 12"(First row, second column).