# Expand polygon to grid in $x-y$ plane

Given a polygon in the $x-y$ plane, what is the simplest formula for expanding the polygon so that all sides lie on a grid?

The image below demonstrates the problem I am trying to solve. The filled in line is the original polygon, while the outer line shows the expected outcome.

Fill - Original shape. Line - desired shape My best idea so far is something along these lines:

$1$. Pick a starting point (let's say $A$ in the image)

$2.$ Snap this point to the grid ($AA$ in the image - I'm not sure how to do this exactly)

$3.$ Determine which is the longer direction between $AB$ (here, it's the $y$ direction)

$4.$ Calculate when the $Y$ direction intersects the $Y$ axis at point $AA$. Mark point $BB$ in the grid BELOW this.

$5.$ ... And that's why I'm asking for help....

I'm coming at this from a programming perspective, but I think a math perspective will produce much better results.

• I found a programming solution and posted it below, but am still interested if anyone has a "math" solution. It seems there must be some sort of formula involving slope... – Anika Halota Feb 8 '16 at 16:57

## 3 Answers

The simplest (not necessarily the fastest...) way could be finding all grid cells intersected by the polygon's edges, plus all internal cells, then finding an outline of the set.

First off, I think you'll get more useful answers to this in computer graphics programming circles. What's simple geometrically doesn't necessarily translate into computationally simple.

That said, the question as asked is fairly straightforward geometrically. Start from a vertex of the polygon (btw, I assume you meant a convex polygon, though it's not explicitly stated) and "mark" all vertices of its enclosing grid cell which are outside the polygon (the "marked" points on the grid are the fat blue dots on the drawing below). Continue along the edge to the next vertex and, for each grid cell that it crosses, again mark all cell vertices that fall outside the polygon. Repeat until you return to the starting vertex. Run a second iteration, and connect each marked dot to the nearest not-yet-connected one for which the connecting segment doesn't intersect the polygon. Below is the outcome for the very simple case of a certain triangle. This algorithm is certainly wasteful, very far from optimal. For example, grid points may be redundantly marked multiple times e.g. the red dot is marked 3 times. Cleverer shortcuts could be devised, but that's a matter of computation rather than geometry.

One other thing that this particular triangle example shows is that the idea you put forward doesn't work in all cases. Your step $2$ snaps a vertex of the polygon to one point on the grid, but in cases like the bottom-left corner above, where a grid cell is crossed over one single side, you need at least one additional anchor point on the grid to run around it.

To find the perimeter grid cells, you are building a supercover line. This page describes one solution, the Bresenham-based supercover line algorithm.

A computational solution is shown on this stackoverflow post: Supercover DDA algorithm

Once the perimeter is found, find the internal cells by including all cells between perimeter cells along each row in any one axis.