Boost logo

Geometry :

Subject: [ggl] Re: Help needed with Intersection operation
From: Christoph Keller (christoph)
Date: 2011-08-29 13:44:48


Hello Barend,

Thanks for you answer.

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.

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.
The best approach may be adaptive precision like in CGal.

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.

Greetings,
Christoph

On 08/28/2011 10:22 PM, Barend Gehrels wrote:
> Hi Christophe,
>
> On 20-8-2011 0:13, Christoph Keller wrote:
>> Hello Angus,
>>
>> thanks for providing the code. However if I do that using double
>> precision, i get a triangle as output, that has little to do with the
>> intersection.
>>
>> I made a mistake posting my Data. One element had a different value.
>> I also used correct, as you suggested, but as I expected this changes
>> nothing.
>>
>> I posted my complete code below. Note that the y-value
>> 29.884635544079821 cannot belong to the first polygon.
>
> Right, it indeed should not. Though the output triangle in general
> represents the (more or less) right difference, it is apparently not
> precise enough for your purposes. If you use ttmath, you will get the
> (more) correct output. I will see if it can be improved for double as
> well.
>
>
>>
>> So it seems we found two errors.
>
> It is unclear to me which is the other error.
>
>> The question for me is if I should develop my own intersection code?
>
> That is not the intention.
>
> 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/20110829/161b5dcd/attachment.html


Geometry list run by mateusz at loskot.net