2 views (last 30 days)

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)

Philippe Lebel
on 4 Dec 2019

Edited: Philippe Lebel
on 4 Dec 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]

Philippe Lebel
on 4 Dec 2019

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

Start Hunting!
## 4 Comments

## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/494800-does-anyone-know-why-it-is-also-taking-point-9-as-convex-hull-point-eventhough-it-shouldn-t#comment_774348

⋮## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/494800-does-anyone-know-why-it-is-also-taking-point-9-as-convex-hull-point-eventhough-it-shouldn-t#comment_774348

## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/494800-does-anyone-know-why-it-is-also-taking-point-9-as-convex-hull-point-eventhough-it-shouldn-t#comment_774901

⋮## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/494800-does-anyone-know-why-it-is-also-taking-point-9-as-convex-hull-point-eventhough-it-shouldn-t#comment_774901

## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/494800-does-anyone-know-why-it-is-also-taking-point-9-as-convex-hull-point-eventhough-it-shouldn-t#comment_777408

⋮## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/494800-does-anyone-know-why-it-is-also-taking-point-9-as-convex-hull-point-eventhough-it-shouldn-t#comment_777408

## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/494800-does-anyone-know-why-it-is-also-taking-point-9-as-convex-hull-point-eventhough-it-shouldn-t#comment_786698

⋮## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/494800-does-anyone-know-why-it-is-also-taking-point-9-as-convex-hull-point-eventhough-it-shouldn-t#comment_786698

Sign in to comment.