3

I'm trying to work out which tiles a rectangle overlaps. Right now I'm just taking the mix/max bounds of the rect, and iterating through the grid tiles that are within those bounds. And for each tile I check whether the tile rectangle intersects with the other rectangle. This isn't very performant as I still have to iterate a lot of tiles and do a lot of intersection checks.

I'm wondering if theres a more performant or mathematical way to achieve this.

enter image description here

user23432432
  • 125
  • 2
  • 8

1 Answers1

1

Sort rectangle vertices by Y-coordinate and treat horizontal bands between vertice Y-positions separately (it is possible to get 1, 2 or 3 bands).

For every Y-interval you have left and right sides, walk through them using Bresenham algorithm (for pixels) or Amanatides-Woo algorithm (for cells/voxels).

For every horizontal you have the leftmost and the rightmost cell, fill also all cells between them.

Also look for triangle rasterization algorithms for more ideas.

MBo
  • 77,366
  • 5
  • 53
  • 86