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

Subject: [ggl] Re: Help needed with Intersection operation
From: Barend Gehrels (barend)
Date: 2011-08-30 00:58:12

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

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