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

Subject: [ggl] Re: Help needed with Intersection operation
From: Simonson, Lucanus J (lucanus.j.simonson)
Date: 2011-08-30 22:06:26

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

On 08/29/2011 10:44 PM, Barend Gehrels wrote:
Hi Christophe,

I think higher precision will not help me. Say I have two triangles A,B,C - where B=C.

I substract B from A to get M. Then I intersect M and C. Because M and C may share a border i will get numeric problems with any precision. This happens quite often in my use case.

Personally I've seen several cases where ttmath did the job, and double didn't. But yes, if you are going up to the limits, in the end you will get problems with ttmath as well (but note that you can define precision by a template parameter).

Besides this, I did some research on your case and have to do more - it seems that it is not unsolveable (carefully stated...)

I think I will avoid this by checking first if the triangles have a parrallel border - and if they do I will take measures to avoid these problems. I have found it is extremely complicated to write code that works with FP for this kind of problem.

Yes, in these kind of cases this might be better. But in general, I did have problems by merging intersection points on distance - this is why that part is rewritten (about a year ago).

The best approach may be adaptive precision like in CGal.

We selected high precision, using an external library (now ttmath but it should be able to use another as well - in the past I used GMP and CLN as well)

If that is not an option, i would just define an epsilon (maybe about 10E-6) and if a point is less than epsilon away from a line, then we assume it is on the line. Maybe the epsilon could be adapted, before including the .hpp file.

See above - this is a solution in some cases but will give problems in other cases. However, we might think about this further - it could be in a strategy or policy, which could be selected at compile time (this has the same effect but is better then a required epsilon).

Regards, Barend

_______________________________________________
ggl mailing list
ggl_at_[hidden]<mailto:ggl_at_[hidden]>
http://lists.osgeo.org/mailman/listinfo/ggl

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/ggl/attachments/20110830/ddffffa8/attachment.html