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

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)

[Matt J]

Great. But please put the question back, so that the forum administrators don't have to do it for you.

[Philippe Lebel]

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]

(Answers Dev) Restored edit

[Rena Berman]

(Answers Dev) Restored edit

Answer 1

[Philippe Lebel]

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]

[The Merchant]

Cheers mate!

[Philippe Lebel]

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?