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

Subject: [ggl] Re: Help needed with Intersection operation
From: Christoph Keller (christoph)
Date: 2011-08-30 08:28:02

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

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