5
$\begingroup$

I'm using an old function which uses ConvexHull from the obsolete ComputationalGeometry package. I understand this is superseded by ConvexHullRegion. However, I need to know which points are on the lower boundary legs of the convex hull and ConvexHull returns this information. In the plot below, the points $(0,8),(3,6),(6,4),(9,2),(12,0)$ are on the (single) lower leg of the polygon and those points are returned by ConvexHull. But ConvexHullRegion only returns the vertexes of the hull. For example, using the obsolete ConvexHull function:

Needs["ComputationalGeometry`"];    
myPoints = {{0, 8}, {2, 7}, {3, 6}, {4, 6}, {5, 5}, {6, 4}, {8, 
        3}, {9, 2}, {12, 0}};
    chIndexes = ConvexHull[myPoints];
    Sort@myPoints[[chIndexes]]

    (* {{0, 8}, {2, 7}, {3, 6}, {4, 6}, {6, 4}, {8, 3}, {9, 2}, {12, 0}} *)

returns all 8 points on the boundary of the hull:

enter image description here

But if I use:

RegionBoundary[ConvexHullRegion[myPoints]] /. Line[x_] -> x

{{0, 8}, {12, 0}, {4, 6}, {0, 8}}

this is only returning the vertex points of the convex hull.

I'd prefer to switch to ConvexHullRegionif it's easy to do so because the obsolete ConvexHull may be removed in future revisions of Mathematica but haven't figured out how to do this but maybe missing something. Or is there no built-in construct to do this?

Improve this question
$\endgroup$
2
  • $\begingroup$ Would you add something that states why you need all of boundary points as they are not needed to define the convex hull? My point is that do you just need to know which points are on the boundary or do you really need those points included in the convex hull polygon? That would help with how to approach an answer. $\endgroup$
    – JimB
    Mar 22, 2022 at 17:50
  • $\begingroup$ @Jim: Ok I updated the post. $\endgroup$
    – josh
    Mar 22, 2022 at 18:58

1 Answer 1

Reset to default
7
$\begingroup$ 
chr = ConvexHullRegion[myPoints];

You can use SignedRegionDistance to select members of myPoints that lie on the boundary of chr:

pointsOnBoundary = Select[SignedRegionDistance[chr]@# == 0 &] @ myPoints

{{0, 8}, {2, 7}, {3, 6}, {4, 6}, {6, 4}, {8, 3}, {9, 2}, {12, 0}} 

Graphics[{LightBlue, chr, 
  Red, AbsolutePointSize[10], Point @ pointsOnBoundary, 
  Black, AbsolutePointSize[5],  Point @ myPoints},
ImageSize -> Large]

enter image description here

You can also use RegionIntersection + RegionBoundary as follows:

RegionIntersection[RegionBoundary[chr], Point@myPoints][[1]] == pointsOnBoundary 

True
Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ It's pretty cool, how almost every time you write an answer, I have some new reading to do :-) (talking about SignedRegionDistance) $\endgroup$
    – bmf
    Mar 22, 2022 at 21:40
  • 1
    $\begingroup$ @kglr: Thank you. Nice to know about that function, and this definitely answers my question. However, it is unfortunately 9400 times slower than ConvexHull in this case: 1.45s and 0.00015s respectively on my machine which would be unacceptably slow for my app which can create hundreds of hulls. I'll leave the thread open for a few days in case anyone wants to attempt a speed improvement otherwise I'll check your excellent answer. $\endgroup$
    – josh
    Mar 22, 2022 at 22:29
  • 2
    $\begingroup$ @josh, try Select[SignedRegionDistance[DiscretizeRegion@RegionBoundary@chr]@#==0&]@myPoints) for a much faster version. $\endgroup$
    – kglr
    Mar 22, 2022 at 22:39
  • $\begingroup$ @kglr: Excellent improvement! Down to 0.035s. And I realize speed was not the topic of my thread. Thanks for taking the time to propose a nice improvement. $\endgroup$
    – josh
    Mar 22, 2022 at 23:02
  • $\begingroup$ @josh You can speed it up by not placing SignedRegionDistance in Select e.g. extracting upper bound envelope $\endgroup$
    – Chris Degnen
    Apr 10, 2022 at 12:56

Your Answer

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

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