MATLAB Answers

Does anyone know why it is also taking point 9 as convex hull point eventhough it shouldn't?

2 views (last 30 days)
Does anyone know why it is also taking point 9 as convex hull point eventhough it shouldn't?
Image representing the cloud of points and it's convex hull
Input
clear;
close all;
clc;
xy = [
3 12 % Point 1
10 8 % Point 2
11 14 % Point 3
13 16 % Point 4
9 19 % Point 5
1 15 % Point 6
2 5 % Point 7
6 1 % Point 8
12 4 % Point 9
16 6 % Point 10
14 17 % Point 11
19 18 % Point 12
];
xy = xy';
convexHull = getConvexHull(xy);
function k = getConvexHull(xy)
[m,n] = size(xy);
if m~=2
error('convexhull: xy must have 2 columns');
end
[xmin,first] = min( xy(1,:) );
ind = [1:(first-1) (first+1):n];
angle = atan2( xy(1,ind)-xy(1,first), xy(2,ind)-xy(2,first) );
[junk,order] = sort(angle);
ind = [ind(order) first];
stack = zeros( n, 1, 'uint32' );
stack(1) = first;
stacktop = 1;
i = 1;
while i<=n
if stacktop<2
stacktop = stacktop+1;
stack(stacktop) = ind(i);
i = i+1;
else
p0 = xy(:,stack(stacktop));
p1 = xy(:,stack(stacktop-1));
p2 = xy(:,ind(i));
if (p1(1)-p0(1))*(p2(2)-p0(2))-(p2(1)-p0(1))*(p1(2)-p0(2)) >= 0
stacktop = stacktop+1;
stack(stacktop) = ind(i);
i = i+1;
else
stacktop = stacktop-1;
end
end
end
k = stack(1:stacktop);
end
Output
6
5
12
10
9
8
7
6
(Counter clockwise convex hull points)

  4 Comments

Show 1 older comment
Philippe Lebel
Philippe Lebel on 5 Dec 2019
Ho, i just remembered i had it saved on my computer to run it and diagnose it!
Here is the original question (code in this case):
clear;
close all;
clc;
xy = [
3 12 % Point 1
3 12 % Point 1
3 12 % Point 1
3 12 % Point 1
10 8 % Point 2
11 14 % Point 3
13 16 % Point 4
9 19 % Point 5
1 15 % Point 6
2 5 % Point 7
6 1 % Point 8
12 4 % Point 9
16 6 % Point 10
14 17 % Point 11
19 18 % Point 12
];
xy = xy';
[m,n] = size(xy);
if m~=2
error('convexhull: xy must have 2 columns');
end
[xmin,first] = min( xy(1,:) );
ind = [1:(first-1) (first+1):n];
angle = atan2( xy(1,ind)-xy(1,first), xy(2,ind)-xy(2,first) );
[junk,order] = sort(angle);
ind = [ind(order) first];
stack = zeros( n, 1, 'uint32' );
stack(1) = first;
stacktop = 1;
i = 1;
while i<=n
if stacktop<2
stacktop = stacktop+1;
stack(stacktop) = ind(i);
i = i+1;
else
p0 = xy(:,stack(stacktop));
p1 = xy(:,stack(stacktop-1));
p2 = xy(:,ind(i));
if (p1(1)-p0(1))*(p2(2)-p0(2))-(p2(1)-p0(1))*(p1(2)-p0(2)) >= 0
stacktop = stacktop+1;
stack(stacktop) = ind(i);
i = i+1;
else
stacktop = stacktop-1;
end
end
end
indexes = stack(1:stacktop);

Sign in to comment.

Accepted Answer

Philippe Lebel
Philippe Lebel on 4 Dec 2019
Edited: Philippe Lebel on 4 Dec 2019
By observation, points 8, 9 and 10 are on the same line.
You have to add a condition to decimate redundant points. (points that lie on the same line or points that are stacked on each other for example)
You can quickly verify if what i say is the case by changing point 9 by [4.00001,12]

More Answers (0)

Sign in to answer this question.