Less strict type requirements

[kahaaga]

Problem

When working with points in (low-ish) N-dimensional space, it is typical in Julia to represent these points by statically sized vectors using the SVector type from StaticArrays.jl. To pass these points on to MiniQhull.delaunay, I first have to gather the points, then convert them to a vector with column-major ordering, which is very slow.

using MiniQhull, StaticArrays
dim = 5
npts = 300
pts = [SVector{dim, Float64}(rand(dim) for i = 1:npts]

# Works, but is veery slow and allocates a lot of memory
x = Array(vcat(pts...,))
delaunay(dim, npts, x)

However, it is possible to reinterpret the points as a column-major vector with almost zero extra cost. But currently, using reinterpreted data doesn't work with MiniQhull.delaunay because it is hard-coded that the input points must be a Vector{Float64}.

using MiniQhull, StaticArrays
dim = 5
npts = 300
pts = [SVector{dim, Float64}(rand(dim) for i = 1:npts]

# This operation is fast/allocates almost nothing
x = reinterpret(Float64, pts) #`x` is now of type `Base.ReinterpretArray`

# Fails, because the input must be `Vector{Float64}`
delaunay(dim, npts, x)

# Works, but adds an additional costly conversion step 
delaunay(dim, npts, Vector{Float64(x))

In my applications, I work with a large number of points. Converting between data formats then quickly becomes computationally unfeasible, so it is crucial performance-wise to be able to not explicitly convert to Vector{Float64} before passing the data to delaunay.

I think this package would be more flexible if delaunay could accept any subtype of AbstractVector{Float64} as input data.

Solution

This PR solves the problem described above by having less strict type requirements (i.e. using AbstractVector/AbstractArray instead of Vector/Array). The current behaviour is not affected, but it is now possible to use Base.ReinterpretArray (and other similar types) as input.

Documentation

I added an extra use case to the documentation, similar to the examples above, highlighting how reinterpreted static vectors can be used as input to delaunay.

Other

This PR also includes the GitHub Actions CI testing that I added in a separate PR.

[codecov-io]

Codecov Report

Merging #13 (607c6c4) into master (a5271ea) will increase coverage by 2.87%. The diff coverage is 100.00%.

@@            Coverage Diff             @@
##           master      #13      +/-   ##
==========================================
+ Coverage   92.68%   95.55%   +2.87%     
==========================================
  Files           3        3              
  Lines          41       45       +4     
==========================================
+ Hits           38       43       +5     
+ Misses          3        2       -1     

Impacted Files	Coverage Δ
src/bindings.jl	100.00% <ø> (ø)
src/MiniQhull.jl	100.00% <100.00%> (ø)
src/load.jl	83.33% <0.00%> (+6.41%)	:arrow_up:

---

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update a5271ea...607c6c4. Read the comment docs.

[kahaaga]

Vector of vectors

I agree it is a good idea to accept vectors of vectors for representing the coordinates. I would do it in a slightly diferentment way than you have proposed.

I added a third method for vectors of vectors.

delaunay(points::AbstractVector{T}, flags::AbstractString) where T -> Matrix{Int32}

where T is some vector-like type. Behind the scenes, there are actually two delaunay(points, flags::AbstractString) -> Matrix{Int32} methods:

• one for a vector of tuples (and other similar types, like SVector), which has the same memory layout as a column-major vector and can be reintepreted without extra memory allocations
• one for vector of regular vectors (which need to explicitly be converted)

Was it something like this you had in mind?

Arbitrary types

We can also extend previous signatures to more arbitrary types.

In addition to what was already in the PR, I also added

delaunay(points::AbstractMatrix, flags::AbstractString) -> Matrix{Int32}

Tests

I added tests for three common use cases: representing points as Vector{Vector}, Vector{Tuple}, and Vector{SVector}.

Note: the dependency on StaticArrays.jl is only for the CI tests, and will not affect users installing the package.

Docstring

Finally, it would be nice to have access to the documentation directly from the REPL. I therefore added a docstring to the delaunay function.

[fverdugo]

Wow I am impressed! @kahaaga

Thanks for the good job!

[kahaaga]

Thanks for the good job!

And thanks for making this package to begin with! Now I can use QHull in my Julia packages without depending on python! 🎆