# Finding non-collinear vertices of a convex hull

I'm fairly new to Mathematica (and programming in general tbh) and need this for a math project I'm working on.

I generate large collections of (rational, 2d) points and need to find which of these points are the vertices of the convex hull.

Some googling suggested that MeshCoordinates would do this, but it does not exclude points on the edges of the convex hull that are collinear with the vertices. It also gives rounded decimals but that is less of an issue.

Is there a simple way to do this?

Edit to include a simplified example, the vertices of the unit square with a redundant point ({1, .5}):

pts = {{0, 0}, {1, 0}, {0, 1}, {1, 1}, {1, .5}}


Both MeshCoordinates[ConvexHullMesh[pts]] and ConvexHullMesh[pts]["VertexCoordinates"] return the point {1, .5}, which is clearly not a vertex of the unit square.

The points I'm generating are not random, they are the result of a fairly involved set of calculations and many of them can be collinear.

• I can't seem to reproduce the presence of extra points that you mention in MeshCoordinates. It actually seems to do exactly what you need. Could you show an example where you see extra points being added? Feb 11, 2017 at 4:12
• @MarcoB I added a simple example. Feb 11, 2017 at 4:35
• kaiten, how many points are in your data set typically? Feb 11, 2017 at 5:24
• @MarcoB It varies but generally a little more than 100 per dataset. (though I'm generating hundreds of such data sets). Feb 11, 2017 at 5:28

Update: a brute force approach to eliminate coordinates that lie in the convex hull of other coordinates:

ClearAll[noncollinearF]
noncollinearF[verts_]:= Function[{k}, Nor @@ (RegionMember[ConvexHullMesh[#],k]&/@
Subsets[Complement[verts,{k}],{2}])]

Pick[#, noncollinearF[#] /@ #]&[Rationalize @ ConvexHullMesh[pts]["VertexCoordinates"]]


{{0, 0}, {1, 0}, {0, 1}, {1, 1}}

Pick[#, noncollinearF[#] /@ #]&[Rationalize@ConvexHullMesh[pts2]["VertexCoordinates"]]


{{0, 0}, {1, 1}, {1, 0}, {2, 1}}

Or define a function that picks the non-collinear vertices of the convex hull of a set of 2D points:

ncvF = With[{v = #}, Pick[v, Function[{k}, Nor @@ (RegionMember[ConvexHullMesh[#],k]&/@
Subsets[Complement[v,{k}],{2}])]/@v]]&;

ncvF[pts]


{{0, 0}, {1, 0}, {0, 1}, {1, 1}}

 ncvF[pts2]


{{0, 0}, {1, 1}, {1, 0}, {2, 1}}

Previous post:

The function GeometryConvexHull2 gives the desired coordinates for the simple example:

pts = {{0, 0}, {1, 0}, {0, 1}, {1, 1}, {1,1/2}};

chm = ConvexHullMesh[pts];
vertices = Rationalize[chm["VertexCoordinates"]] (* or MeshCoordinates[chm] *)


{{0, 0}, {1, 0}, {0, 1}, {1, 1}, {1, 1/2}}

strictvertices = Rationalize[GeometryConvexHull2[ pts]]


{{0, 0}, {1, 0}, {1, 1}, {0, 1}}

Show[chm, Graphics@Point[pts], Graphics[{Red, PointSize[Large], Point @ vertices}]]


Show[chm, Graphics@Point[pts], Graphics[{Red, PointSize[Large], Point @ strictvertices}]]


... but, it fails to eliminate some coordinates in an other example:

pts2 = {{0, 0}, {1/2, 0}, {1/2, 1/2}, {1, 1}, {3/2, 1}, {1, 0}, {2, 1}, {3/2, 1/2}}

Show[ConvexHullMesh[pts2], Graphics @ Point[pts2],
Graphics[{Red, PointSize[Large], Point @ GeometryConvexHull2[ pts2]}]]


• I thought your code solved my problem but after a little testing it has the same flaw as MeshCoordinates. I updated my post with a simple example. Feb 11, 2017 at 4:31
• @kaiten, just noticed the update to your post. I don't think it is an issue because the point {1, 1/2} is a member of the the convex hull.
– kglr
Feb 11, 2017 at 4:34
• Yes, but it is not a vertex (should I call them corners?). The convex hull is a polygon, and I'm interested in the vertices of that polygon. An equivalent way to look at it would be a minimal set of points to generate the same convex hull. Feb 11, 2017 at 4:42
• @kaiten, i see your point. That seems to be a difficult problem. ConvexHullMesh does not eliminate collinear vertices; check for example pts2={{0,0},{1/2,0},{1/2,1/2},{1,1},{3/2,1},{1,0},{2,1},{3/2,1/2}}. (Btw, i meant {1, 1/2}` is a vertex of the convex hull.)
– kglr
Feb 11, 2017 at 5:35
• @kaiten, please see the updated post.
– kglr
Feb 11, 2017 at 6:19