Bug #72103 for Math-ConvexHull: Convex Hull Problems

Tue Nov 01 15:45:57 2011 Frank.Poggio [...] pdt.com - Ticket created

Subject:	Convex Hull Problems
Date:	Tue, 1 Nov 2011 19:45:46 +0000
To:	"bug-Math-ConvexHull [...] rt.cpan.org" <bug-Math-ConvexHull [...] rt.cpan.org>
From:	"Poggio, Frank" <Frank.Poggio [...] pdt.com>

Dear Mr. Mueller, First, thank you very much for writing the Convex Hull script for Perl. I have found it very useful. I am using Convex Hull with my own rotating calipers code to calculate the height of large sets (thousands) of randomly ordered points in XY space. I am removing duplicates and these are floating point numbers, to 12 digits to the right of the decimal point, so I am rounding, leaving only 3, 2, or even 1 digit(s) to the right of the decimal point. However, it still does not work on approximately 10% of the data sets, it does not eliminate what is obviously an internal point. If I sent you some problem files, do you have the time to investigate? Thank you very much. Frank Poggio product development technologies, inc. One Corporate Drive, Suite 110 Lake Zurich, Illinois 60047 p 847 821 3039 f 847 821 3020 frank.poggio@pdt.com<mailto:frank.poggio@pdt.com> PDT<http://www.pdt.com/> | LinkedIn<http://www.linkedin.com/company/product-development-technologies/products> | Facebook<http://www.facebook.com/askpdt> | Twitter<http://www.twitter.com/askpdt> | YouTube<http://www.youtube.com/askpdt>

Wed Nov 02 03:16:14 2011 smueller [...] cpan.org - Correspondence added

Subject:	Re: [rt.cpan.org #72103] Convex Hull Problems
Date:	Wed, 02 Nov 2011 08:15:55 +0100
To:	bug-Math-ConvexHull [...] rt.cpan.org
From:	Steffen Mueller <smueller [...] cpan.org>

Hi, On 11/01/2011 08:45 PM, Poggio, Frank via RT wrote: Show quoted text

> First, thank you very much for writing the Convex Hull script for > Perl. I have found it very useful. I am using Convex Hull with my own > rotating calipers code to calculate the height of large sets > (thousands) of randomly ordered points in XY space. I am removing > duplicates and these are floating point numbers, to 12 digits to the > right of the decimal point, so I am rounding, leaving only 3, 2, or > even 1 digit(s) to the right of the decimal point. However, it still > does not work on approximately 10% of the data sets, it does not > eliminate what is obviously an internal point. > > If I sent you some problem files, do you have the time to > investigate? Thank you very much.

Unfortunately, that's rather unlikely. If you could provide a small example that exhibits the problem, I might get a chance, but don't hold your breath. I have too much work on my hands as it stands. On the other hand, if you figure out the problem and come up with a patch, I'll gladly apply it and make a fresh release. Best regards, Steffen

Wed Nov 02 03:16:15 2011 The RT System itself - Status changed from 'new' to 'open'

Thu Nov 03 17:19:04 2011 Frank.Poggio [...] pdt.com - Correspondence added

Subject:	RE: [rt.cpan.org #72103] Convex Hull Problems
Date:	Thu, 3 Nov 2011 21:18:45 +0000
To:	"bug-Math-ConvexHull [...] rt.cpan.org" <bug-Math-ConvexHull [...] rt.cpan.org>
From:	"Poggio, Frank" <Frank.Poggio [...] pdt.com>

Hi Steffen Mueller, Thank you for getting back to me quickly. If you happen to find time, the attached zip file has rounded and unrounded input and output data in Excel format. I have attached my Perl script which calls the convex hull module and the source STL file, which is the reason for the strange "clumping" of the input data. The bizarre thing is, for this data, the convex hull works for the unrounded data, but doesn't work for the rounded data. In most problem files, the opposite is true. Any assistance you can offer would be most appreciated. I don't have much time either, but if I do write code, it will be from scratch, and it won't be modular, as I'm not much of a Perl programmer (I'm a mechanical engineer) and don't understand much of your code. But, if I ever get it working, I'll be happy to share it with you. Frank Poggio Show quoted text

-----Original Message----- From: Steffen Mueller via RT [mailto:bug-Math-ConvexHull@rt.cpan.org] Sent: Wednesday, November 02, 2011 2:16 AM To: Poggio, Frank Subject: Re: [rt.cpan.org #72103] Convex Hull Problems <URL: https://rt.cpan.org/Ticket/Display.html?id=72103 > Hi, On 11/01/2011 08:45 PM, Poggio, Frank via RT wrote:

> First, thank you very much for writing the Convex Hull script for > Perl. I have found it very useful. I am using Convex Hull with my own > rotating calipers code to calculate the height of large sets > (thousands) of randomly ordered points in XY space. I am removing > duplicates and these are floating point numbers, to 12 digits to the > right of the decimal point, so I am rounding, leaving only 3, 2, or > even 1 digit(s) to the right of the decimal point. However, it still > does not work on approximately 10% of the data sets, it does not > eliminate what is obviously an internal point. > > If I sent you some problem files, do you have the time to investigate? > Thank you very much.

Unfortunately, that's rather unlikely. If you could provide a small example that exhibits the problem, I might get a chance, but don't hold your breath. I have too much work on my hands as it stands. On the other hand, if you figure out the problem and come up with a patch, I'll gladly apply it and make a fresh release. Best regards, Steffen Email secured by Check Point

Download 110209-hsg-base_r042.zip
application/x-zip-compressed 982.8k

Message body not shown because it is not plain text.

Wed Nov 09 12:22:56 2011 smueller [...] cpan.org - Correspondence added

I tested the module with your data and can reproduce the failure. Instead of spending arbitrary amounts of time fixing it, I have instead implemented a similar but slightly faster algorithm (Andrews' Monotone Chain) for calculating convex hulls. I wrote this one in C and added a Perl/XS interface. As a benefit, it should be much faster (and could be more optimized still). The new implementation produces the correct results. The new module was released under a different name: Math::ConvexHull::MonotoneChain. It will appear on you CPAN mirrors some when within the next couple of hours or days. When I get to it, I'll make a Math::ConvexHull release noting the known problems and pointing users at the improved module. Thanks and regards, Steffen

Wed Nov 09 12:22:58 2011 smueller [...] cpan.org - Status changed from 'open' to 'stalled'

Wed Nov 09 17:04:07 2011 Frank.Poggio [...] pdt.com - Correspondence added

Subject:	RE: [rt.cpan.org #72103] Convex Hull Problems
Date:	Wed, 9 Nov 2011 22:03:56 +0000
To:	"bug-Math-ConvexHull [...] rt.cpan.org" <bug-Math-ConvexHull [...] rt.cpan.org>
From:	"Poggio, Frank" <Frank.Poggio [...] pdt.com>

Thank you Steffen. I see it on CPAN. I should get it installed in the next few days. I will do some testing and let you know. Do duplicate points need to eliminated, and is trimming the precision on floating point numbers recommended? Frank Show quoted text

-----Original Message----- From: Steffen Mueller via RT [mailto:bug-Math-ConvexHull@rt.cpan.org] Sent: Wednesday, November 09, 2011 11:23 AM To: Poggio, Frank Subject: [rt.cpan.org #72103] Convex Hull Problems <URL: https://rt.cpan.org/Ticket/Display.html?id=72103 > I tested the module with your data and can reproduce the failure. Instead of spending arbitrary amounts of time fixing it, I have instead implemented a similar but slightly faster algorithm (Andrews' Monotone Chain) for calculating convex hulls. I wrote this one in C and added a Perl/XS interface. As a benefit, it should be much faster (and could be more optimized still). The new implementation produces the correct results. The new module was released under a different name: Math::ConvexHull::MonotoneChain. It will appear on you CPAN mirrors some when within the next couple of hours or days. When I get to it, I'll make a Math::ConvexHull release noting the known problems and pointing users at the improved module. Thanks and regards, Steffen Email secured by Check Point

Wed Nov 09 17:04:08 2011 The RT System itself - Status changed from 'stalled' to 'open'

Thu Nov 10 02:00:43 2011 smueller [...] cpan.org - Correspondence added

Subject:	Re: [rt.cpan.org #72103] Convex Hull Problems
Date:	Thu, 10 Nov 2011 08:00:23 +0100
To:	bug-Math-ConvexHull [...] rt.cpan.org
From:	Steffen Mueller <smueller [...] cpan.org>

Hi Frank, On 11/09/2011 11:04 PM, Poggio, Frank via RT wrote: Show quoted text

> Thank you Steffen. I see it on CPAN. I should get it installed in the > next few days. I will do some testing and let you know. Do duplicate > points need to eliminated, and is trimming the precision on floating > point numbers recommended?

It should eliminate duplicates by itself (see tests) and rounding isn't necessary. You might run into problems with VERY large coordinate values close to the limit of what your architecture can stuff into a double since they'll be squared in at least on place. But that shouldn't normally be an issue. Unlike the original implementation, then new one does not use any trig functions. It sorts by x/y instead of polar coordinates. This bug report is about the original module, though, so please send further questions about the new module to smueller@cpan.org by email. (And separate bug reports to the bug tracker of the new module.) Best regards, Steffen