1

Problem (psuedo) How to find the outline of a set of tiles? Let's assume we have three tiles, at the x/y coordinates A[20,20], B[20,30] and C[30,30] (this will make a simple L-shape). Those points represent the centers of the tiles. Each tile has 4 vertexes: TL (top left), TR, BL (bottom left) and BR. Together, the 3 tiles have 8 unique (non-overlapping) vertexes.

We want the red line (path), defined by green dots (vertexes): http://img7.imageshack.us/img7/2469/lshapetiles.png

Needed solution The output of the algorithm should be a path that forms the outline shape of the tiles, consisting out of these vertexes - in this order: A TL, A TR, A BR, C TR, C BR, C BL, B BL, B TL (and optional, A TL again, to close). See the red line.

Possible solution(s) One option is to iterate over all the tiles, and for each tile check: + does it have a neighbor above? If not, at TL and TR to path + does it have a neighbor on the right? If not, at TR and BR to path + does it have a neighbor underneath? If not, at BL and BR to path + does it have a neighbor on the left? If not, at TL and BL to path

If you only add the found vertexes to the path if they're not added already yet, you've succesfully collected the unique vertexes for the path. However, they might be in the wrong order. This is a (the) problem.

Does someone know of a good solution (algorithm) for this?

4

2 回答 2

1

You can try something like this:

You iteratively build a graph representing the tiles, except for a small change -when an edge is doubled, you remove it.

So you add the first tile to the graph G, all its edges will be added. For the next tile, you add all its edges to G, but if any of its edges overlap with an edge in G, you remove that edge from G. You continue this process for all tiles.

At the end, you will only be left with "outside" edges, so you just traverse the path you have left.

于 2013-04-10T15:00:11.903 回答
1

First, build a data structure to represent the tile structure.

Algorithm: 1 find the top-left point. 2 start from this point, iteratively find the next point by using the up, right,down,left order (in the data structure, each point contains these 4 links) 3 stop when go back the initial point.

if the graph contains separated structures, run the above algorithm for each connected component.

于 2013-04-10T15:08:39.940 回答