Efficient Algorithm for the boundary of a set of tiles

Question

I have a grid of tiles of a known finite size that forms a map. Some of the tiles inside the map are put into a set known as a territory. This territory is connected, but nothing is known about its shape. Most of the time it would be a fairly regular blob, but it could be very elongated in one direction, and it could potentially even have holes. I am interested in finding the (outer) border of the territory.

That is, I want a list of all the tiles that touch one of the tiles in the territory without itself being in the territory. What is an efficient way of finding this?

For extra difficulty, it happens that my tiles are hexes, but I suspect this doesn't make too much difference, each tile is still labelled with an integer x and y coordinate and, given a tile, I can easily find its neighbors. Below are a few examples: The black is the territory, and the blue the border I want to find. This in itself, is not a difficult problem, One simple algorithm for this, in pseudo-python, is:

def find_border_of_territory(territory):
    border = []
    for tile in territory:
        for neighbor in tile.neighbors():
            if neighbor not in territory and neighbor not in border:
                border.add(neighbor)

However this is slow and I would like something better. I have an O(n) loop over the territory, another loop (a short one, but still) over all the neighbors, and then I have to check membership over two lists, one of which is of size n. That gives an awful scaling of O(n^2). I can reduce that to O(n) by using sets instead of lists for border and territory so that membership is fast to check, but it still isn't great. I expect there to be many cases where the territory is large but the border is small due to a simple area vs line scaling. For example if the territory is a hex of radius 5, it is of size 91 but the border is only of size 36.

Can anyone propose something better?

Edit:

To answer some of the questions below. The territory can range in size, from about 20 to 100 or so. The set of tiles forming the territory is an attribute of an object, and it's this object that needs a set of all the border tiles.

Initially the territory is created as a block, and then mostly gains tiles one by one. In this case, it is true that the fastest way is just to keep a set of the border and only update it on the tile that is gained. Occasionally a big change to the territory might happen - so it will need to be recalculated fully then.

I'm now of the opinion that doing a simple border-finding algorithm is the best solution. The only additional complexity this raises is to ensure that the border is recalculated every single time it might need to be, but not more than that. I'm pretty confident that this can be done reliably in my current framework.

As for timing, in my current code I have some routines that need to check every tile of the territory . Not every turn, but on creation and occasionally afterwards. That takes over 50% of the running time of my suit of test code even though it is a very small part of the complete program. I was therefore keen to minimise any repeats. HOWEVER, the test code involves a lot more object creation than a normal running of the program (naturally), so I realise this might not be very relevant.

Answer 1

Finding an algorithm is usually best done with a data structure that makes the algorithm easy.

In this case, your territory.

The territory should be an unordered (O(1) hash) set of borders and elements.

Whenever you add an element to the territory, you iterate over adjacent tiles and see if they should be a border tile; in this case, they are a border tile if they are not an element tile.

Whenever you subtract an element from the territory, you ensure that its adjacent tiles are still in the territory, and you see if yourself should become a border tile. If you need this to be fast, have the border tiles keep track of their "adjacent count".

This takes O(1) work whenever you add or remove a tile to or from a territory. Visiting the border takes O(border length). So long as you want to know "what the border is" significantly more often than you add/remove elements from the territory, this should win.

Answer 2

If you need to find edges of holes in the middle of your territory too, then your linear in the area of the territory bound is the best we can do. Any tile on the interior could potentially be a hole that we need to count, so we need to look at every tile in the area bounded by the territory's outline at least once to be sure we've found all the holes.

But if you're only concerned with finding the outer border (not interior holes), then we can do this a bit more efficiently:

1. Find one edge separating your territory. You can do this by...

   • (if you know at least one territory tile, and know that you have exactly one connected territory blob on your map)

     ...beginning at an arbitrary tile in your territory, and moving toward the closest edge of your map. As you do so, remember the last edge where you transitioned from a territory tile to a non-territory tile. Once you hit the edge of the map, this remembered edge is your starting edge.

     This scan is linear in the diameter of the map.

   • or (if you don't know where any of your territory tiles are in advance, or your map may contain several disconnected territories)

     ...beginning at an edge of your map, scan along each row until you hit a terrain tile. The last edge you crossed from non-terrain to terrain is your starting edge.

     This scan could be at worst linear in the area of the map (quadratic in its diameter), but if you have any bounds to constrain your search (say, you know the territory almost always crosses the middle rows) you can improve this worst-case behaviour.

2. Beginning at your starting edge found in step 1, follow it around the perimeter of your terrain, adding each non-terrain tile on the outside to your border collection, until you return back to the starting edge.

   This edge-following step is linear in the perimeter of your terrain outline, rather than its area. The downside is that the code is more complicated because you need to account for each kind of turn the edge can take, and avoid double-counting border tiles at inlets.

If your examples are representative of your real data size to within a couple orders of magnitude, then myself I'd go for the naive area search - it will still be blazingly fast on such a small number of tiles, and is substantially simpler to write, understand, and maintain (typically leading to fewer bugs!)

Answer 3

Notice: Whether or not a tile is on the boundary only depends on it and its neighbors.

Because of that:

• It is easy to run this query lazily. For instance: You do not need to search for the boundary on the whole map, only on what is visible.

• It is easy to run this query in parallel. In fact, I could image some shader code that does this. And if you need it for something other that visualization, you can render to a texture and use that.

• If a tile changes, the boundary only changes locally, which means you do not need to compute the whole thing again.

You can also pre compute the boundary. That is, if you are populating the hex, you can decide if a tile is boundary at that moment. That means that:

• If you use a loop to populate the grid, and it is the same you use to decide what is a boundary.
• If you start with an empty grid and pick tiles to change, then you can update the boundary locally.

---

Do not use a list for the boundary. Use a set if you really have to (I do not know what do you want the boundary for.). However, if you make whatever a tile is boundary or not an attribute of the tile then you do not have to go to another data structure to check.

Answer 4

Move your area up one tile, then up-right, then down right, etc.. Afterwards remove the original area.

Merging all six sets should be O(n), sorting O(n.log(n)), set difference O(n). If the original tiles are stored in some sorted format, the merged set can be sorted in O(n) too.

I don't think there is an algorithm with less than O(n), since you need to access each tile at least once.

Answer 5

I just wrote a blog post about how to do this. This uses the first method that @DMGregory mentioned starting with an edge cell and marching around the perimeter. It's in C# instead of Python but should be pretty easy to adapt.

https://dillonshook.com/hex-city-borders/

Answer 6

ORIGINAL POST :

I can't comment on this site so I'll try to answer with a pseudocode algorithm.

You know every single territory has at most six neighbors that are part of the boundary. For every tile in the territory, add the six neighboring tiles to a potential border list. Then subtract every tile in the territory from the border and you are left with only the border tiles. It will work best if you use an unordered set to store each list. Hope I was helpful.

EDIT There are much more effective ways than simple iteration. As I tried to state in my (now deleted) answer below, you can achieve O(1) in the best cases and O(n) in the worst case.

Adding a tile to a territory O(1) - O(N) :

In the case of no neighbors, you simply create a new territory.

In the case of one neighbor you add the new tile to the existing territory.

In the case of 5 or 6 neighbors you know it is all connected, so you add the new tile to the existing territory. These are all O(1) operations, and updating the new border territories is O(1) as well, since it is a simple merge of one set with another.

In the case of 2, 3, or 4 neighboring territories you may have to merge up to 3 unique territories. This is O(N) on combined territory size.

Removing a tile from a territory O(1) - O(N) :

With zero neighbors erase the territory. O(1)

With one neighbor remove the tile from the territory. O(1)

With two or more neighbors, up to 3 new territories may be created. This is O(N).

I spent my spare time over the last few weeks developing a demonstration program that is a simple hex based territory game. Try to raise your income by placing territories next to each other. 3 players, Red, Green, and Blue compete to generate the most revenue by strategically placing tiles on a limited game field.

You can download the game here (in .7z format) hex.7z

Simple mouse control LMB places a tile (can only place where highlighted with hover). Score on top, income on bottom. See if you can come up with an effective strategy.

Code can be found here :

Eagle/EagleTest

To build from source code you need Eagle and Allegro 5. Both build with cmake. Hex game builds with CB project currently.

Turn those downvotes upside down. :)