[BUG]: triangulation either lasts forever or fails with this dataset

[asinghvi17]

Describe the bug

If I try to triangulate this using triangulate(tuple.(lon, lat)), then it just keeps running. With Makie.tricontourf(lon, lat, data) it terminates with a stack overflow within the triangulation.

Reproducer

Give a minimal working example of your bug here, e.g. something like

using HDF5
ds = h5open("test.hdf5")
lon = collect(ds["lon"])
lat = collect(ds["lat"])
data = collect(ds["data"])

import Delaunator
import DelaunayTriangulation

Delaunator.triangulate(tuple.(lon, lat)) # works fine

DelaunayTriangulation.triangulate(tuple.(lon, lat)) # keeps running indefinitely

DelaunayTriangulation.triangulate(tuple.(lon, lat); randomise = false) # fails with the error below

julia> tricontourf(lon, lat, data)
ERROR: StackOverflowError:
Stacktrace:
  [1] dig_cavity!(tri::DelaunayTriangulation.Triangulation{…}, r::Int64, i::Int64, j::Int64, ℓ::Int64, flag::DelaunayTriangulation.Certificate.T, V::Tuple{…}, store_event_history::Val{…}, event_history::Nothing, peek::Val{…}, predicates::DelaunayTriangulation.AdaptiveKernel)
    @ DelaunayTriangulation ~/.julia/packages/DelaunayTriangulation/P5U9H/src/algorithms/triangulation/unconstrained_triangulation.jl:341
  [2] dig_cavity!(tri::DelaunayTriangulation.Triangulation{…}, r::Int64, i::Int64, j::Int64, ℓ::Int64, flag::DelaunayTriangulation.Certificate.T, V::Tuple{…}, store_event_history::Val{…}, event_history::Nothing, peek::Val{…}, predicates::DelaunayTriangulation.AdaptiveKernel)
    @ DelaunayTriangulation ~/.julia/packages/DelaunayTriangulation/P5U9H/src/algorithms/triangulation/unconstrained_triangulation.jl:351
  [3] dig_cavity!(tri::DelaunayTriangulation.Triangulation{…}, r::Int64, i::Int64, j::Int64, ℓ::Int64, flag::DelaunayTriangulation.Certificate.T, V::Tuple{…}, store_event_history::Val{…}, event_history::Nothing, peek::Val{…}, predicates::DelaunayTriangulation.AdaptiveKernel) (repeats 380 times)
    @ DelaunayTriangulation ~/.julia/packages/DelaunayTriangulation/P5U9H/src/algorithms/triangulation/unconstrained_triangulation.jl:352
  [4] add_point_bowyer_watson_dig_cavities!(tri::DelaunayTriangulation.Triangulation{…}, new_point::Int64, V::Tuple{…}, q::Tuple{…}, flag::DelaunayTriangulation.Certificate.T, update_representative_point::Bool, store_event_history::Val{…}, event_history::Nothing, peek::Val{…}, predicates::DelaunayTriangulation.AdaptiveKernel)
    @ DelaunayTriangulation ~/.julia/packages/DelaunayTriangulation/P5U9H/src/algorithms/triangulation/unconstrained_triangulation.jl:226
  [5] add_point_bowyer_watson_after_found_triangle!
    @ ~/.julia/packages/DelaunayTriangulation/P5U9H/src/algorithms/triangulation/unconstrained_triangulation.jl:183 [inlined]
  [6] add_point_bowyer_watson_and_process_after_found_triangle!
    @ ~/.julia/packages/DelaunayTriangulation/P5U9H/src/algorithms/triangulation/unconstrained_triangulation.jl:167 [inlined]
  [7] add_point_bowyer_watson!(tri::DelaunayTriangulation.Triangulation{…}, new_point::Int64, initial_search_point::Int64, rng::Random.TaskLocalRNG, predicates::DelaunayTriangulation.AdaptiveKernel, update_representative_point::Bool, store_event_history::Val{…}, event_history::Nothing, peek::Val{…})
    @ DelaunayTriangulation ~/.julia/packages/DelaunayTriangulation/P5U9H/src/algorithms/triangulation/unconstrained_triangulation.jl:160
  [8] add_point_bowyer_watson!
    @ ~/.julia/packages/DelaunayTriangulation/P5U9H/src/algorithms/triangulation/unconstrained_triangulation.jl:152 [inlined]
  [9] unconstrained_triangulation!(tri::DelaunayTriangulation.Triangulation{…}; predicates::DelaunayTriangulation.AdaptiveKernel, randomise::Bool, try_last_inserted_point::Bool, skip_points::Set{…}, num_sample_rule::typeof(DelaunayTriangulation.default_num_samples), rng::Random.TaskLocalRNG, insertion_order::Vector{…})
    @ DelaunayTriangulation ~/.julia/packages/DelaunayTriangulation/P5U9H/src/algorithms/triangulation/unconstrained_triangulation.jl:462
 [10] unconstrained_triangulation!
    @ ~/.julia/packages/DelaunayTriangulation/P5U9H/src/algorithms/triangulation/unconstrained_triangulation.jl:448 [inlined]
 [11] _triangulate!
    @ ~/.julia/packages/DelaunayTriangulation/P5U9H/src/algorithms/triangulation/main.jl:179 [inlined]
 [12] triangulate(points::Matrix{…}; segments::Nothing, boundary_nodes::Nothing, predicates::DelaunayTriangulation.AdaptiveKernel, weights::DelaunayTriangulation.ZeroWeight{…}, IntegerType::Type{…}, EdgeType::Type{…}, TriangleType::Type{…}, EdgesType::Type{…}, TrianglesType::Type{…}, randomise::Bool, delete_ghosts::Bool, delete_empty_features::Bool, try_last_inserted_point::Bool, skip_points::Tuple{}, num_sample_rule::typeof(DelaunayTriangulation.default_num_samples), rng::Random.TaskLocalRNG, insertion_order::Vector{…}, recompute_representative_points::Bool, delete_holes::Bool, check_arguments::Bool, full_polygon_hierarchy::Nothing, boundary_enricher::Nothing, boundary_curves::Tuple{}, polygonise_n::Int64, coarse_n::Int64, enrich::Bool)
    @ DelaunayTriangulation ~/.julia/packages/DelaunayTriangulation/P5U9H/src/algorithms/triangulation/main.jl:161
 [13] triangulate
    @ ~/.julia/packages/DelaunayTriangulation/P5U9H/src/algorithms/triangulation/main.jl:118 [inlined]
 [14] convert_arguments(::Type{…}, x::Vector{…}, y::Vector{…}, z::Vector{…}; triangulation::Makie.DelaunayTriangulation)
    @ Makie ~/.julia/dev/makie/Makie.jl/src/basic_recipes/tricontourf.jl:68

I checked and there are no duplicate points (length(unique(tuple.(lon, lat))) == length(lon) == length(lat).

I had to upload this as a zip because Github doesn't accept HDF5, you will have to unzip locally.

test.hdf5.zip

Environment information

I'm on Julia v1.11.5, DelaunayTriangulation v1.6.4.