Find inner points among a set of points on a regular grid

I am dealing with the following problem:

Given a two-dimensional regular grid G = [a*h:h:b*h]x[c*h:h:d*h] and a subset S of G (i.e. a collection of knots on G), find the elements of S which lie on the inner of a 4x4 region of points of S.

In my situation, S usually looks like an "island" of points, and I am trying to select the points which do not lie on the coast, so to say. You could also think of a chess board with many kings placed and you want to find those kings which are unable to move (I know, "many kings" is a little imaginary). A 3x3 region as a selection criterion would be right for this situation actually, but it could lead to "one-dimensional lines" of inner points, which is not what I want (since I am actually interested in the regions between four inner points).

I made some straightforward implementation: When considering a point P, I run four loops which check whether P is the (2,2), (2,3), (3,2) or (3,3) position of such a 4x4 region respectively. Inside such a loop, for all other 15 positions of the 4x4 regions I check if S contains a point at this position. If there exist points at all 15 positions, the point P is marked as an inner point and I end the loops using the break command.

The implementation works, however it is quite costly. In my overall program, I have several such subsets S, and I would like to work with grids as fine as possible (resulting in large sets S). Checking 15 positions as above means running the isempty command 15 times, and the input for this command consists of four inequations each time (checking both coordinates seperately and using some eps tolerance bound, since sometimes there are rounding issues), each inequation being checked for every element of S.

I am wondering if there is some more elegant and quicker way to solve the problem, without spending weeks of defining some efficient searching algorithm or so. Perhaps there is even some Matlab function which I can use but haven't thought of (I searched using some keywords, but did not find anything useful).

Answer 1

[KSSV]

Read about inpolygon.

[Kai]

I'm not given a polygon. I am given a set of points S. I also can use a graph G which contains the points of S as nodes and edges between horizontally or vertically adjacent points. I thought about using this graph, but in either way it doesn't solve the problem. Also using the graph to define a polygon (e.g. choose the vertices with less than four neighbors) doesn't help. There can be vertices with four neighbors which are not inner points. Also there seems to be no way that this will lead to 4x4 and not 3x3 regions (inpolygon will at most find the points inside a 3x3 region).

[Kai]

One idea would be to modify the above graph and set up edges between diagonally adjacent points. Then first check if a vertex has 8 neighbors, if true check if the left, upper and left-upper neighbor all have 8 neighbors as well. That would mean that the point lies within a 4x4 region. Similarly check the other three directions. I can try that later, but it might be costly and not that elegant I think.

[KSSV]

Try knnsearch or rangesearch

[Kai]

Hmm, rangesearch could be an idea. I will try that, thank you!

Answer 2

[Matt J]

Make a binary map BW of S and use imerode,

[I,J]=find( imerode(BW,ones(4));