# Geometry :

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]

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

Geometry list run by mateusz at loskot.net