Possible Bug in Boost Geometry's Huiller Algorithm
Hi Folks. I was looking at the implementation of the huiller algorithm in boost, and it seems to be partially incorrect. See boost/geometry/strategies/spherical/area_huiller.hpp In the apply() function, we have if(lon2 < lon1){ E =-E;} which I believe should instead be calculation_type lon;if( lon2 < lon1 ) lon = lon1 - lon2;else lon = lon1 - lon2 + two_pi;if(2* half_pi < lon ) E =-E; according to Graphics Gems 5, pg 45 - 46. The comments at the top of the C++ file state that the code was derived from code in Graphics Gems 4, though the code was later corrected in Graphics Gems 5. I noticed this when trying to calculate areas of polygons on a sphere, where one of the points was (0, 0). In that case, it would always return a negative area, even though the polygon was defined counter-clockwise. Using a point other than (0,0) seemed to alleviate the problem, which got me wondering what was going on. Can anybody else confirm that this is an issue? Any suggestions for cleanly overriding boost's implementation until this is fixed? Thanks! - Brian
Hi Brian,
I was looking at the implementation of the huiller algorithm in boost, and it seems to be partially incorrect. See boost/geometry/strategies/spherical/area_huiller.hpp
In the apply() function, we have if(lon2< lon1){ E =-E;} which I believe should instead be calculation_type lon;if( lon2< lon1 ) lon = lon1 - lon2;else lon = lon1 - lon2 + two_pi;if(2* half_pi< lon ) E =-E; according to Graphics Gems 5, pg 45 - 46. The comments at the top of the C++ file state that the code was derived from code in Graphics Gems 4, though the code was later corrected in Graphics Gems 5. I noticed this when trying to calculate areas of polygons on a sphere, where one of the points was (0, 0). In that case, it would always return a negative area, even though the polygon was defined counter-clockwise. Using a point other than (0,0) seemed to alleviate the problem, which got me wondering what was going on.
Can anybody else confirm that this is an issue? Any suggestions for cleanly overriding boost's implementation until this is fixed?
Thanks for your report. I will have a look at this and correct it. Regards, Barend
Hi Brian, On 28-2-2012 15:48, Brian Ahr wrote:
Hi Folks.
I was looking at the implementation of the huiller algorithm in boost, and it seems to be partially incorrect. See boost/geometry/strategies/spherical/area_huiller.hpp
(...)The comments at the top of the C++ file state that the code was derived from code in Graphics Gems 4, though the code was later corrected in Graphics Gems 5.
The comments also say: "The version in Gems didn't account for polygons crossing the 180 meridian. This version works for (...) for 180 meridian crossing polygons ... " So the same bug is apparently corrected (but probably differently).
I noticed this when trying to calculate areas of polygons on a sphere, where one of the points was (0, 0). In that case, it would always return a negative area, even though the polygon was defined counter-clockwise. Using a point other than (0,0) seemed to alleviate the problem, which got me wondering what was going on.
I cannot reproduce your problem. When I'm doing what you describe, also using (0,0), I get the correct results. Can you send me a problem-causing polygon? (preferrably in WKT format). Thanks, Barend
participants (2)
-
Barend Gehrels -
Brian Ahr