Given a set of tiles on a grid, I want to determine:
- If the tiles make an enclosed figure
- If the tiles make an enclosed figure when you count the sides of the board as an edge of the figure
- If either of the previous two statements are true, which additional tiles fall inside the enclosed figure the initial tiles form.
The player will begin by pressing down on one tile, then dragging their finger to other tiles to create a chain of same-colored tiles. I will check as I go to see if the next tile is valid. Ex. If the player begins on a red tile, their only next valid move is to an adjacent red tile (diagonals do count). When the user lifts their finger, I need to be able to check for the 3 items above.
So my initial thought was that, since I was checking for the validity of the chain each time I went, when the player lifted their finger I could check if the first and last tiles were adjacent. (I already know they're the same color.) If they were adjacent I had a hunch that I'd made an enclosed figure, and I was going to come here to try and see if I was missing something big, and to get some kind of logical/mathematical proof that my hunch was correct (or an example proving it incorrect.)
But that's when I thought of item number 2: I also have to account for chains which use an edge of the board as a side of the enclosed figure. In that case, the first and last items in the chain would not be adjacent, but I would still have an enclosed figure. So now I'm back to square one, a bit.
What can I do with this chain of grid coordinates to figure out if they make an enclosed figure or not? And once I do know I have an enclosed figure, what's the best way to get an additional list of all tiles that fall inside its bounds?
Above I've drawn pictures of what I expect the 4 possible results of this test can be.
The chain does not make an enclosed figure.
The chain does make an enclosed figure.
If you count the sides of the board as an edge (or more than one edge) of the figure, the chain does make an enclosed figure.
The chain does make an enclosed figure, but there are extra data points (validly selected by the user as part of the chain) which are not a part of the figure that is created.
Case 4 is the trickiest, because you'd have to extract the "extra" chain links to find the enclosed figure and the pieces that fall inside it (but not around the "unenclosed" area).
So... Anyone have an idea of a good way to solve this, or just a starting point for me? I'm kind of going in circles at this point and could use another set of eyes.