MATLAB Answers

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

6 ビュー (過去 30 日間)
The Merchant 2019 年 12 月 4 日
Commented: Rena Berman 2020 年 1 月 16 日 13:20
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 件のコメント

Philippe Lebel 2019 年 12 月 5 日
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);
Rena Berman 2019 年 12 月 12 日
(Answers Dev) Restored edit
Rena Berman 2020 年 1 月 16 日 13:20
(Answers Dev) Restored edit

サインイン to comment.

### 採用された回答

Philippe Lebel 2019 年 12 月 4 日

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]

#### 2 件のコメント

The Merchant 2019 年 12 月 4 日
Cheers mate!
Philippe Lebel 2019 年 12 月 4 日
I just saw your picture, i don't know why point 9 shows inside the convex hull. Maybe it has been made with an other data set?

サインイン to comment.

### More Answers (0)

サインイン してこの質問に回答します。

Translated by