4
$\begingroup$

I have been unable to explain the behavior of Graphics`Mesh`ConvexHull[] on the following (highly simplified) example:

pts = {{-1/6, -1/18}, {-4/31, 1/9}, {-1/26, -12/73},
       {1/6, 2/37}, {1/26, 12/73}, {4/31, -1/9}};

Graphics`Mesh`MeshInit[];

idx = ConvexHull[pts];

idx2 = Most[First[FindCurvePath[pts]]];

GraphicsRow[{Graphics[Line[pts]], Graphics[Line[pts[[idx]]]], Graphics[Line[pts[[idx2]]]]}]

I get the following result on my system (version 8.0.4 on Linux, if it matters):

convex hull attempts on my points

As you can see, ConvexHull[] does not seem to work properly on my set of points, while FindCurvePath[] has no problem. However, I had wanted to use ConvexHull[] because it consistently orders points in an anticlockwise manner (or at the very least it seems to), while FindCurvePath[] sometimes orders points clockwise. I can break down and just implement the Graham scan myself, but I'd prefer to understand why the hidden convex hull routine is not behaving in the manner I expect.

$\endgroup$
  • 2
    $\begingroup$ Why are you bothering with Graphics`Mesh? $\endgroup$ – m_goldberg Feb 26 '13 at 6:30
  • $\begingroup$ See my comment to your answer. $\endgroup$ – Carlos Culo Feb 26 '13 at 6:31
  • 1
    $\begingroup$ Is Graphics``Mesh documented somewhere? $\endgroup$ – Dr. belisarius Feb 26 '13 at 12:12
1
$\begingroup$

I can not reproduce your problem. When I carry out the following evaluations

Needs@"ComputationalGeometry`"

GraphicsRow@{
  Graphics[Line@pts], 
  Graphics[Line@pts[[ConvexHull[pts]]]]}

I get

enter image description here

$\endgroup$
  • 1
    $\begingroup$ As I mentioned in my post, I was using Graphics`Mesh`ConvexHull[] and not the implementation from the Computational Geometry package (I am aware of that, but due to a number of reasons, I prefer not to have to load a package)... $\endgroup$ – Carlos Culo Feb 26 '13 at 6:30
  • $\begingroup$ @CarlosCulo. If that's the case, then you are probably stick with the behavior you observe. $\endgroup$ – m_goldberg Feb 26 '13 at 7:12

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.