how to find the vertices of the convex hull of set of points

Dear all,

I want to check the points in the convex hull, I know how to find the convex hull of the set but I don't know how to find the vertices so I can check them. if anyone have an idea how to do it could he please tell me.

Regards,

Imola

Answer 1

[John D'Errico]

K = unique(convhull(xy));

Unique is there because one point will be replicated in that list otherwise. If you want it as a polygon, so the first and last points will be the same, then drop the unique.

[imola]

Dear John,

I tried this code for just 10 points and I want just the points of the vertices so I can check them in my hyper-rectangle in stead all the points, how I can manage to find them?

x = rand(1,10);
y = rand(1,10);
  hold on
plot(x,y,'.r');
K = convhull(x,y);
plot(x(K),y(K),'-')
I used your code

l = unique(convhull(K)); but I didn't get the points.

thanks for answering me.

Regards, imola

[John D'Errico]

Sigh. Before you do silly things, think about what you have, what it means. Look at the output from a computation.

In the code fragment you show in your comment, K IS a list of indexes to the points in the convex hull. Essentially, it already tells you which points are in the convex hull.

If you then try to compute convhull(K), you will get garbage. But why would you bother to do so? Think about what you are doing, rather than trying random things. If you want to look at the coordinates of those points, then

x(K)
y(K)

will suffice. In fact, the code fragment you already have plots EXACTLY those points!

The only thing extra I added was the unique call, since convhull returns a polygon, with the first point repeated at the end of the polygon.

x = rand(1,10);
y = rand(1,10);
K = convhull(x,y)
K =
     1
     8
     6
     5
     4
     1

Thus in the list of points in the plane, (x,y), the convex hull is a polygon that uses points from that set [1 8 6 5 4 1], in THAT ORDER to move around the convex hull polygon.

Unique removes the repeated final point, but it also sorts the indices, so that those points need no longer be in the proper order to form a polygon. Since you asked only for the points which represent the vertices of the convex hull, I gave you the indices which reference that set.

unique(K)
ans =
     1
     4
     5
     6
     8

Again, IF you want the points in the convex hull as a set of (x,y) pairs, you have already plotted them! The set

x(K),y(K)

is a polygon for the convex hull.