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 ...
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.
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 ...
Assuming you have Hex objects stored in a 2d array, just make each Hex own some of its edges and vertices. For example, have each hex own the edges with arrows pointing to them as well as the two vertices between those edges:
/ \ <3
We only store three edges and two vertices, so where do the others come from? Well, continuing ...
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 ...
The height of each individual hexagon is 84px including shadow but the shadow only matters for the last row. So we need to know the size without shadows. I believe the height of the hexagon without shadow is 73px.
For all rows except the last row, there is overlap in heights by 1/4 of the hexagon height. The second row starts at 3/4 of the hexagon height. (...
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.
In case anyone needs it, here's the C# implementation of Patel's algorithm:
IEnumerable<Hex> GetRange(Hex center, int range)
var inRange = new List<Hex>();
for (int q = -range; q <= range; q++)
int r1 = Math.Max(-range, -q - range);
int r2 = Math.Min(range, -q + range);