Geometry Boost List: [ggl] Re: Help needed with Intersection operation

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]
> http://lists.osgeo.org/mailman/listinfo/ggl
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.

Greetings,
Christoph
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/ggl/attachments/20110906/9d865e0b/attachment.html