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

Question

Kai 2018-9-6

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/417827-find-inner-points-among-a-set-of-points-on-a-regular-grid

编辑： Matt J 2018-9-6

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).