Find a 4-point polygon enclosing scattered points

8 views (last 30 days)
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

Accepted Answer

Scott MacKenzie
Scott MacKenzie on 8 Jun 2021
Edited: Scott MacKenzie on 8 Jun 2021
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:

More Answers (1)

Matt J
Matt J on 8 Jul 2021
k=convhull(x,y);
xc=x(k); yc=y(k); %corners
  5 Comments
Scott MacKenzie
Scott MacKenzie on 9 Jul 2021
@Matt J Hey, that's great. Thanks for the follow-up and clarification.

Sign in to comment.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by