Problematic polygon for simplexify

[juliohm]

The first row of this geotable has MultiPolygon geometry. The simplexify function is reaching the recursion limit of the Dehn1899 algorithm in the first Polygon of this MultiPolygon:

using GeoIO
using Meshes

multipoly = GeoIO.load("andlucia.geojson").geometry[1]

poly1 = parent(multipoly)[1]

simplexify(poly1)

ERROR: StackOverflowError:
Stacktrace:
   [1] _sort!(v::Vector{…}, a::Base.Sort.ScratchQuickSort{…}, o::Base.Order.Perm{…}, kw::@NamedTuple{…}; t::Vector{…}, offset::Int64, swap::Bool, rev::Bool)
     @ Base.Sort ./sort.jl:1063
   [2] _sort!(v::Vector{…}, a::Base.Sort.ScratchQuickSort{…}, o::Base.Order.Perm{…}, kw::@NamedTuple{…}; t::Vector{…}, offset::Int64, swap::Bool, rev::Bool)
     @ Base.Sort ./sort.jl:1098
   [3] _sort!(v::Vector{…}, a::Base.Sort.ScratchQuickSort{…}, o::Base.Order.Perm{…}, kw::@NamedTuple{…}; t::Vector{…}, offset::Int64, swap::Bool, rev::Bool)
     @ Base.Sort ./sort.jl:1094
   [4] _sort!(v::Vector{…}, a::Base.Sort.ScratchQuickSort{…}, o::Base.Order.Perm{…}, kw::@NamedTuple{…}; t::Vector{…}, offset::Int64, swap::Bool, rev::Bool) (repeats 3 times)
     @ Base.Sort ./sort.jl:1098
   [5] _sort!(v::Vector{…}, a::Base.Sort.ScratchQuickSort{…}, o::Base.Order.Perm{…}, kw::@NamedTuple{…}; t::Vector{…}, offset::Int64, swap::Bool, rev::Bool) (repeats 2 times)
     @ Base.Sort ./sort.jl:1094
   [6] _sort!
     @ Base.Sort ./sort.jl:1063 [inlined]
--- the last 2 lines are repeated 1 more time ---
   [9] _sort!(v::Vector{…}, a::Base.Sort.StableCheckSorted{…}, o::Base.Order.Perm{…}, kw::@NamedTuple{…})
     @ Base.Sort ./sort.jl:1131
  [10] _sort!
     @ Base.Sort ./sort.jl:730 [inlined]
  [11] _sort!
     @ Base.Sort ./sort.jl:681 [inlined]
  [12] _sort!
     @ Base.Sort ./sort.jl:752 [inlined]
  [13] _sort!
     @ Base.Sort ./sort.jl:697 [inlined]
  [14] _sort!
     @ Base.Sort ./sort.jl:636 [inlined]
  [15] #sort!#28
     @ ./sort.jl:1463 [inlined]
  [16] sort!
     @ ./sort.jl:1456 [inlined]
  [17] #_sortperm#33
     @ ./sort.jl:1664 [inlined]
  [18] _sortperm
     @ ./sort.jl:1651 [inlined]
  [19] #sortperm#32
     @ ./sort.jl:1648 [inlined]
  [20] sortperm
     @ ./sort.jl:1637 [inlined]
  [21] dehn1899(v::Vector{Point2f}, inds::Vector{Int64})
     @ Meshes ~/.julia/dev/Meshes/src/discretization/dehn.jl:40
  [22] dehn1899(v::Vector{Point2f}, inds::Vector{Int64}) (repeats 296 times)
     @ Meshes ~/.julia/dev/Meshes/src/discretization/dehn.jl:69
  [23] dehn1899(v::Vector{Point2f}, inds::Vector{Int64})
     @ Meshes ~/.julia/dev/Meshes/src/discretization/dehn.jl:68
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
--- the last 2 lines are repeated 1 more time ---
 [144] dehn1899(v::Vector{Point2f}, inds::Vector{Int64}) (repeats 1517 times)
     @ Meshes ~/.julia/dev/Meshes/src/discretization/dehn.jl:69
--- the last 1 lines are repeated 1 more time ---
 [146] discretizewithin(ring::Ring{2, Float32, CircularArrays.CircularVector{Point2f, Vector{Point2f}}}, ::Dehn1899)
     @ Meshes ~/.julia/dev/Meshes/src/discretization/dehn.jl:29
 [147] discretize(polygon::PolyArea{2, Float32, Ring{2, Float32, CircularArrays.CircularVector{…}}}, method::Dehn1899)
     @ Meshes ~/.julia/dev/Meshes/src/discretization.jl:55
 [148] simplexify(poly::PolyArea{2, Float32, Ring{2, Float32, CircularArrays.CircularVector{Point2f, Vector{Point2f}}}})
     @ Meshes ~/.julia/dev/Meshes/src/discretization.jl:167
Some type information was truncated. Use `show(err)` to see complete types.

We need to pick a different discretization method depending on the number of vertices of the polygon. In this case, we can call FIST instead of Dehn1899.

[juliohm]

I replaced Dehn1899 by FIST in the case the polygon has more than 5k vertices: a50136a

Now we need to optimize our FIST implementation to be able to handle 33k vertices.

[juliohm]

I will close this issue, and add a comment to #488 regarding FIST.