Possible orientation4 bug about robust-orientation HOT 6 CLOSED

It is quite possibly a bug. I found an error in robust-scale the other day which I am currently working on correcting. Once I get this fixed up, my next highest priority is to take a closer look at robust-orientation to make sure that it is working as intended.

from robust-orientation.

I just pushed a change set to two-product that fixed a long standing bug, and the latest version ought to work.

Looking at the mathematica examples, I think your expressions for the determinants are wrong. You are evaluating in Wolfram alpha the determinant:

| a0  b0  c0 |
| a1  b1  c1 |
| a2  b2  c2 |

But what you are computing in robust-orientation is the determinant:

| a0  b0  c0  0 |
| a1  b1  c1  0 |
| a2  b2  c2  0 |
| 1   1   1   1 |

For more information on this predicate, here is a link:

http://www.cs.cmu.edu/~quake/robust.html

from robust-orientation.

Thanks for looking into this!

Actually, the two determinant expressions you give above are equivalent. But I did make a mistake in my test case: the transposition wasn’t actually needed, since the determinant should be:

| a0 a1 a2 |
| b0 b1 b2 |
| c0 c1 c2 |

This is orient3d from Shewchuk’s paper. For convenience, I’m taking d = [0, 0, 0]. I’ve corrected the code in the bug description so it doesn’t transpose anything.

Your library now gives a positive sign for both test cases, which is encouraging, but unfortunately this doesn’t seem to match Mathematica, which gives a negative sign. For random test cases with no roundoff, your library seems to match Mathematica, so I’m wondering if there’s still a bug somewhere in the robustness code?

from robust-orientation.

Actually, I’m getting a positive sign when using an alternative quadruple-precision library, so maybe I shouldn’t put so much faith in Mathematica. I’ll check into it some more and get back to you.

from robust-orientation.

Yeah, it seems Mathematica doesn’t use any additional precision by default as I had naïvely assumed. I checked with Maxima with fpprec=100 and it is positive, so all looks good. Thanks!

from robust-orientation.

Another possible explanation for this inconsistency could be how mathematica interprets decimal encodings of 64 bit IEEE 754 numbers. If it unpacks them internally into a higher precision format, then there could be issues. Eg. 0.3f != 0.3 in C.

from robust-orientation.