[BUG]: Duplicate points not correctly handled when present in `boundary_nodes`

[dgleich]

Describe the bug

While translating paths from an SVG file, I encountered an odd issue with a repeated final point. Definitely, this could be flagged as 'user error', on the other hand, the failure doesn't seem to manifest as something obviously. wrong.

Reproducer

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

setup()
p1 = [(118.57716599999999, 28.538463999999994), (118.814236, 27.962729999999993), (119.435126, 27.759529999999994), (120.044726, 27.962729999999993), (120.30437599999999, 28.538463999999994), (120.044726, 29.114197999999995), (119.435126, 29.317397999999994), (118.814236, 29.114197999999995), (118.57716599999999, 28.538463999999994), (118.57716599999999, 28.538463999999994)]

boundary_points = [
    [p1],
]
boundary_nodes, points = convert_boundary_points_to_indices(boundary_points)
tri6 = triangulate(points; boundary_nodes)
refine!(tri6; max_area=1e-2get_area(tri6))
triplot(tri6, markersize=0.1)

Describe what you expected to obtain.

The last point is repeated twice. Removing it gives the right answer.

p1 = [(118.57716599999999, 28.538463999999994), (118.814236, 27.962729999999993), (119.435126, 27.759529999999994), (120.044726, 27.962729999999993), (120.30437599999999, 28.538463999999994), (120.044726, 29.114197999999995), (119.435126, 29.317397999999994), (118.814236, 29.114197999999995), (118.57716599999999, 28.538463999999994)]

boundary_points = [
[p1],
]
boundary_nodes, points = convert_boundary_points_to_indices(boundary_points)
tri6 = triangulate(points; boundary_nodes)
refine!(tri6; max_area=1e-2get_area(tri6))
triplot(tri6, markersize=0.1)

Environment information

Post the result of doing

using InteractiveUtils
julia> versioninfo()

Julia Version 1.11.2
Commit 5e9a32e7af2 (2024-12-01 20:02 UTC)
Build Info:
  Official https://julialang.org/ release
Platform Info:
  OS: macOS (x86_64-apple-darwin24.0.0)
  CPU: 16 × Intel(R) Xeon(R) W-2140B CPU @ 3.20GHz
  WORD_SIZE: 64
  LLVM: libLLVM-16.0.6 (ORCJIT, skylake-avx512)
Threads: 4 default, 0 interactive, 2 GC (on 16 virtual cores)
Environment:
  JULIA_EDITOR = code
  JULIA_NUM_THREADS = 4

and

using Pkg
Pkg.status()

Status `~/Dropbox/research/2025/03-12-website-logo/Project.toml`
  [927a84f5] DelaunayTriangulation v1.6.4
  [8f5d6c58] EzXML v1.2.0
  [ae8d54c2] Luxor v4.2.0

[DanielVandH]

Thanks for the issue! Technically yes this is "user error" but, it's probably closer to a bug since I actually do want to avoid duplicate points now as of #218. I assume the error you saw was

┌ Warning: There were duplicate points. Only one of each duplicate will be used, and all other duplicates will be skipped. The indices of the duplicates are:
│   (118.57716599999999, 28.538463999999994) at indices [1, 9]
│ To suppress this warning, call `DelaunayTriangulation.toggle_warn_on_dupes!()`.
└ @ DelaunayTriangulation C:\Users\djv23\.julia\packages\DelaunayTriangulation\P5U9H\src\algorithms\triangulation\check_args.jl:122
ERROR: StackOverflowError:
Stacktrace:
   [1] Array
     @ .\boot.jl:579 [inlined]
   [2] getindex
     @ .\array.jl:400 [inlined]
   [3] connect_segments!(segments::Vector{Tuple{Int64, Int64}})
     @ DelaunayTriangulation C:\Users\djv23\.julia\packages\DelaunayTriangulation\P5U9H\src\algorithms\triangulation\constrained_triangulation.jl:89
   [4] process_collinear_segments!(tri::DelaunayTriangulation.Triangulation{…}, e::Tuple{…}, collinear_segments::Vector{…}; predicates::DelaunayTriangulation.AdaptiveKernel, rng::Random.TaskLocalRNG)
     @ DelaunayTriangulation C:\Users\djv23\.julia\packages\DelaunayTriangulation\P5U9H\src\algorithms\triangulation\constrained_triangulation.jl:765
nayTriangulation.PolygonHierarchy{…}; rng::Random.TaskLocalRNG, delete_holes::Bool)
     @ DelaunayTriangulation C:\Users\djv23\.julia\packages\DelaunayTriangulation\P5U9H\src\algorithms\triangulation\constrained_triangulation.jl:835
 [657] constrained_triangulation!
     @ C:\Users\djv23\.julia\packages\DelaunayTriangulation\P5U9H\src\algorithms\triangulation\constrained_triangulation.jl:831 [inlined]
 [658] _triangulate!(tri::DelaunayTriangulation.Triangulation{…}, segments::Nothing, boundary_nodes::Vector{…}, predicates::DelaunayTriangulation.AdaptiveKernel, randomise::Bool, try_last_inserted_point::Bool, skip_points::Set{…}, num_sample_rule::Function, rng::Random.TaskLocalRNG, insertion_order::Vector{…}, recompute_representative_points::Bool, delete_holes::Bool, full_polygon_hierarchy::DelaunayTriangulation.PolygonHierarchy{…}, delete_ghosts::Bool, delete_empty_features::Bool)
     @ DelaunayTriangulation C:\Users\djv23\.julia\packages\DelaunayTriangulation\P5U9H\src\algorithms\triangulation\main.jl:181
Some type information was truncated. Use `show(err)` to see complete types.

which is a very nasty error. I think what I need to do is to check that the boundary_nodes doesn't contain the duplicate indices in a single segment of any boundary's curve and remove those. The stuff that handles checking for duplicate points is at

DelaunayTriangulation.jl/src/algorithms/triangulation/check_args.jl

Lines 102 to 126 in da9f582

	function has_unique_points!(skip_points, points)
	all_unique = points_are_unique(points)
	if !all_unique
	dup_seen = find_duplicate_points(points)
	if WARN_ON_DUPES[]
	io = IOBuffer()
	println(io, "There were duplicate points. Only one of each duplicate will be used, and all other duplicates will be skipped. The indices of the duplicates are:")
	end
	for (p, ivec) in dup_seen
	for j in 2:lastindex(ivec)
	push!(skip_points, ivec[j])
	end
	if WARN_ON_DUPES[]
	println(io, " ", p, " at indices ", ivec)
	end
	end
	if WARN_ON_DUPES[]
	println(io, "To suppress this warning, call `DelaunayTriangulation.toggle_warn_on_dupes!()`.")
	end
	if WARN_ON_DUPES[]
	@warn String(take!(io))
	end
	end
	return true
	end

but doesn't currently look at boundary_nodes at all.

I am quite busy this month but I can try and find some time to look into it, but no guarantees on any sort of timeline sorry... If you would like to try and fix it I'm more than happy to assist with that / review any PR, in case you are interested.

[dgleich]

Thanks -- I'll try and take a look soon to see if I can fix it.

[DanielVandH]

@dgleich: I realise now that I think I misunderstood your issue. My thought was that you were having an issue with your boundary nodes being something like

[p, p1, p2, p3, p4, q], but with p == q

but I think you are actually talking about wanting a case like

[p, p1, p2, p3, p4, p, p1]

(where instead of stopping at p, it continues onto p1) to work so that triangulate should just know to truncate the curve. Is that what you wanted?

I implemented a fix for the first case here #224 but I'm guessing now that it's irrelevant to what your issue here is...

For the case of handling things like [p, p1, p2, p4, p, p1], on #224 your current example gives

p1 = [(118.57716599999999, 28.538463999999994), (118.814236, 27.962729999999993), (119.435126, 27.759529999999994), (120.044726, 27.962729999999993), (120.30437599999999, 28.538463999999994), (120.044726, 29.114197999999995), (119.435126, 29.317397999999994), (118.814236, 29.114197999999995), (118.57716599999999, 28.538463999999994), (118.57716599999999, 28.538463999999994)]
boundary_points = [[p1]]
boundary_nodes, points = convert_boundary_points_to_indices(boundary_points)
tri6 = triangulate(points; boundary_nodes)
refine!(tri6; max_area=1e-2get_area(tri6))
triplot(tri6, markersize=0.1)

but the boundary isn't actually correct so the triangulation isn't Delaunay and it's broken in someways...

julia> validate_triangulation(tri6)
ERROR: KeyError: key (1, 2) not found
Stacktrace:
 [1] getindex
   @ .\dict.jl:477 [inlined]
 [2] get_boundary_edge_map
   @ C:\Users\djv23\.julia\dev\DelaunayTriangulation.jl\src\data_structures\triangulation\methods\boundary_edge_map.jl:10 [inlined]
 [3] test_boundary_nodes_matches_boundary_edge_map(tri::Triangulation{…})
   @ DelaunayTriangulation C:\Users\djv23\.julia\dev\DelaunayTriangulation.jl\src\validation.jl:577
 [4] BoundaryNodesBoundaryEdgeMapState
   @ C:\Users\djv23\.julia\dev\DelaunayTriangulation.jl\src\validation.jl:554 [inlined]
 [5] DelaunayTriangulation.TriangulationState(tri::Triangulation{…}; predicates::ExactKernel)
   @ DelaunayTriangulation C:\Users\djv23\.julia\dev\DelaunayTriangulation.jl\src\validation.jl:874
 [6] TriangulationState
   @ C:\Users\djv23\.julia\dev\DelaunayTriangulation.jl\src\validation.jl:869 [inlined]
 [7] validate_triangulation(tri::Triangulation{…}; print_result::Bool, predicates::ExactKernel)
   @ DelaunayTriangulation C:\Users\djv23\.julia\dev\DelaunayTriangulation.jl\src\validation.jl:929
 [8] validate_triangulation(tri::Triangulation{…})
   @ DelaunayTriangulation C:\Users\djv23\.julia\dev\DelaunayTriangulation.jl\src\validation.jl:928
 [9] top-level scope
   @ REPL[4]:1
Some type information was truncated. Use `show(err)` to see complete types.

Honestly I'm perplexed as to how refine! didn't crash/overflow somewhere or that triplot even worked. It's possible that this might still be something you can work around with your application I guess now that it actually does run.

I don't know that I would want to make triangulate automatically trim the boundary curves to be correct, I try to avoid so much post processing like that since it might give the expectation to the user that I also post-process e.g. self-intersections which I don't currently. Also because really [p, p1, p2, p3, p4, p, p1] and [p, p1, p2, p3, p4, p] are not really the same curve.