If you have not read about the failed solution for "Detection of a perfect point to start Flood fill", you should go through it once. DevLog LinkDevLog: detection-of-a-perfect-point-to-start-flood-fill-the-failed-solution.

The solution is the combination of two different algorithms and these are as follows.

1. Convex Hull(Graham scan)
   
2. A* pathfinding

The Logic:

Whenever a player wants to cover a new territory, the player has to enclose the territory by creating a boundary around it with their trail.

Once the territory is enclosed by the trail boundary, we need a perfect point to start the Filling algorithm. For this, we have to traverse through all the neighbor cells of every trail cell, where we will apply our logic to check whether the cell is perfect or not. 

Before starting to traverse through the neighbor cells we have to find the Convex Hull using the the trail boundary cells.

Step 1: Collect all the trail cells. 

Step 2: Pass the trail cells to a function called GetConvexHull, which will return the Convex-Hull cells.

Step 3: Store the convex hull cells returned by the function for further use.

Once all the above steps are done we will start traversing through the neighbor cells, and at each cell, we are going to use A* Path Finding algorithm, you must be thinking why Path-Finding, and the reason is, that we will find a path to go out of the trail boundary where our starting point will the current checking cell. If we are not able to find any path that is going out of the trail boundary from the current checking cell, it means the cell is inside the boundary, and If we find the path that is going outside of the boundary it means the cell must belong to outside the boundary. (Note: In the path-finding algorithm the path blocker is all trail cells. it means whenever a path tries to go through any trail cell it gets rejected.)

Now we can find a cell that is inside the trail boundary as all the outgoing paths were blocked by the trail boundary cells, but how will we know that we can find a path from a cell that is going outside of the boundary? Now it's the place where Convex-Hull will work.

Whenever a path is generated by checking cell-by-cell, it checks at every cell whether the cell is going out of the convex hull or not. If the path contains a cell that is going out of the convex hull, then the current checking cell from where we started to check for the outgoing path will get rejected for being a perfect cell/point to start the food fill.

For a more detailed understanding check the below attached example image of the output, which I have taken after the successful implementation of the logic.

Here you can see the coordinates ((3, 10), (6, 10), (9, 12), (12, 9), (4, 6), (6, 6)) which are colored green, are found as perfect points, because they don't have any path going out of the yellow colored trail boundary (Note: trail boundary cells are named as U/D/R/L).

Also, you can notice the red-colored neighbor coordinates which are outside of the boundary these are rejected for being a perfect point because some of them are found already outside of the Convex-hull boundary and those are not outside of the Convex-hull boundary, they do have a path to go outside of the Convex-hull. 

(Note: The yellow-colored line boundary is the Convex-hull boundary, the trail boundary is constructed by the cells denoted with U/D/R/L)