This commit directly ports Shewchuk's public domain robust incircle predicate ( https://www.cs.cmu.edu/afs/cs/project/quake/public/code/predicates.c ) to Java as closely as possible and uses it for isInCircleRobust, thereby addressing #310 and (imho more thoroughly) achieve the motivation of #311 . One test is changed, assuming Shewchuk's robust predicates are the ground truth. Many of the existing tests produce calls with sufficiently pathological points to run into the lines past stage B (I'd say DD-arithmetic is effectively ~stage B/stage C).
Allocating so many arrays (past stage C) may look slow but the idea is that this almost never happens (in Shewchuk's original paper this happened 4 times out of ~7.2M calls in a degenerate dataset representing a tilted grid). Everything that is sampled from a continuous distribution with support covering some positive area should never go past the first error bound check, which is the fast double implementation. Almost everything coming from a distribution on a grid or circle or sth. like that should be caught in stage B or C.
I understand that this is borderline unreviewable. The implementation is intentionally as close as possible to Shewchuk's implementation and the idea is to enable review and potential future debugging by direct comparison to the source. The greatest deviation comes from the problem of Java having no macros and no references to primitives, so the respective functions return arrays instead. All of the ported methods from Shewchuk are private implementation details. Some of the arrays in stage D are initialized with values that are never used because the system will complain about potentially uninitialized use, e.g. axtbc, even though, this could never happen.
This commit directly ports Shewchuk's public domain robust incircle predicate ( https://www.cs.cmu.edu/afs/cs/project/quake/public/code/predicates.c ) to Java as closely as possible and uses it for isInCircleRobust, thereby addressing #310 and (imho more thoroughly) achieve the motivation of #311 . One test is changed, assuming Shewchuk's robust predicates are the ground truth. Many of the existing tests produce calls with sufficiently pathological points to run into the lines past stage B (I'd say DD-arithmetic is effectively ~stage B/stage C).
Allocating so many arrays (past stage C) may look slow but the idea is that this almost never happens (in Shewchuk's original paper this happened 4 times out of ~7.2M calls in a degenerate dataset representing a tilted grid). Everything that is sampled from a continuous distribution with support covering some positive area should never go past the first error bound check, which is the fast double implementation. Almost everything coming from a distribution on a grid or circle or sth. like that should be caught in stage B or C.
I understand that this is borderline unreviewable. The implementation is intentionally as close as possible to Shewchuk's implementation and the idea is to enable review and potential future debugging by direct comparison to the source. The greatest deviation comes from the problem of Java having no macros and no references to primitives, so the respective functions return arrays instead. All of the ported methods from Shewchuk are private implementation details. Some of the arrays in stage D are initialized with values that are never used because the system will complain about potentially uninitialized use, e.g.
axtbc, even though, this could never happen.