BinnedPointList

mutable struct BinnedPointList{T}

Binned point list structure allowing for fast check for already existing points.

This provides better performance for indendifying already inserted points than the naive linear search.

OTOH the implementation is still quite naive - it dynamically maintains a cuboid binning region with a fixed number of bins.

Probably tree based adaptive methods (a la octree) will be more efficient, however they will be harder to implement.

In an ideal world, we would maintain a dynamic Delaunay triangulation, which at once could be the starting point of mesh generation which will follow here anyway.

• dim::Int32: Space dimension

• tol::Any: Point distance tolerance. Points closer than tol (in Euclidean distance) will be identified, i.e. are collapsed to the first inserted.

• binning_region_min::Vector: " The union of all bins is the binning region - a cuboid given by two of its corners. It is calculated dynamically depending on the inserted points.

• binning_region_max::Vector

• binning_region_increase_factor::Any: Increase factor of binning region (with respect to the cuboid defined by the coordinates of the binned points)

• points::ElasticArrays.ElasticArray{T, 2, M, V} where {T, M, V<:DenseVector{T}}: The actual point list

• bins::Array{Vector{Int32}}: The bins are vectors of indices of points in the point list We store them in a dim-dimensional array of length "numberofdirectional_bins^dim"

• number_of_directional_bins::Int32: Number of bins in each space dimension

• unbinned::Vector{Int32}: Some points will fall outside of the binning region. We collect them in vector of ubinned point indices

• num_allowed_unbinned_points::Int32: Number of unbinned points tolerated without rebinning

• max_unbinned_ratio::Any: Maximum ratio of unbinned points in point list

• current_bin::Vector{Int32}: Storage of current point bin

findpoint(binnedpointlist, p)

Find point in binned point list. Return its index in the point list if found, otherwise return 0.

 Base.insert!(binnedpointlist,p)

If another point with distance less the tol from p is in pointlist, return its index. Otherwise, insert point into pointlist. p may be a vector or a tuple.

 Base.insert!(binnedpointlist,x)

Insert 1D point via coordinate.

 Base.insert!(binnedpointlist,x,y,z)

Insert 3D point via coordinates.

_findpoint(binnedpointlist, index, p)

Find point in index list (by linear search) Return its index, or zero if not found

_bin_of_point!(binnedpointlist, p)

Calculate the bin of the point. Result is stored in bpl.current_bin

_rebin_all_points!(bpl)

Re-calculate binning if there are too many unbinned points This amounts to two steps:

• Enlarge binning area in order to include all points
• Re-calculate all point bins

naiveinsert(binnedpointlist, p)

Insert via linear search, without any binning. Just for being able to check of all of the above was worth the effort...