9
\$\begingroup\$

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?

enter image description here

enter image description here

Above I've drawn pictures of what I expect the 4 possible results of this test can be.

  1. The chain does not make an enclosed figure.

  2. The chain does make an enclosed figure.

  3. 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.

  4. 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.

\$\endgroup\$
  • 1
    \$\begingroup\$ What about intersecting paths like a figure-8, or pentagram? Would you assume the non-zero or the even-odd fill rule? \$\endgroup\$ – Anko Apr 21 '14 at 12:24
  • \$\begingroup\$ Case 4 could also merge with Case 3: Enclosed using sides of board, with extra information \$\endgroup\$ – ChargingPun Apr 25 '14 at 18:17
  • \$\begingroup\$ If you have a vertical line running down the center of your board from top edge to bottom, which side of the board is 'enclosed'? \$\endgroup\$ – Steven Stadnicki May 1 '14 at 18:11
  • \$\begingroup\$ I think we should assume that the smallest space is enclosed for now. Unless OP specifies otherwise. \$\endgroup\$ – Tom 'Blue' Piddock May 13 '14 at 11:55
2
\$\begingroup\$

1. Detecting a loop of tiles

The problem seems similiar to detecting a cycle (loop) in a graph, see here or here.

  • The set of nodes V of that graph G=(V, E) are the tiles,
  • an edge e = (v1, v2) exists between two different nodes, if the tiles are direct or diagonal neighbours

2. Handling the screen border case

The screen border consists of those imaginary tiles which would form a one tile wide rim around the screen of visible tiles.

According to your specification part of the screen border would form an implicit part of a closed loop. Just to detect a closed loop, it would be sufficient to extend the graph G to a graph G'by honoring the connection via this rule:

  • another edge exists between any two different nodes, if the two tiles are each positioned directly near the border of the screen

Thus tiles at (0,0) and (1,0) would be part of a closed loop, together with the "border tiles" (-1,0), (-1,-1), (0, -1), (1, -1).

3. The inner part of a looped area

I would go into a similiar direction to what user Arthur Wulf White suggested:

Limiting the set of tiles we have to examine by the bounding box of the loop tiles.

Then using a flood fill to select all tiles within the bounding box which are either exterior or interior to the closed loop. It can only be one of those two cases. Which one we have to find out afterwards.

Extending the bounding box by one tile in each direction would be a good idea as well, yielding the extbb, so we just end up with one connected set of exterior points, in case we started the flood fill with an exterior tile.

Once we have the flood fill area, we would calculate its bounding box as well, the ffbb. In case we started with an exterior tile, it should be identical to the extended loop bounding box.

ffbb == extbb

In case we started with an interior tile, it should yield a distinctly smaller bounding box, because the loop tiles have to be sandwiched in between both bounding boxes.

ffbb < extbb

The initial starting tile for the flood fill could be any tile within the extbb which is a free tile. Maybe picking one randomly is the best approach.

If I would know before that the interior is smaller than the exterior, I would start around the center of mass of the loop points which is in the interior for many areas (counter example: C shaped area), otherwise on the border of the extbb. But I have no idea how to estimate this.

Final remarks

Normaly I would say a simple walk starting from some tile and keeping a list of visited tiles would be sufficient to detect a cycle, but that screen boundary condition might yield a more complicated graph, so you should be on the safe side with a graph algorithm.

Below is an example where the interior is not connected, on the other hand the cycle detection should find two loops in that case, one should get discarded.

some cases

\$\endgroup\$
1
\$\begingroup\$

You can resolve this by:

  1. Finding the bounding box of that shape.
  2. Increasing it's size by 1 in each direction.
  3. Iterating over the frame of the new slightly enlarged bounding box and applying flood-fill.
  4. If there are any tiles that you did not mark with flood-fill that are not on that chain then they are enclosed. I suppose that by your definition if there are enclosed tiles than the shape is a closed figure.

To do one, iterate over all tiles on the chain and find their minX, minY, maxX and maxY and that is your bounding box or AABB.

Two is trivial.

Iterating over the frame is simple, just make sure not to flood-fill outside the grid. You can learn how to flood-fill in Wikipedia.

For number four you can start by only checking tiles adjacent to the chain. You could flood-fill from any tile you find that is not marked to locate more tiles.

\$\endgroup\$
0
\$\begingroup\$

Your intuition is right, assuming that the chain ends as soon as the user tries to select a tile they have already selected. In that case, the shape in general looks like a lasso, in your picture (4). If they can keep swiping, then they can draw many loops, and things get more complicated. What you want to do is answer the points-in-polygon question.

First, we need to define the problem. I am going to assume that the situation looks like (2), i.e. any tail has been stripped off, and the end connects back to the start, so that each tile has exactly one "predecessor" and exactly one "successor" in the chain (where the predecessor of the successor of tile X is always tile X). Further, if you follow "successors" for long enough, you eventually get back to where you started. You can use Gurgadurgen's suggestion to detect whether the loop actually crosses back on itself at any point. Assuming you end the user's input when it does, it will look like some series of nodes in a line, followed by a loop. You can strip the line off the get the loop.

Now we, for each row do the following:

  1. Start at the left edge, and keep track of a boolean for each tile which tells whether we are IN or OUT. Start OUT.
  2. If the current tile is part of the chain, look at both the successor and the predecessor (which must be adjacent). If either is strictly above (i.e. north, north east, or north west of the current tile), set the current tile's state to the opposite of the tile to its left. Otherwise, set it to the same as the tile to the left. Goto 4.
  3. If the current tile is not part of the chain, set the tile to the state of the title to its left. Goto 4.
  4. The tile one to the right is now the current tile. Goto 2.

Now take all the tiles which are IN, add in the tiles on the border (including a tail if you stripped it earlier or not, your choice), and call that the region.

If you want to allow the user to use borders, remember that this does not define and IN/OUT on the board, but just divides it into two parts. You could select the smaller region, for example, or require the user to use two adjacent sides (i.e., the left and bottom, but not either top/bottom or left/right).

An optimization is that you only need to do rows which have any border in them (if you can't use the sides). I assume that your board is small enough that iterating over every tile and doing a very simple computation is not an issue, even on the weakest mobile system. (You do have to render them, after all, which is far more complex of a task).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.