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?

Karel de Boer
  • 38
  • 4

2 Answers2

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.

Bitwise
  • 7,577
  • 6
  • 33
  • 50
  • This will leave me exactly where I am already: having all the edges (combo's of two vertexes) of the path, but in a random order. Please note that the order is important. Or do I not see your solution correct? – Karel de Boer Apr 10 '13 at 15:08
  • @KareldeBoer this shouldn't a problem if you represent the graph correctly, e.g. each node points to its neighboring nodes. – Bitwise Apr 10 '13 at 15:29
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.

Tianyun Ling
  • 1,045
  • 1
  • 9
  • 24
  • This seems like a good approach. Thanks :) PS For anyone trying this; make sure you remove points from your grid that are closed in. Iow, remove points that are surrounded by four tiles before you start your logic. I will post a pseudo solution a little bit later today here. Tnx Tianyun :) – Karel de Boer Apr 18 '13 at 09:02
  • Pseudo solution. See: http://img825.imageshack.us/img825/2194/outlinepathfinding.png 1) We want the outline of this tilegrid, as a path 2) Find all vertexes 3) Remove vertexes that connect 4 tiles with each other 4) Start in top left; add it to your path 5) Now do as Tianyun said :) (only add a vertex to your path when it's not on the path already, of course. GL. Tnx all :) – Karel de Boer Apr 18 '13 at 09:15