# How to find the closest mesh to a specific markups point (algorithm , idea )

Operating system: window 10
Slicer version: 5.2.1

hi Slicer users

I want to get only the position value of the inner mesh closest to the center point of this mesh. Can anyone recommend an idea or algorithm?

Assuming that the center point will always be closer to the inner mesh than to the outer mesh (or if your mesh has been splitted/segmented beforehand), you could build a KD-Tee (VTK: vtkKdTree Class Reference) and query the tree for the closest point (VTK: vtkKdTree Class Reference). A C++ example of this can be found here (https://kitware.github.io/vtk-examples/site/Cxx/DataStructures/KdTree/). This example is easily translatable to python and can be used within Slicer.

2 Likes

Hi again @RafaelPalomar

I implemented what you said in Python, but as a result, it seems that only one mesh point closest to the center point is obtained.

Is there any way to get all points of the inner mesh?

``````# set kD-tree via mesh
mesh_center_pos =[0,0,0]
node_in_scene = slicer.mrmlScene.GetNodesByClass('vtkMRMLModelNode')

for value in node_in_scene:

node_name = value.GetName()

crown_node = getNode(node_name)
mesh = crown_node.GetMesh()

# make kdtree for mesh data
points = mesh.GetPoints()
k_Dtree = vtk.vtkKdTree()
k_Dtree.BuildLocatorFromPoints(points)

# cal mesh's center point
for value in range(mesh.GetNumberOfPoints()):
mesh_center_pos[0] += mesh.GetPoint(value)[0]
mesh_center_pos[1] += mesh.GetPoint(value)[1]
mesh_center_pos[2] += mesh.GetPoint(value)[2]

mesh_center_pos[0] /= mesh.GetNumberOfPoints()
mesh_center_pos[1] /= mesh.GetNumberOfPoints()
mesh_center_pos[2] /= mesh.GetNumberOfPoints()

# check mesh's center point
slicer.modules.markups.logic().AddControlPoint(mesh_center_pos[0], mesh_center_pos[1] , mesh_center_pos[2])

p_distance = vtk.reference(0.5)
inner_mesh_pos = k_Dtree.FindClosestPoint( mesh_center_pos, p_distance)

closet_pos = mesh.GetPoint(inner_mesh_pos)
# check closet point from mesh's center point
slicer.modules.markups.logic().AddControlPoint(closet_pos[0], closet_pos[1] , closet_pos[2])

``````

You could use vtkKDTree to query for N closest points (VTK: vtkKdTree Class Reference) or even find points within a radius (VTK: vtkKdTree Class Reference)

If you want to discriminate what you call â€śinner meshâ€ť and â€śouter meshâ€ť, you probably need to be more specific about what criteria these points should meet to be considered inner or outer; with arbitrary geometries, I would think distance alone wonâ€™t be sufficient.

1 Like