Eliminate allocations of `vertices` in `Multi` geometries

[juliohm]

The current implementation currently allocates:

Meshes.jl/src/geometries/multigeom.jl

Line 53 in 42f8543

vertices(m::MultiPolytope) = [vertex for geom in m.geoms for vertex in vertices(geom)]

We need a quick fix for that.

[ghyatzo]

assuming homogeneous multigeometries (multiple geometries all of the same type, like a triangle mesh)
we can do something like this:

julia> function myvertices(m::Multi) #with some kind of parametric type constraint
           N = mapreduce(nvertices, +, m.geoms) # compile is smart enough to constant propagate this away.
           k = nvertices(eltype(m.geoms))
           ntuple(i -> vertices(m.geoms[ceil(Int, i/k)])[1 + i % k], Val(N))
       end
myvertices (generic function with 1 method)

julia> m
MultiTriangle{2,Float64}
├─ Triangle((0.550249, 0.314319), (0.657976, 0.225926), (0.743882, 0.414126))
├─ Triangle((0.0381363, 0.475113), (0.745496, 0.223022), (0.922711, 0.0582245))
├─ Triangle((0.868872, 0.000274105), (0.217163, 0.322933), (0.354929, 0.543288))
└─ Triangle((0.890692, 0.383539), (0.482963, 0.218332), (0.167305, 0.309235))

julia> @btime myvertices($m);
  120.630 ns (2 allocations: 240 bytes)

julia> @btime vertices($m);
  323.735 ns (4 allocations: 960 bytes)

still allocates, but much less. ( I think it can be made completely non allocating, but couldn't find how).
Also, it returns a tuple instead of a vector, that might be a breaking change? But I thought it was fitting since normal vertices returns a tuple.

For a general case of completely arbitrary multi geometry I couldn't think of a way to avoid looping over all the geometries. If you know that all are a fixed size, other than knowing the total number of vertices, you also know where to look for each vertex.

[juliohm]

Thank you for the suggestions. We will review the return type of all vertices methods and will then decide what to do in general.

[juliohm]

All vertices methods currently return AbstractVector, except for the method with Ngon, which returns a NTuple. One way to make the output more homogeneous is to return SVector instead. We can then look into the method with Multi to return a lazy vector.

[juliohm]

After some discussion on Zulip, we came up with a backward compatible solution. We will make sure that vertices always returns an AbstractVector, possibly allocating in the case of Multi, and will introduce a new API function vertexiterator (or similar name) that returns an iterator of vertices instead.

This idea of iterator vs vector comes up all the time, so we better have both implemented.

[juliohm]

Closing in favor of #1131