Geometry Boost List: Re: [geometry] Bug in boost geometry 1.48: union of 2 polygons is wrong.

Subject: Re: [geometry] Bug in boost geometry 1.48: union of 2 polygons is wrong.
From: Barend Gehrels (barend_at_[hidden])
Date: 2012-01-15 15:58:07

Hi Zachary,

> Some background, please ignore if not useful:

Thanks for this useful background!

>
> Here I was computing a union of rectangles making sure upfront that 
> the set is connected and rectangles only abut each other (no 
> intersections with positive area).
>
> I worked for 9 years in GIS and more in EDA and I implemented a few 
> geometrical packages. Every time integers were used as coordinates and 
> we made sure that the absolute values were less than 2^30 for our 
> domain, so it was always possible to add or subtract two values 
> without overflow. I never used integer multiplication in the code. I 
> had to use long long for finding the sign of a cross product. When 
> finding an intersection of two segments I first determined the type of 
> intersection (overlap, touch, etc, etc.) and in case of true 
> intersection I was using doubles and then some logic to round up the 
> result back to integers.
>
> No matter what precision you use you can always construct a case when 
> intersection causes topology violation. Take 2 rays emanating from the 
> same point at a very narrow angle and intersect them with a line, 
> which passes close to this point. Two intersection points, which are 
> distinct will merge into one.
>
> However one can be safe if the nature of the data is well understood 
> and the data is verified. Presently I am working in the architecture 
> domain, my objects are rectilinear and my units are 1/1000 of an inch, 
> which does not cause overflow for the buildings I work with.
>
> So, my suggestion is: don't use integer multiplication in your code 
> and then your geometrical software will be applicable for a very wide 
> range of practical problems where coordinates are chosen to be integers.

This is very clear. It more or less fits into our design as well. In 
some strategies we use an (optional) CalculationType, a type to do the 
calculations in, which defaults (but might be different from) the 
CoordinateType of the geometries. So that is more or less what you have 
done with true intersections.

However, such a strategy cannot yet be specified for the union function.

But I will take this into account.

Regards, Barend