5
$\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.

Improve this question
$\endgroup$
4
  • $\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
    Commented Feb 11, 2017 at 4:12
  • $\begingroup$ @MarcoB I added a simple example. $\endgroup$
    – kaiten
    Commented Feb 11, 2017 at 4:35
  • $\begingroup$ kaiten, how many points are in your data set typically? $\endgroup$
    – MarcoB
    Commented Feb 11, 2017 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
    Commented Feb 11, 2017 at 5:28

1 Answer 1

Reset to default
4
$\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

Improve this answer
$\endgroup$
10
  • $\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
    Commented Feb 11, 2017 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
    Commented Feb 11, 2017 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
    Commented Feb 11, 2017 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
    Commented Feb 11, 2017 at 5:35
  • $\begingroup$ @kaiten, please see the updated post. $\endgroup$
    – kglr
    Commented Feb 11, 2017 at 6:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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