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: Zachary Deretsky (zach.deretsky_at_[hidden])
Date: 2012-01-15 18:55:49

Barend,
thanks for your response.

Since at Aditazz we chose to utilize boost geometry it will be very useful
for us to know, which operations are guaranteed to be safe for which
objects with integer coordinates with abs values less than 2^30.

It is not hard for me to implement the rest, I just did not want to build
the world from scratch again -:)

Best regards, Zach.

On Sun, Jan 15, 2012 at 12:58 PM, Barend Gehrels <barend_at_[hidden]> wrote:

> 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
>
> ______________________________**_________________
> Geometry mailing list
> Geometry_at_[hidden]
> http://lists.boost.org/**mailman/listinfo.cgi/geometry
>

>