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