Does anyone know why it is also taking point 9 as convex hull point eventhough it shouldn't?
4 Ansichten (letzte 30 Tage)
Ältere Kommentare anzeigen
The Merchant
am 4 Dez. 2019
Kommentiert: Rena Berman
am 16 Jan. 2020
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 Kommentare
Akzeptierte Antwort
Philippe Lebel
am 4 Dez. 2019
Bearbeitet: Philippe Lebel
am 4 Dez. 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]
2 Kommentare
Philippe Lebel
am 4 Dez. 2019
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?
Weitere Antworten (0)
Siehe auch
Kategorien
Mehr zu Bounding Regions finden Sie in Help Center und File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!