Find a 4-point polygon enclosing scattered points

20 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];
ax = gca;
ax.XTick = 0:12;
ax.YTick = -2:12;
hold on;
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)]);
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
xc=x(k); yc=y(k); %corners
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.


Find more on Elementary Polygons in Help Center and File Exchange

Community Treasure Hunt

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

Start Hunting!

Translated by