4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – MarcoB Feb 11 '17 at 4:12
  • $\begingroup$ @MarcoB I added a simple example. $\endgroup$ – kaiten Feb 11 '17 at 4:35
  • $\begingroup$ kaiten, how many points are in your data set typically? $\endgroup$ – MarcoB Feb 11 '17 at 5:24
  • $\begingroup$ @MarcoB It varies but generally a little more than 100 per dataset. (though I'm generating hundreds of such data sets). $\endgroup$ – kaiten Feb 11 '17 at 5:28
3
$\begingroup$

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 Geometry`ConvexHull2 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[Geometry`ConvexHull2[ pts]]

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

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

Mathematica graphics

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

Mathematica graphics

... 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 @ Geometry`ConvexHull2[ pts2]}]]

Mathematica graphics

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – kaiten Feb 11 '17 at 4:31
  • 1
    $\begingroup$ @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. $\endgroup$ – kglr Feb 11 '17 at 4:34
  • $\begingroup$ 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. $\endgroup$ – kaiten Feb 11 '17 at 4:42
  • $\begingroup$ @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.) $\endgroup$ – kglr Feb 11 '17 at 5:35
  • $\begingroup$ @kaiten, please see the updated post. $\endgroup$ – kglr Feb 11 '17 at 6:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.