Boost logo

Geometry :

Subject: [ggl] Re: Help needed with Intersection operation
From: Christoph Keller (christoph)
Date: 2011-09-06 03:21:23

On 08/30/2011 11:33 PM, Barend Gehrels wrote:
> On 30-8-2011 18:47, Simonson, Lucanus J wrote:
>> Christoph,
>> As it happens the Boost.Polygon library provide polygon intersection
>> operations that use 32 bit long instead of double and are 100%
>> numerically robust. The library uses snap rounding and bounds the
>> maximum error to 1 integer unit square (you can move sqrt(2) distance
>> diagonally at maximum due to integer snapping error). To get high
>> precision you can scale your data. You might consider giving it a try.
>> Regards,
>> Luke
>> ------------------------------------------------------------------------
>> *From:* ggl-bounces_at_[hidden]
>> [mailto:ggl-bounces_at_[hidden]] *On Behalf Of *Christoph Keller
>> *Sent:* Monday, August 29, 2011 8:51 PM
>> *To:* Generic Geometry Library Discussion
>> *Subject:* Re: [ggl] Re: Help needed with Intersection operation
>> Hello Barend,
>> Maybe i could use integers (32 bit long) instead of double?
>> I have to cut out streets (rectangles) out of a 2d mesh. The result
>> is fed into a nav mesh generator, so it does not matter if the
>> results are not absolutely precise, but they should not be off by a
>> very wide margin.
>> Thanks,
>> Christoph
> Hi Christoph,
> If integer is an option, I don't exactly understand why ttmath is not.
> Anyway, if you want to use integers, Boost.Polygon, as Luke suggests,
> is a good alternative and tested extensively with integer coordinates.
> Besides that, I looked further to the problem and in the end it is (of
> course) very simple and fixed, at least temporary helped (I want to
> work further on it but don't know if I've the time coming month). It
> was a robustness issue and also influenced the testcase of Enrico and
> that if Brandon (submitted long ago). I should have been more
> defensive at that point.
> So thanks for the report, this again helped to make the library
> better, and it is possible that you encounter more problems, if so the
> reports are welcome.
> Regards, Barend
> _______________________________________________
> ggl mailing list
> ggl_at_[hidden]
Hello Barend,

The difference between integer and ttmath is that if we look at the
original test case and substract B from A (lets call the result C) and
then intersect C with B, then no precision would have avoided this kind
of numerical problem. (The problem is that a point from B is very near
the border of C in the order of epsilon). With integer we get some
rounding error in each operation(I can live with that). It is ok, if I
get a very small triangle from the intersecton operation, that can be
thrown away.

This whole series of operations is a bit strange anyway.

Thanks for all your effort.

-------------- next part --------------
An HTML attachment was scrubbed...

Geometry list run by mateusz at