Find a 4-point polygon enclosing scattered points

I have a set of scattered points (x,y) as in the attached figure and I want to find the polygon defined only by 4 points that encloses those scattered points. Those 4 points will belong to the original set of (x,y) points because they are quite regularly spaced as in the figure. How could I find the vertices of the shape? thanks

Answer 1

[Scott MacKenzie]

No doubt this can be simplified, but I think it meets your objective of finding the vertices (4) enclosing the points:

% create sample of regularly-spaced points, as per question
g = 0:0.1:1;
x = [];
y = [];
for i=1:10
    x = [x i+g];
    y = [y i-g];
end

ax = gca;
ax.XTick = 0:12;
ax.YTick = -2:12;
hold on;
plot(x,y,'.');

k = boundary(x',y');

[~, xMinIdx] = min(x(k));
[~, xMaxIdx] = max(x(k));
[~, yMinIdx] = min(y(k));
[~, yMaxIdx] = max(y(k));
xx = x(k);
yy = y(k);

p = polyshape([xx(xMinIdx) xx(yMinIdx) xx(xMaxIdx) xx(yMaxIdx)], ...
    [yy(xMinIdx) yy(yMinIdx) yy(xMaxIdx) yy(yMaxIdx)]);
plot(p);

v = p.Vertices % output vertices (4)

Command window output:

v =

1 1

10 10

11 9

2 0

Figure window:

[Albert]

It works perfectly!! Thanks ;)

Answer 2

[Matt J]

k=convhull(x,y);

xc=x(k); yc=y(k); %corners

[Albert]

easy one! thanks!!

[Scott MacKenzie]

@Matt J: Wow, nice. Must confess, I've never used the convhull function. However, with the x and y test data I used in my answer, convhull yields 32 "corners". That's the sizes for xc and yc. But, there should only be 4 corners. Am I missing something?

[Matt J]

@Scott MacKenzieFloating point errors can make (x,y) points along the boundary look slightly non-colinear with the four "true" corners. Therefore, as far as convhull can see, it is a 32-sided polygon. Basically, to make this approach robust, you need to post process the results and weed out approximately colinear points. But, at least convhull will give you the boundary points in sequential order and help you discard points that are substantially interior to the polygon...

[Matt J]

@Scott MacKenzie similar to your solution, polyshape is a pretty good tool for weeding out the non-vertex boundary points that convhull() doesn't manage to find:

g = 0:0.1:1;
x = [];
y = [];
for i=1:10
    x = [x i+g];
    y = [y i-g];
end

k=convhull(x,y);
p=polyshape(x(k),y(k));

Warning: Polyshape has duplicate vertices, intersections, or other inconsistencies that may produce inaccurate or unexpected results. Input data has been modified to create a well-defined polyshape.

v=p.Vertices

v = 4×2

1 1 10 10 11 9 2 0

[Scott MacKenzie]

@Matt J Hey, that's great. Thanks for the follow-up and clarification.