Understanding how KNearestSearch works

xiaoming · March 7, 2024, 1:35pm

I have a surface in three-dimensional space composed of triangles generated by Meshes.jl. Given a point in space, the function ‘search’ in Meshes.jl can find the closest triangle to this point. I want to know how this distance is measured, how the algorithm is implemented, and it would be even better if someone could provide some reference materials.

juliohm · March 7, 2024, 1:42pm

Everything is open-source, you can read the source code to learn more, it is simple Julia code:

github.com

JuliaGeometry/Meshes.jl/blob/master/src/neighborsearch/knearest.jl

# ------------------------------------------------------------------
# Licensed under the MIT License. See LICENSE in the project root.
# ------------------------------------------------------------------

"""
    KNearestSearch(domain, k; metric=Euclidean())

A method for searching `k` nearest neighbors in `domain`
according to `metric`.
"""
struct KNearestSearch{D<:Domain,T} <: BoundedNeighborSearchMethod
  # input fields
  domain::D
  k::Int

  # state fields
  tree::T
end

function KNearestSearch(domain::D, k::Int; metric=Euclidean()) where {D<:Domain}

This file has been truncated. show original

We use the NearestNeighbors.jl package and compute the distance to the centroid of the triangles. There are options to control the distance used, number of neighbors, etc.

xiaoming · March 7, 2024, 1:46pm

Thanks! I will check that.

juliohm · March 7, 2024, 2:09pm

Feel free to ask these user questions in our Zulip channel. We sometimes miss posts in Discourse.

xiaoming · March 7, 2024, 2:39pm

OK. I am glad to join the channel.

cormullion · March 7, 2024, 3:15pm