samtregar has asked for the wisdom of the Perl Monks concerning the following question:

Greetings geometry monks. Here's my problem - I have a set of points on a grid and I want to draw a line around them. I believe this is basically what Math::ConvexHull was born for, but please correct me if I'm wrong. My problem is that instead of drawing a line around the points I'm getting a line that darts in and out of the volume, producing a very non-convex shape. It's all, um, spiky.

More detail - the points are longitude and latitude, although the scale is small enough that I should be able to pretend the grid is flat. However, that means that they're signed floats and the delta between them is relatively small.

I can post my data if need be, but it's pretty voluminous and hard to interpret without a graphing system, which I don't have to post at the moment. Perhaps someone can help me without a working example?

Thanks,
-sam

PS: I'm not stuck on using Math::ConvexHull for this. If you know of a more suitable tool I'd be happy to hear it. It doesn't need to be particularly fast.

  • Comment on Getting non-convex hulls from Math::ConvexHull

Replies are listed 'Best First'.
Re: Getting non-convex hulls from Math::ConvexHull
by GrandFather (Saint) on Jul 09, 2007 at 23:22 UTC

    Can you provide a small dataset (around 20 points) that shows the problem?

    It sounds like you need some sort of smoothing phase following the hull calculation. It may suffice to run the hull calculation twice using the result from the first pass as the input to the second pass.

    DWIM is Perl's answer to Gödel
[reply]
      Thank you! In attempting to put together a small test set I noticed that I had a lot of doubled points. I thought I'd successfully filtered them out in an earlier stage, but apparently not. After removing them I'm getting perfectly convex shapes.

      -sam

[reply]

        It may be worth reporting that as a bug (or at least as a known gotcha) to the module author.

        DWIM is Perl's answer to Gödel
[reply]

Back to Seekers of Perl Wisdom