1

I'm looking for an algorithm that can compute all grid cells occupied by an arbitrary rectangle in 2d space in a defined area. The rectangle is defined by it's 4 corner coordinates. In the picture below I marked two of them as red, the coordinates of the grid cells are in black. I'm looking for a generic case that also covers unaligned grids (center of grid != center of underlying coodinate system), but converting between Cell coordinates <=> Coordinate system is trivial and already implemented. All cells are squares.

The calculation is done thousands in very short amounts of time and needs to be as fast as possible.

enter image description here

What I'm doing right now:

Right now I'm calculating the edges of the rectangle (AB, BC, CD, DA) and sample them at sampleRate = cellWidth / 4 intervals. To find the middle cells I construct new lines from AB + sampleRate * x to CD + sampleRate * x and sample those lines again at sampleRate. I put all cells that I find at each sampled point into a HashSet to remove duplicates. But I feel this is increadibly inefficient.

I also thought about grabbing all cells in my relevant area into a buffer and generate a range tree or index tree. Then I could queue the bounds of the rectangle and get all contained cells at O(log n+m), but I'm not sure how to implement that and I can't even find any C# range tree implementations.

My knowledge in computer graphics is very rusty, but shouldn't there be an easy geometrical approach that works without sampling?

sollniss
  • 1,895
  • 2
  • 19
  • 36
  • Why not see the rectangle as two triangles? There are a lot of well known algorithms for fast filling of a triangle. – Willem Van Onsem Aug 13 '19 at 19:20
  • @WillemVanOnsem As I said, my CG is pretty limited. What would those algorithms be? – sollniss Aug 13 '19 at 19:21
  • see https://github.com/ssloy/tinyrenderer/wiki/Lesson-2:-Triangle-rasterization-and-back-face-culling – Willem Van Onsem Aug 13 '19 at 19:22
  • and https://www.gabrielgambetta.com/computer-graphics-from-scratch/filled-triangles.html – Willem Van Onsem Aug 13 '19 at 19:22
  • Possible duplicate of [how to rasterize rotated rectangle (in 2d by setpixel)](https://stackoverflow.com/questions/10061146/how-to-rasterize-rotated-rectangle-in-2d-by-setpixel) – Spektre Aug 14 '19 at 07:06
  • convex polygons can be rasterized without triangulation ... see [how to rasterize rotated rectangle (in 2d by setpixel)](https://stackoverflow.com/questions/10061146/how-to-rasterize-rotated-rectangle-in-2d-by-setpixel) – Spektre Aug 14 '19 at 07:07

1 Answers1

1

The points you care about are marked with a dot in the image below. Each point represents either the minimum X value or the maximum X value for a given Y value. For each Y value, the X value is easily calculated from the equation for a line:

x = x0 + (y - y0)(x1 - x0) / (y1 - y0)

Note that an axis-aligned rectangle (where (y1 - y0) is 0) needs to be handled as a special (but trivial) case.

Also note that once you've computed the first X value along an edge of the rectangle, the other X values are equally spaced. The spacing is the inverse of the slope of the line. So the division
M = (x1 - x0) / (y1 - y0)
only needs to be done once, and then repeatedly added to the X value. For example, after calculating the X coordinate for point A in the image, the X coordinate for point B is Bx = Ax + M. And the X coordinate for point C is Cx = Bx + M.

Once you have the min and max X values for each Y value, it's a simple for loop to get all the cells that have that Y value.

enter image description here

user3386109
  • 34,287
  • 7
  • 49
  • 68
  • I'm not sure I understand. Where do I get the Y values from? – sollniss Aug 13 '19 at 21:20
  • 1
    @sollniss The top Y coordinate is 4.554, and the bottom Y coordinate is -1.2. So the Y values you care about are 4 to -1. – user3386109 Aug 13 '19 at 21:24
  • @sollniss I missed the part where the grid coordinates don't use the same scale as the point coordinates. So you need to convert the 4 points of the rectangle into grid coordinates first, and do all the math in grid coordinates. – user3386109 Aug 13 '19 at 21:28
  • I still don't get it. The X and Y you use are all in grid-space, or in normal space? I have a function ToGridCoordinate(Vector2), and calculate the grid coordinates for all the corner points. I don't know what the min/max X is and how to get your points. Can you maybe provide a pseudocode? – sollniss Aug 13 '19 at 21:41
  • @sollniss In your drawing, the XY values `1.843` `4.554` and `2.64` all make it appear that grid coordinates **are** normal space coordinates. But the `-1.2` appears to be off by 1, seems like it should be `-0.2`. My answer assumed that all coordinates are grid coordinates, but if they aren't, then you need to convert to grid coordinates first. – user3386109 Aug 13 '19 at 21:50
  • Yes, sorry. It is supposed to be -0.2, didn't notice. In the drawing the two coordinate system are aligned, yes. So In the general case I convert to grid coordinates, then compute the four sides and then traverse them with your formula? – sollniss Aug 13 '19 at 22:05
  • Is M still the same for cell sizes different than 1? Like say, all cells are 1.3x1.3 units. – sollniss Aug 14 '19 at 10:57
  • Cells are always 1x1 in the cell coordinate system. If they're a different size in normal space coordinates, that affects the transformation of the 4 points of the rectangle from normal coordinates to cell coordinates, but nothing else. – user3386109 Aug 15 '19 at 16:03