Rotating Rectangle Rasterization Algorithm

Question

In a nutshell: I want to make not an approximate version of the linear Bresenham algorithm, but for a rectangle, not a line, and the points of which do not necessarily coincide with the grid.

Given a square grid and a rectangle of four points not connected to the grid, I want to find a list of all the grid squares that are partially or fully covered by the rectangle.

The Breshenem line algorithm is approximate - not all partially covered squares are identified. I am looking for a “perfect” algorithm that has no false positives or negatives.

Answer 1

This is an old question, but I solved this problem (C ++)

https://github.com/feelinfine/tracer

Maybe it will be useful for someone

(sorry for my bad english)

Single line trace

template <typename PointType> std::set<V2i> trace_line(const PointType& _start_point, const PointType& _end_point, size_t _cell_size) { auto point_to_grid_fnc = [_cell_size](const auto& _point) { return V2i(std::floor((double)_point.x / _cell_size), std::floor((double)_point.y / _cell_size)); }; V2i start_cell = point_to_grid_fnc(_start_point); V2i last_cell = point_to_grid_fnc(_end_point); PointType direction = _end_point - _start_point; //Moving direction (cells) int step_x = (direction.x >= 0) ? 1 : -1; int step_y = (direction.y >= 0) ? 1 : -1; //Normalize vector double hypot = std::hypot(direction.x, direction.y); V2d norm_direction(direction.x / hypot, direction.y / hypot); //Distance to the nearest square side double near_x = (step_x >= 0) ? (start_cell.x + 1)*_cell_size - _start_point.x : _start_point.x - (start_cell.x*_cell_size); double near_y = (step_y >= 0) ? (start_cell.y + 1)*_cell_size - _start_point.y : _start_point.y - (start_cell.y*_cell_size); //How far along the ray we must move to cross the first vertical (ray_step_to_vside) / or horizontal (ray_step_to_hside) grid line double ray_step_to_vside = (norm_direction.x != 0) ? near_x / norm_direction.x : std::numeric_limits<double>::max(); double ray_step_to_hside = (norm_direction.y != 0) ? near_y / norm_direction.y : std::numeric_limits<double>::max(); //How far along the ray we must move for horizontal (dx)/ or vertical (dy) component of such movement to equal the cell size double dx = (norm_direction.x != 0) ? _cell_size / norm_direction.x : std::numeric_limits<double>::max(); double dy = (norm_direction.y != 0) ? _cell_size / norm_direction.y : std::numeric_limits<double>::max(); //Tracing loop std::set<V2i> cells; cells.insert(start_cell); V2i current_cell = start_cell; size_t grid_bound_x = std::abs(last_cell.x - start_cell.x); size_t grid_bound_y = std::abs(last_cell.y - start_cell.y); size_t counter = 0; while (counter != (grid_bound_x + grid_bound_y)) { if (std::abs(ray_step_to_vside) < std::abs(ray_step_to_hside)) { ray_step_to_vside = ray_step_to_vside + dx; //to the next vertical grid line current_cell.x = current_cell.x + step_x; } else { ray_step_to_hside = ray_step_to_hside + dy;//to the next horizontal grid line current_cell.y = current_cell.y + step_y; } ++counter; cells.insert(current_cell); }; return cells; } 

Get all cells

 template <typename Container> std::set<V2i> pick_cells(Container&& _points, size_t _cell_size) { if (_points.size() < 2 || _cell_size <= 0) return std::set<V2i>(); Container points = std::forward<Container>(_points); auto add_to_set = [](auto& _set, const auto& _to_append) { _set.insert(std::cbegin(_to_append), std::cend(_to_append)); }; //Outline std::set<V2i> cells; /* for (auto it = std::begin(_points); it != std::prev(std::end(_points)); ++it) add_to_set(cells, trace_line(*it, *std::next(it), _cell_size)); add_to_set(cells, trace_line(_points.back(), _points.front(), _cell_size)); */ //Maybe this code works faster std::vector<std::future<std::set<V2i> > > results; using PointType = decltype(points.cbegin())::value_type; for (auto it = points.cbegin(); it != std::prev(points.cend()); ++it) results.push_back(std::async(trace_line<PointType>, *it, *std::next(it), _cell_size)); results.push_back(std::async(trace_line<PointType>, points.back(), points.front(), _cell_size)); for (auto& it : results) add_to_set(cells, it.get()); //Inner std::set<V2i> to_add; int last_x = cells.begin()->x; int counter = cells.begin()->y; for (auto& it : cells) { if (last_x != it.x) { counter = it.y; last_x = it.x; } if (it.y > counter) { for (int i = counter; i < it.y; ++i) to_add.insert(V2i(it.x, i)); } ++counter; } add_to_set(cells, to_add); return cells; } 

Types

 template <typename _T> struct V2 { _T x, y; V2(_T _x = 0, _T _y = 0) : x(_x), y(_y) { }; V2 operator-(const V2& _rhs) const { return V2(x - _rhs.x, y - _rhs.y); } bool operator==(const V2& _rhs) const { return (x == _rhs.x) && (y == _rhs.y); } //for std::set sorting bool operator<(const V2& _rhs) const { return (x == _rhs.x) ? (y < _rhs.y) : (x < _rhs.x); } }; using V2d = V2<double>; using V2i = V2<int>; 

Using

 std::vector<V2d> points = { {200, 200}, {400, 400}, {500,100} }; size_t cell_size = 30; auto cells = pick_cells(points, cell_size); for (auto& it : cells) ... //do something with cells 

Answer 2

This is not optimal, but can give a general idea.

First, consider the special case where the rectangle is aligned horizontally or vertically separately. It is quite easy to check and make everything simpler.

You can imagine a rectangle as a set of 4 inequalities a1 x + b1 y >= c1 a1 x + b1 y <= c2 a3 x + b3 y >= c3 a3 x + b3 y <= c4 , since the edges of the rectangles are parallel, some of the constants are the same. You also have (up to a few) a3=b1 and b3=-a1 . You can multiply each inequality by a common factor to work with integers.

Now consider each scan line with a fixed y value. For each y value, find the four points where the lines intersect the scan line. This is to find a solution with each line above. A bit of logic will find the minimum and maximum values ​​of x. Select all the pixels between these values.

Are you sure you want all the partially covered squares to make things a little more complicated. You can solve this by looking at two adjacent scan lines. You want to plot points between the minimum x for both lines and the maximum for both lines. Speaking a1 x+b1 y>=c , this is an inequality for the lower left line in the figure. You want to find the largest value of x so that a1 x + b1 y < c it will be floor((c-b1 y)/a1) call it minx(y) also find minx(y+1) and the left point will be the minimum of these two values.

There is a lot of simple optimization where you can find the y values ​​of the upper and lower angles, reducing the range of y values ​​for testing. You only need to check two sides. For each endpoint of each line, there is one multiplication, one subtraction, and one division. Partitioning is the slowest part, which I think about 4 times slower than other operating systems. You may be able to remove this using the Bresenham or DDA algorithms others have talked about.

Answer 3

You can use the scanline approach. A rectangle is a closed convex polygon, so it is enough to save the leftmost and rightmost pixel for each horizontal scan line. (Both the top and bottom scan lines, too.)

The Breshenem algorithm tries to draw a thin, visually pleasing line without adjacent cells in a smaller size. We need an algorithm that visits every cell through which the edges of the polygon pass. The basic idea is to find the starting cell (x, y) for each edge, and then adjust x whenever the edge crosses the vertical border and adjust y when it crosses the horizontal border.

We can represent the intersections using the normalized coordinate s , which moves along the edge and is equal to 0.0 in the first node n1 and 1.0 in the second node n2 .

  var x = Math.floor(n1.x / cellsize); var y = Math.floor(n1.y / cellsize); var s = 0; 

Vertical intrusions can be represented as equidistant stages with dsx from the initial sx .

  var dx = n2.x - n1.x; var sx = 10; // default value > 1.0 // first intersection if (dx < 0) sx = (cellsize * x - n1.x) / dx; if (dx > 0) sx = (cellsize * (x + 1) - n1.x) / dx; var dsx = (dx != 0) ? grid / Math.abs(dx) : 0; 

Similarly for horizontal intersections. A default value greater than 1.0 captures cases of horizontal and vertical lines. Add the first point to the scan line data:

  add(scan, x, y); 

Then we can visit the next neighboring cell by looking at the next intersection with the smallest s .

  while (sx <= 1 || sy <= 1) { if (sx < sy) { sx += dsx; if (dx > 0) x++; else x--; } else { sy += dsy; if (dy > 0) y++; else y--; } add(scan, x, y); } 

Do this for all four edges and with the same scan line data. Then fill in all the cells:

  for (var y in scan) { var x = scan[y].min; var xend = scan[y].max + 1; while (x < xend) { // do something with cell (x, y) x++; } } 

(I just looked at the links provided by MBo. It seems that the approach presented in this article is essentially the same as mine. If so, please excuse the unnecessary answer, but after that I decided it.)

Answer 4

There is an Amanatides and Woo method for listing all intersecting cells. A quick Voxel traversal algorithm for ray tracing .
Here is a practical implementation.
As a side effect for you - you get intersection points with grid lines - this can be useful if you need areas of partially covered cells (for smoothing, etc.).