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
.
- Initialize two other hash sets to empty:
exteriorPoints
andpossibleInteriorPoints
. - 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
.
- At the end of the walk, remove from
possibleInteriorPoints
any point inexteriorPoints
(set subtraction). Return any point remaining inpossibleInteriorPoints
as an interior point. - 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.