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-14 21:45:04

Barend,
thank you for the fast response.

Some background, please ignore if not useful:

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.

Best regards, Zach.

On Sat, Jan 14, 2012 at 2:39 AM, Barend Gehrels <barend_at_[hidden]> wrote:

>  Hi again,
>
>
> On 14-1-2012 11:20, Barend Gehrels wrote:
>
>
> But of course I will have a look what is exactly going wrong here because
> I agree that this simple case should be handled correctly in *integer *
> coordinates.
>
>
> The cause is overflow, if you use *__int64* (or another large enough
> integer type) the result is correct.
> Also, if you divide the coordinates by 100 (rounding of ~4 values), the
> result is correct in plain *integer *coordinates.
>
> Regards, Barend
>
>
>
> _______________________________________________
> Geometry mailing list
> Geometry_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/geometry
>
>