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

2 次查看（过去 30 天）
The Merchant
The Merchant 2019-12-4
评论： Rena Berman 2020-1-16
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 个评论
显示 2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

采纳的回答

Philippe Lebel
Philippe Lebel 2019-12-4
编辑：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]

更多回答（0 个）

类别

在 Help Center 和 File Exchange 中查找有关 Bounding Regions 的更多信息

标签

Community Treasure Hunt

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

Start Hunting!

Translated by