Determine whether a polyomino has a hole

Question

Suppose I know the $(x,y)$ coordinates of the corners of all the unit squares making up a connected polyomino. Is there a simple/elegant way to determine if the polyomino has a hole in it, merely by using these coordinates?

Polyomino with no holes:

Polyomino with two holes:

Note: I've already determined a solution by a process similar to the following list, but I am wondering if there is a nicer/cleverer way:

1. Find the smallest bounding rectangle (using $x_\text{min},\, x_\text{max},\, y_\text{min}\,$ and $\,y_\text{max}$).
2. Make a list of all blank squares on the perimeter of this rectangle.
3. For each blank square in this list, look up, down, left and right for more blank squares (that are inside the rectangle), adding all of these to the list.
4. Loop step 3 over this list until no new blank squares are found.
5. Sum the number of blank squares in this list with the known number of shaded squares. If this sum is less than the area of the bounding rectangle, we know there is a hole.

Is there a theorem/perspective I've overlooked that would have provided an elegant solution?

Answer 1

Try Pick's theorem: if $B$ is the number of grid points on the boundary of the polyomino, $I$ is the number of grid points in the interior, and $A$ is the number of squares, then $$A+1-I-\frac B2=H$$ where $H$ is the number of holes.

To compute $B$ and $I$, iterate over each vertex of each square. Keep a count of the number of times each point appears. If a point appears in one, two, or three of the squares, it is a boundary point. If it is on four squares, it is an interior point.

Answer 2

You can travel along the outer boundary, the boundary to the unrestricted area. You can calculate the area enclosed by this outer boundary while you are travelling along the boundary (similar to a planimeter): start with $A=0$. Add $x$ to $A$ if you go from $(x,y)$ to $(x,y-1)$ and subtract it if you go from $(x,y)$ to $(x,y+1)$. If only $x$ changes but $y$ does not, $A$ does not change. At the end of the travel $A$ is equal to the area. If this area is finally equal to the number of squares, then there are no holes. If it is larger, then there are holes. To start choose the points with the lowest $x$-coordinate $x_0$ and from these choose the one with the lowest $y$ coordinate $y_0$. This is the left lower vertex of a square. The first move is from this vertex $(x_0,y_0)$ up to $(x_0,y_0+1)$.

Answer 3

Pick's Theorem has unexpected results for some holey polyominoes. Take for example the smallest such, the holey heptomino. It is not a correct candidate for Pick's theorem, as the external boundary of the polyomino is not distinct from the boundary of the hole.
As a result, H = A + 1 - I - B/2 evaluates as 7 + 1 - 0 - 15/2 = 1/2
There is a way to fix this, counting D = vertices surrounded only by 2 squares adjacent diagonally (note that such vertices get counted twice, in both B and D).
The new formula is H = A + 1 - I + (D - B)/2.