CODEWITHSUNDEEP
mathcollisionshapesbounds
user23432432
user23432432

Reputation: 125

Is there a performant/mathematical way to find which tiles on a grid that a rotated rectangle overlaps?

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

Upvotes: 3

Views: 694

Answers (1)

MBo
MBo

Reputation: 80287

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.

Upvotes: 1

Related Questions