Re: [Jts-topo-suite-user] strange case for the GeometryNoder

[Martin D. <mtn...@gm...>]

Great reference, Stefan!  I'm not sure it offers much guidance on the
robust orientation problem, but it sure makes me feel good about being
part of the open source software world!

Martin

On Thu, May 17, 2012 at 1:42 PM, Stefan Steiniger <ss...@ge...> wrote:
> Not that I really contribution to the fact nor fully understand what it
> is about, but I just want to link to that paper by Ince et al. (Nature,
> 2o11): The case for open computer programs [1]
>
> its section: "Errors exist within ‘perfect’ descriptions"
>
> and the quote (from Monniaux):
>
> ‘‘More subtly, on some platforms, the exact same expression, with the
> same values in the same variables, and the same compiler, can be
> evaluated to different results, depending on seemingly irrelevant
> statements (print- ing debugging information or other constructs that do
> not openly change the values of variables).’’
>
> (by Monniaux,D. The pitfalls of verifying floating-point computations.
> ACM Trans. Programming Languages Systems 30 (3), 1–41 (2008).
>
> read this was really enlightening.. (at least I can blame someone ;)
> cheers,
> stefan
>
> [1] one of the links should work for download:
> http://scholar.google.ca/scholar?cluster=6783031770567216058&hl=en&as_sdt=0,5
> e.g.: http://www.runmycode.org/data/MetaSite/upload/nature10836.pdf
>
> PS: how about implementing 3/4 versions and picking the "majority"
> result? (which of course doesn't make it fast)
>
> Am 17.05.12 12:44, schrieb Martin Davis:
>> I'm aware of his work, but have no experience with implementing it or
>> using it.  It looks like it might be a bit complex to implement in
>> Java.
>>
>> I did some experimenting with implementing an orientation test
>> combining a fast filter with a fallback of the DD orientation code.
>> It worked for all my current failure cases - but not for your simple
>> case!  Or at least, the fast, direct double-precision code returned a
>> value of 0 for your case, whereas the DD code returned 1 (not
>> collinear).
>>
>> Now, what's puzzling is that if you treat the provided numbers as true
>> reals, 0 is the correct result! (as can be seen by scaling the numbers
>> by 10, to make them exact).   My only explanation for why the DD and
>> RD code return something else (with varying results in the case of the
>> RD code) is that they are working with an exact 64=bit unrounded
>> representation of the real numbers (which are only approximations to
>> the true value).  Whereas the simple FP code is using rounding, which
>> in this case is the right thing to do.
>>
>> My takeaway from this is that your suggestion of using rounding in
>> situations where a fixed precision is being used is a good approach.
>> In the case of snap-rounding, this should not be an issue, because as
>> long as a node is within the precision tolerance of a segment (ie the
>> segment intersects a hot pixel), the segment should be noded.  So
>> really I think there is a bug in the GeometryNoder code - it should
>> not be so affected by discrepancies at such high-precision.
>>
>> This still doesn't provide a solution for computing accurate
>> orientation values when using a FLOATING precision model (when the
>> issues discussed above are still effect).  In fact, there may be no
>> real solution to this, since it depends on how the binary
>> representation of decimal numbers is interpreted.  This is one more
>> example that reinforces my hypothesis that the only way to get fully
>> robust operations is to use snap-rounding (and thus some
>> fixed-precision model).
>>
>> On Thu, May 17, 2012 at 12:29 AM, Tomas Fa<tof...@gm...>  wrote:
>>> Thanks.
>>> Do you have experience of, or opinions about, Shewchuks algorithm for robust
>>> sign of determinants? (http://www.cs.cmu.edu/~quake/robust.html)
>>>
>>> /Tomas
>>>
>>> On Wed, May 16, 2012 at 10:53 PM, Martin Davis<mtn...@gm...>  wrote:
>>>>
>>>> Yes, it looks like you've run into a robustness failure with the
>>>> (supposedly) RobustDeterminant algorithm.  There's a few of those that have
>>>> cropped up - although none with as low precision as your case.  Clearly
>>>> the RobustDeterminant code is not in fact 100% robust, contrary to the
>>>> advertising!
>>>>
>>>>
>>>> http://jts-topo-suite.svn.sourceforge.net/viewvc/jts-topo-suite/trunk/jts/java/test/test/jts/junit/algorithm/OrientationIndexFailureTest.java?revision=597&view=markup
>>>>
>>>> I'm reluctant to go in and mess with the RobustDeterminant algorithm,
>>>> since it's pretty complex and obviously critical to get right.  The idea of
>>>> rounding might work for your case, but the other failure cases occur with
>>>> full FP precision, so it's not going to fix them.
>>>>
>>>> Another possibility is to use another method for computing determinant
>>>> sign.  The DoubleDouble arithmetic now in JTS seems to provide enough
>>>> precision to handle this, but it's slow.  Combining it with a fast filter
>>>> might be the way to go. It might even be possible to compute the filter
>>>> using a combination of basic double-precision determinant evaluations, which
>>>> would be as faster or faster than the current algorithm.
>>>>
>>>> This is going to take some careful experimentation, however - there is a
>>>> large risk for getting this wrong.
>>>>
>>>>
>>>> On Tue, May 15, 2012 at 5:40 AM, Tomas Fa<tof...@gm...>  wrote:
>>>>>
>>>>> I think that the problem lies in the RobustDeterminant. I think that the
>>>>> RobustDeterminant would be more
>>>>> robust if it was using a fixed PrecisionModel (in a context where a fixed
>>>>> precision is used). Currently, it is
>>>>> impossible, as far as I know ,to specify a precisionModel for
>>>>> CGAlgorithms, but I think it would be desirable.
>>>>> You can provide a MCIndexSnapRounder with a PrecisionModel, but it
>>>>> doesn't use it when CGAlgorithms
>>>>> gets involved (which it gets because of the line intersection
>>>>> operations). In the following program
>>>>> CGAlgorithms fails to behave consistently:
>>>>>
>>>>
>>>>
>>>> ------------------------------------------------------------------------------
>>>> Live Security Virtual Conference
>>>> Exclusive live event will cover all the ways today's security and
>>>> threat landscape has changed and how IT managers can respond. Discussions
>>>> will include endpoint security, mobile security and the latest in malware
>>>> threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/
>>>> _______________________________________________
>>>> Jts-topo-suite-user mailing list
>>>> Jts...@li...
>>>> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
>>>>
>>>
>>
>> ------------------------------------------------------------------------------
>> Live Security Virtual Conference
>> Exclusive live event will cover all the ways today's security and
>> threat landscape has changed and how IT managers can respond. Discussions
>> will include endpoint security, mobile security and the latest in malware
>> threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/
>> _______________________________________________
>> Jts-topo-suite-user mailing list
>> Jts...@li...
>> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
>
> ------------------------------------------------------------------------------
> Live Security Virtual Conference
> Exclusive live event will cover all the ways today's security and
> threat landscape has changed and how IT managers can respond. Discussions
> will include endpoint security, mobile security and the latest in malware
> threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/
> _______________________________________________
> Jts-topo-suite-user mailing list
> Jts...@li...
> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user