I have a grid that represents a sampling of a continuous function in a 2 dimensional space. I'm looking for a (preferably fast) algorithm that can calculate the discrete line integral along a straight-line path from one grid cell to a distant grid cell.

This seems like it would be a canonical problem with an accepted solution, but I can't seem to find anything online or in my resources. I've made an algorithm that works for uniform grids, but occasionally hiccups when the cell height and cell width differ by a large amount due to floating point precision.

My hope is that someone has seen this problem before and can get me pointed in the right direction.

  • How is "cost" defined? Why would floating point precision cause cell height and width to differ by a large amount? Are these extremely small numbers? – Robert Harvey May 24 '16 at 17:30
  • Cost is the discrete line integral. If the value of the function in a cell is 5 and the line intersects that cell for a length of 2, then the contribution to the cost is 10. I'll clear that up in the question. The issue with precision comes into play when the real distance to the next x-intercept is equal to the real distance to the next y-intercept. These are two calculated values and the comparison requires arbitrary precision. It's not an issue when they are calculated using the same numbers, but when the width and height are different, it's a problem. – littlebenlittle May 24 '16 at 17:41
  • programmers.stackexchange.com/a/299182/106917 2D-DDA is a grid traversal algorithm that returns every cell in the grid that the line touches. The nice thing about it is it traverses start to end and allows you to easily compute the distance to the next cell wall. That means the algorithm can effectively give you every small line segment cut by the grid. I'm not sure what kind of accuracy you're looking at, but you could naively use bilinear interpolation (for the start and end of every line segment) and use the trapezoid rule for each individual line segment to get a fast result. – Sirisian May 24 '16 at 22:01
  • @Sirisian, I will look into that. At a glance, it appears to be what I'm looking for. – littlebenlittle May 25 '16 at 16:04

I assume you used Bresenham's algorithm? It works fine for nearly-horizontal or nearly-vertical cases. Works well with integer-only coordinates, too.

If your integral value depends on the amount of interconnection between a cell and the line, consider the Xiaolin Wu's antialiased line algorithm.

Both are for uniform grids only, though.

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.