0
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ that sounds like a variant of the bresenham algorithm to draw line segments given in continuous coordinates on a rasterized output device. $\endgroup$ – collapsar Apr 1 '14 at 17:22
  • $\begingroup$ @collapsar thanks for suggestion, I'll try to implement it and see if it works for me. $\endgroup$ – fuzzomorphism Apr 2 '14 at 12:37
  • 1
    $\begingroup$ @collapsar Please consider adding an answer. $\endgroup$ – Raphael Apr 2 '14 at 15:11
1
$\begingroup$

Bresenham's method is one possibility, however do be aware that as originally presented, it produces the best discrete approximation to the line, which isn't exactly what you want. You want the grid cells which include the polygon, which means that (say) left-edges should be rounded down and right-edges should be rounded up. Wu's algorithm effectively enumerates all of the cells which a line passes through, so it would probably be easier to modify that.

Do bear in mind that on a lot of modern CPUs, floating point arithmetic is extremely efficient compared with integer arithmetic, especially now that we have SIMD execution units. It can actually be more efficient in some cases since the register file and execution units for floating point are typically independent of those used for integer computations. Bresenham is still important, of course, but it's probably worth considering other methods.

Another algorithm that may be worth considering is Pineda's method, which is used by many (if not most) GPUs to scan-convert triangles into fragments. The question asked about polygon edges specifically, not the interior of polygons, but you might find some useful ideas there.

If raw speed is important, one advantage of Pineda's method is that you can enumerate which 4x4 cells the polygon touches, and then calculate individual grid entries in parallel using SIMD arithmetic. This should be very fast on modern hardware.

$\endgroup$
0
$\begingroup$

You can use line drawing algorithm like Bresenham.
The second question is just Bresenham in the loop, or simply discrete version of point on segment using discrete grid.
Bresenham algorithm presents very fast rasterization as it operates on integers - for sure faster than DDA and also works for vertical segments.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.