Determine whether a polyomino has a hole
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:
- Find the smallest bounding rectangle (using $x_\text{min},\, x_\text{max},\, y_\text{min}\,$ and $\,y_\text{max}$).
- Make a list of all blank squares on the perimeter of this rectangle.
- 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.
- Loop step 3 over this list until no new blank squares are found.
- 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?
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.