incircle issues

[DanielVandH]

Looking into some issues with AdaptivePredicates.jl and noticed some things. They're also in the incircle of this repo so I'll forward them onto here for you.

With bounds checks on, there can be BoundsErrors (this is why I have safe_getindex in the AdaptivePredicates.jl code)

julia> using Delaunator

julia> (pa, pb, pc, pd) = ((-2.1805754507765765e45, -9.077393688127387e59), (5.60747804973906e23, 9.578697981336844e8), (-2.407029693684877e-15, -2.2237653047058956e23), (6.899627924251412e-14, 3.4680080890995206e58))
((-2.1805754507765765e45, -9.077393688127387e59), (5.60747804973906e23, 9.578697981336844e8), (-2.407029693684877e-15, -2.2237653047058956e23), (6.899627924251412e-14, 3.4680080890995206e58))

julia> Delaunator.incircle(pa, pb, pc, pd)
ERROR: BoundsError: attempt to access NTuple{32, Float64} at index [33]
Stacktrace:
 [1] setindex
   @ .\tuple.jl:57 [inlined]
 [2] setindex!!
   @ C:\Users\danjv\.julia\packages\Delaunator\pbsdL\src\robust.jl:348 [inlined]
 [3] fast_expansion_sum_zeroelim
   @ C:\Users\danjv\.julia\packages\Delaunator\pbsdL\src\robust.jl:468 [inlined]
 [4] fast_expansion_sum_zeroelim
   @ C:\Users\danjv\.julia\packages\Delaunator\pbsdL\src\robust.jl:394 [inlined]
 [5] _incircleadapt_round1(pa::Tuple{…}, pb::Tuple{…}, pc::Tuple{…}, pd::Tuple{…}, permanent::Float64, cache::Nothing)
   @ Delaunator C:\Users\danjv\.julia\packages\Delaunator\pbsdL\src\robust.jl:517
 [6] incircle(pa::Tuple{…}, pb::Tuple{…}, pc::Tuple{…}, pd::Tuple{…}, cache::Nothing)
   @ Delaunator C:\Users\danjv\.julia\packages\Delaunator\pbsdL\src\robust.jl:216
 [7] incircle(pa::Tuple{…}, pb::Tuple{…}, pc::Tuple{…}, pd::Tuple{…})
   @ Delaunator C:\Users\danjv\.julia\packages\Delaunator\pbsdL\src\robust.jl:184
 [8] top-level scope
   @ REPL[21]:1
Some type information was truncated. Use `show(err)` to see complete types.

These BoundsErrors are also in the original C code except it's just undefined behavior.

The main reason I noticed this case is that, with bounds check off so that the above doesn't happen (and so you rely on the same undefined behavior), you get

julia> (pa, pb, pc, pd) = ((-2.1805754507765765e45, -9.077393688127387e59), (5.60747804973906e23, 9.578697981336844e8), (-2.407029693684877e-15, -2.2237653047058956e23), (6.899627924251412e-14, 3.4680080890995206e58))
((-2.1805754507765765e45, -9.077393688127387e59), (5.60747804973906e23, 9.578697981336844e8), (-2.407029693684877e-15, -2.2237653047058956e23), (6.899627924251412e-14, 3.4680080890995206e58))

julia> Delaunator.incircle(pa, pb, pc, pd)
ERROR: UndefVarError: `bdxtail` not defined
Stacktrace:
 [1] _incircleadapt_round1(pa::Tuple{…}, pb::Tuple{…}, pc::Tuple{…}, pd::Tuple{…}, permanent::Float64, cache::Nothing)
   @ Delaunator C:\Users\danjv\.julia\packages\Delaunator\pbsdL\src\robust.jl:607
 [2] incircle(pa::Tuple{…}, pb::Tuple{…}, pc::Tuple{…}, pd::Tuple{…}, cache::Nothing)
   @ Delaunator C:\Users\danjv\.julia\packages\Delaunator\pbsdL\src\robust.jl:216
 [3] incircle(pa::Tuple{…}, pb::Tuple{…}, pc::Tuple{…}, pd::Tuple{…})
   @ Delaunator C:\Users\danjv\.julia\packages\Delaunator\pbsdL\src\robust.jl:184
 [4] top-level scope
   @ REPL[7]:1
Some type information was truncated. Use `show(err)` to see complete types.

This is because finlength and ablength won't actually stop right at 32. Even in the original C code this happens, it can just keep counting for a little bit longer (e.g. ablen can go up to alen+blen which is 34 in this example, and indeed ablen==34, and finlength can go up to ablen+clen=51, but finlength = 43 here). So the checks

ablen == 32 || finlength == 32 

might be problematic and should be >= 32 ||. Alternatively, maybe a check could be added to fast_expansion_sum_zeroelim to return when hindex >= length(h). Dunno.

[DanielVandH]

I think also the first check

ablen < 32 || finlength < 32

should be && instead of ||? && passes the tests in AdaptivePredicates.jl but there are some failures with ||.

[DanielVandH]

JuliaGeometry/AdaptivePredicates.jl#21 fixed the issue you raised in the original issue and those I mentioned here. Feel free to modify the code here based on that if you want to.