[BUG]: `k` not defined in local scope

[EdsterG]

Describe the bug

k is not defined here:

DelaunayTriangulation.jl/src/algorithms/point_location/jump_and_march.jl

Line 422 in 9134c8e

return (false, Cert.Outside, i, j, k)

and here:

DelaunayTriangulation.jl/src/algorithms/point_location/jump_and_march.jl

Line 448 in 9134c8e

return (false, Cert.Outside, i, j, k)

Reproducer

Anything snippet that hits those lines in the code.

Environment information

UndefVarError: `k` not defined in local scope
Suggestion: check for an assignment to a local variable that shadows a global of the same name.

Stacktrace:
  [1] search_right_down_adjacent_boundary_edges(...
  ...

[DanielVandH]

Thanks, it should be get_adjacent(tri, i, j) instead of k probably. I can try and fix it soon or if you want to make a PR that'd be helpful.

Did you have an actual example that ran into this? That would be ideal so that it could be used as a test - it's one of the main reasons I ask for a reproducer.

[EdsterG]

Unfortunately it was in a large run, I wasn’t able to narrow down a small example.

[DanielVandH]

Doesn't need to be any particularly small example. e.g. there are some examples in my tests that are many lines long just for a single test since finding these examples can be a bit tough.

[EdsterG]

I think this should do the trick, this was the input into WLGMakie:

[(1.0791812460476249, -3.7886681935906106), (1.0791812460476249, -4.4006006582615305), (1.0791812460476249, -5.012533122932451), (1.0791812460476249, -4.022405596275408), (1.0791812460476249, -4.634338060946328), (1.0791812460476249, -5.2462705256172475), (1.0791812460476249, -4.256142998960205), (1.0791812460476249, -4.868075463631126), (1.0791812460476249, -3.877947936974082), (1.0791812460476249, -4.489880401645002), (1.0791812460476249, -5.101812866315922), (1.0791812460476249, -4.111685339658881), (1.0791812460476249, -4.723617804329802), (1.0791812460476249, -3.7334902776727588), (1.0791812460476249, -4.345422742343679), (1.0791812460476249, -4.957355207014598), (1.0791812460476249, -3.967227680357556), (1.0791812460476249, -4.579160145028475), (1.0791812460476249, -5.191092609699395), (1.0791812460476249, -4.200965083042353), (1.0791812460476249, -4.8128975477132725)]

[DanielVandH]

julia> triangulate(points; randomise=false)
ERROR: UndefVarError: `k` not defined in local scope
Suggestion: check for an assignment to a local variable that shadows a global of the same name.
Stacktrace:
  [1] search_left_down_adjacent_boundary_edges(tri::Triangulation{…}, q::Tuple{…}, q_pos::DelaunayTriangulation.Certificate.T, predicates::AdaptiveKernel, store_history::Val{…}, history::Nothing, ghost_vertex::Int64, i::Int64, j::Int64, pⱼ::Tuple{…})
    @ DelaunayTriangulation C:\Users\djv23\.julia\packages\DelaunayTriangulation\oZmqW\src\algorithms\point_location\jump_and_march.jl:448
  [2] search_down_adjacent_boundary_edges(tri::Triangulation{…}, k::Int64, q::Tuple{…}, direction::DelaunayTriangulation.Certificate.T, q_pos::DelaunayTriangulation.Certificate.T, next_vertex::Int64, predicates::AdaptiveKernel, store_history::Val{…}, history::Nothing, ghost_vertex::Int64)
    @ DelaunayTriangulation C:\Users\djv23\.julia\packages\DelaunayTriangulation\oZmqW\src\algorithms\point_location\jump_and_march.jl:393
  [3] initialise_find_triangle_boundary_vertex(tri::Triangulation{…}, _q::Tuple{…}, k::Int64, predicates::AdaptiveKernel, store_history::Val{…}, history::Nothing, ghost_vertex::Int64, concavity_protection::Bool)
    @ DelaunayTriangulation C:\Users\djv23\.julia\packages\DelaunayTriangulation\oZmqW\src\algorithms\point_location\jump_and_march.jl:859
  [4] _find_triangle(tri::Triangulation{…}, q::Tuple{…}, k::Int64, store_history::Val{…}, history::Nothing, rng::Random.TaskLocalRNG, maxiters::Int64, cur_iter::Int64, concavity_protection::Bool, num_restarts::Int64, use_barriers::Val{…}, predicates::AdaptiveKernel)
    @ DelaunayTriangulation C:\Users\djv23\.julia\packages\DelaunayTriangulation\oZmqW\src\algorithms\point_location\jump_and_march.jl:1149
  [5] #find_triangle#142
    @ C:\Users\djv23\.julia\packages\DelaunayTriangulation\oZmqW\src\algorithms\point_location\jump_and_march.jl:772 [inlined]
  [6] add_point_bowyer_watson!(tri::Triangulation{…}, new_point::Int64, initial_search_point::Int64, rng::Random.TaskLocalRNG, predicates::AdaptiveKernel, update_representative_point::Bool, store_event_history::Val{…}, event_history::Nothing, peek::Val{…})
    @ DelaunayTriangulation C:\Users\djv23\.julia\packages\DelaunayTriangulation\oZmqW\src\algorithms\triangulation\unconstrained_triangulation.jl:154
  [7] add_point_bowyer_watson!
    @ C:\Users\djv23\.julia\packages\DelaunayTriangulation\oZmqW\src\algorithms\triangulation\unconstrained_triangulation.jl:152 [inlined]
  [8] unconstrained_triangulation!(tri::Triangulation{…}; predicates::AdaptiveKernel, randomise::Bool, try_last_inserted_point::Bool, skip_points::Tuple{}, num_sample_rule::typeof(DelaunayTriangulation.default_num_samples), rng::Random.TaskLocalRNG, insertion_order::Vector{…})
    @ DelaunayTriangulation C:\Users\djv23\.julia\packages\DelaunayTriangulation\oZmqW\src\algorithms\triangulation\unconstrained_triangulation.jl:462
  [9] unconstrained_triangulation!
    @ C:\Users\djv23\.julia\packages\DelaunayTriangulation\oZmqW\src\algorithms\triangulation\unconstrained_triangulation.jl:448 [inlined]
 [10] _triangulate!
    @ C:\Users\djv23\.julia\packages\DelaunayTriangulation\oZmqW\src\algorithms\triangulation\main.jl:174 [inlined]
 [11] triangulate(points::Vector{…}; segments::Nothing, boundary_nodes::Nothing, predicates::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 C:\Users\djv23\.julia\packages\DelaunayTriangulation\oZmqW\src\algorithms\triangulation\main.jl:156
 [12] top-level scope
    @ REPL[60]:1
Some type information was truncated. Use `show(err)` to see complete types.

Yep, that works. Note though that this is a very degenerate point set... all the $x$-coordinates are equal. I wouldn't be surprised if other things break even after this is fixed.

[EdsterG]

Yes, it is indeed degenerate. Though it seems possible to produce horizontal divisions (parallel to x-axis).

[DanielVandH]

Absolutely, it should still work but if something else comes up during the fix might take a while for me to get the changes in. I'll work on it soon.

[DanielVandH]

Made a quick start in #217 but it's a bit annoying to fix since you now run into

ERROR: The point, (1.0791812460476249, -5.2462705256172475), could not be located.
Stacktrace:
  [1] search_down_adjacent_boundary_edges(tri::Triangulation{…}, k::Int64, q::Tuple{…}, direction::DelaunayTriangulation.Certificate.T, q_pos::DelaunayTriangulation.Certificate.T, next_vertex::Int64, predicates::AdaptiveKernel, store_history::Val{…}, history::Nothing, ghost_vertex::Int64)
    @ DelaunayTriangulation C:\Users\djv23\.julia\dev\DelaunayTriangulation.jl\src\algorithms\point_location\jump_and_march.jl:396
  [2] initialise_find_triangle_boundary_vertex(tri::Triangulation{…}, _q::Tuple{…}, k::Int64, predicates::AdaptiveKernel, store_history::Val{…}, history::Nothing, ghost_vertex::Int64, concavity_protection::Bool)
    @ DelaunayTriangulation C:\Users\djv23\.julia\dev\DelaunayTriangulation.jl\src\algorithms\point_location\jump_and_march.jl:859
  [3] _find_triangle(tri::Triangulation{…}, q::Tuple{…}, k::Int64, store_history::Val{…}, history::Nothing, rng::TaskLocalRNG, maxiters::Int64, cur_iter::Int64, concavity_protection::Bool, num_restarts::Int64, use_barriers::Val{…}, predicates::AdaptiveKernel)
    @ DelaunayTriangulation C:\Users\djv23\.julia\dev\DelaunayTriangulation.jl\src\algorithms\point_location\jump_and_march.jl:1149
  [4] #find_triangle#142
    @ C:\Users\djv23\.julia\dev\DelaunayTriangulation.jl\src\algorithms\point_location\jump_and_march.jl:772 [inlined]
  [5] add_point_bowyer_watson!(tri::Triangulation{…}, new_point::Int64, initial_search_point::Int64, rng::TaskLocalRNG, predicates::AdaptiveKernel, update_representative_point::Bool, store_event_history::Val{…}, even    @ DelaunayTriangulation C:\Users\djv23\.julia\dev\DelaunayTriangulation.jl\src\algorithms\triangulation\unconstrained_triangulation.jl:154
  [6] add_point_bowyer_watson!
    @ C:\Users\djv23\.julia\dev\DelaunayTriangulation.jl\src\algorithms\triangulation\unconstrained_triangulation.jl:152 [inlined]
  [7] unconstrained_triangulation!(tri::Triangulation{…}; predicates::AdaptiveKernel, randomise::Bool, try_last_inserted_point::Bool, skip_points::Tuple{}, num_sample_rule::typeof(DelaunayTriangulation.default_num_samples), rng::TaskLocalRNG, insertion_order::Vector{…})
    @ DelaunayTriangulation C:\Users\djv23\.julia\dev\DelaunayTriangulation.jl\src\algorithms\triangulation\unconstrained_triangulation.jl:462
  [8] unconstrained_triangulation!
    @ C:\Users\djv23\.julia\dev\DelaunayTriangulation.jl\src\algorithms\triangulation\unconstrained_triangulation.jl:448 [inlined]
  [9] _triangulate!
    @ C:\Users\djv23\.julia\dev\DelaunayTriangulation.jl\src\algorithms\triangulation\main.jl:174 [inlined]
 [10] triangulate(points::Vector{…}; segments::Nothing, boundary_nodes::Nothing, predicates::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::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 C:\Users\djv23\.julia\dev\DelaunayTriangulation.jl\src\algorithms\triangulation\main.jl:156
 [11] top-level scope
    @ c:\Users\djv23\.julia\dev\DelaunayTriangulation.jl\test\point_location\jump_and_march.jl:771
Some type information was truncated. Use `show(err)` to see complete types.

since, with this point set, there really is no good definition of orientation or direction for any of the triangles / edges, which the point location algorithm is quite reliant on. I'll try and come back to this when I have time (could be a while since this seems a bit annoying sorry), or feel free to take a look yourself and I'm happy to help.

In the mean time, I would advise trying to avoid triangulating these types of point sets entirely. (If you are encountering this within tricontourf [guessing since you say this is from Makie] you could manually define the triangulation yourself and pass it to the triangulation kwarg, if I remember correctly, if you really can't avoid these point sets entirely.)

[EdsterG]

Awesome thanks! I might take a look myself when I get a chance.

[DanielVandH]

Just letting you know, I haven't forgotten about this. The few times I've come back to look at it keep getting a bit stuck on how to actually address this, so might still be delayed a bit.