Bug #65285 for Math-ConvexHull:

Mon Jan 31 09:45:35 2011 peterbhowell [...] gmail.com - Ticket created

The algorithm fails to exclude all of the "internal" points in my circumstance. I created a square array of points arranged in columns and rows, filling a circular area. There are a few points not on the perimeter that are always included in the hull. When I introduce a small random error to the position of the points, the problem goes away. It only appears to occur when some of the points share the exact same X or Y values.

Sun Feb 13 05:56:20 2011 smueller [...] cpan.org - Correspondence added

Subject:	Re: [rt.cpan.org #65285]
Date:	Sun, 13 Feb 2011 11:56:06 +0100
To:	bug-Math-ConvexHull [...] rt.cpan.org
From:	Steffen Mueller <smueller [...] cpan.org>

Hi Peter, On 01/31/2011 03:45 PM, Peter B Howell via RT wrote: Show quoted text

> Mon Jan 31 09:45:35 2011: Request 65285 was acted upon. > Transaction: Ticket created by Peter_Howell > Queue: Math-ConvexHull > Subject: (No subject given) > Broken in: 1.03 > Severity: Normal > Owner: Nobody > Requestors: peterbhowell@gmail.com > Status: new > Ticket<URL: https://rt.cpan.org/Ticket/Display.html?id=65285> > > > The algorithm fails to exclude all of the "internal" points in my circumstance. I created a square > array of points arranged in columns and rows, filling a circular area. There are a few points not > on the perimeter that are always included in the hull. When I introduce a small random error to > the position of the points, the problem goes away. It only appears to occur when some of the > points share the exact same X or Y values.

I was planning to look into this ever since I got the mail about the RT ticket. Needless to say, it hasn't happened yet. Sorry. Thus I'm replying to let you know that I'm not ignoring you. It's just that right now, all my free software work is going into other projects. Do you think you could try to come up with a patch to fix this problem? The code is so old that I would have to re-learn it from scratch just as you would. If not, I will try to come back to this as soon as possible, but don't hold your breath. Best regards, Steffen

Sun Feb 13 05:56:21 2011 The RT System itself - Status changed from 'new' to 'open'

Sun Feb 13 13:48:31 2011 smueller [...] cpan.org - Correspondence added

Okay, strike my previous reply. I spent some time on the train today to fix your problem and optimize the module a bit. A new version will be release to CPAN within a few minutes and should propagate to CPAN mirrors within a day or so. Best regards, Steffen

Sun Feb 13 13:48:31 2011 smueller [...] cpan.org - Status changed from 'open' to 'resolved'

Sun Feb 13 14:09:28 2011 peterbhowell [...] gmail.com - Correspondence added

Subject:	Re: [rt.cpan.org #65285]
Date:	Sun, 13 Feb 2011 14:07:14 -0500
To:	bug-Math-ConvexHull [...] rt.cpan.org
From:	Peter Howell <peterbhowell [...] gmail.com>

That was fast. Thanks. I'm only a little disappointed that it's not an excuse for me to attempt a CPAN patch, but realistically I know that was just an excuse to avoid my paying projects. Thanks again. I'll wait a day and try the new version. On Feb 13, 2011, at 1:48 PM, Steffen Mueller via RT wrote: Show quoted text

> <URL: https://rt.cpan.org/Ticket/Display.html?id=65285 > > > Okay, strike my previous reply. I spent some time on the train today to > fix your problem and optimize the module a bit. A new version will be > release to CPAN within a few minutes and should propagate to CPAN mirrors > within a day or so. > > Best regards, > Steffen

Sun Feb 13 14:09:28 2011 The RT System itself - Status changed from 'resolved' to 'open'

Sun Feb 13 17:20:44 2011 smueller [...] cpan.org - Correspondence added

Hi Peter, On Sun Feb 13 14:09:28 2011, Peter_Howell wrote: Show quoted text

> That was fast. Thanks. I'm only a little disappointed that it's not > an excuse for me to attempt a CPAN patch, but realistically I know > that was just an excuse to avoid my paying projects. > > Thanks again. I'll wait a day and try the new version.

You can still make the effort and implement Chan's algorithm instead of Graham's scan. That should be algorithmically faster than the current implementation. On a side note: please send potential follow-ups to my email address directly instead of to RT. Sending email through RT using a ticket will reopen the ticket. Best regards, Steffen

Sun Feb 13 17:20:46 2011 smueller [...] cpan.org - Status changed from 'open' to 'resolved'