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 endend k = stack(1:stacktop); end
Output
6512109876
(Counter clockwise convex hull points)
Best Answer