Finding point inside enclosed area

Question

I have xy grid, where points have whole-numbered, positive coordinates. These points are "neighbours" if both their x and y coordinates differ by less than 2 - they are simply next to each other.

In this grid, I have found path that encloses some area. Every point in the path is neighbour to the previous point and the next point, so it is sorted like you walked around the enclosed area. It is also shortest path around that enclosed area, so there are no steps back and forth. The enclosed area does not need to be convex, so when you connect two random points on the path with one line, that line can lie completely out of that area.

The problem is, I need to find at least one point in enclosed area, that is neighbour to any point in enclosing path.

It might sound easy, but I have not found solid algorithm to determine it.

* I'm sorry, I did not explain that well enough. There are no "empty parts" in enclosed area. If there are three points in enclosed area, the path around is the smallest path that captures those three points. In this picture, red path is shortest, black is too long and I never need to detect those.

Answer 1

Observations to check that I understand the question:

• It's possible that there are no such interior points.
• Given that consecutive path point are neighbors, the connection angles will be at multiples of 45°.

The basic idea is to walk the path and keep track of interior and exterior neighbors.

To determine which side is the interior, walk the path and keep track of the cumulative turn angle. The final amount will be 360° or -360° which will indicate the interior is on the left or the right, depending on which way you defined positive and negative angles.

During that first pass, also collect a hash set of the points on the path, onPathPoints.

1. Initialize two other hash sets to empty: exteriorPoints and possibleInteriorPoints.
2. Walk the path and for each point:
   • a. categorize the 8 neighbors as on-path, interior-side or exterior-side based on the relative positions of the previous and next points on the path.
   • b. for each point in onPathPoints, ignore it.
   • c. for any point on the interior side and distance 1 away, return that point as the result.
   • d. for each points on the interior side with distance > 1 (diagonal neighbor), add it to possibleInteriorPoints.
   • e. for each point on the exterior side and distance 1 away, add it to exteriorPoints.
3. At the end of the walk, remove from possibleInteriorPoints any point in exteriorPoints (set subtraction). Return any point remaining in possibleInteriorPoints as an interior point.
4. Otherwise, there are no interior points.

The possibleInteriorPoints represent diagonally neighboring points that are in the interior unless the path loops back between the original point and it (in which case it will be an exterior point to the new path part.

For example in the image below, when visiting (2,2) and going toward (3,3) the interior is on the right. (3,1) is a possible interior point, but later in the walk while visiting (4,1), (3,1) is noted to be an exterior point and so would get removed from possibleInteriorPoints.

Technically, in this example the algorithm would have stopped when visiting (4,3) and noting (4,2) as an interior point at distance 1.