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

**URL:** <https://discourse.slicer.org/t/how-to-find-the-closest-mesh-to-a-specific-markups-point-algorithm-idea/27715>\
**Category:** Development\
**Tags:** python\
**Created:** [February 9, 2023, 4:25am UTC](https://discourse.slicer.org/t/how-to-find-the-closest-mesh-to-a-specific-markups-point-algorithm-idea/27715 "2023-02-09T04:25:32Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![dsa934](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.slicer.org/dsa934/32/17907_2.png) [@dsa934](https://discourse.slicer.org/u/dsa934)\
**Post date:** [February 9, 2023, 4:25am UTC](https://discourse.slicer.org/t/how-to-find-the-closest-mesh-to-a-specific-markups-point-algorithm-idea/27715/1 "2023-02-09T04:25:32Z")

</div>

Operating system: window 10  
Slicer version: 5.2.1

hi Slicer users

 ![image](https://us1.discourse-cdn.com/flex002/uploads/slicer/original/3X/9/3/93322a162c74d175824394fa25daa2617e64104c.png)

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?

---

<div class="post-metadata">

**Author:** ![RafaelPalomar](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.slicer.org/rafaelpalomar/32/1436_2.png) [@RafaelPalomar](https://discourse.slicer.org/u/RafaelPalomar)\
**Post date:** [February 9, 2023, 5:12am UTC](https://discourse.slicer.org/t/how-to-find-the-closest-mesh-to-a-specific-markups-point-algorithm-idea/27715/2 "2023-02-09T05:12:43Z")

</div>

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](https://vtk.org/doc/nightly/html/classvtkKdTree.html)) and query the tree for the closest point ([VTK: vtkKdTree Class Reference](https://vtk.org/doc/nightly/html/classvtkKdTree.html#af5cabd7f0482765792d376ca70b25dd8)). A C++ example of this can be found here ([https://kitware.github.io/vtk-examples/site/Cxx/DataStructures/KdTree/](https://kitware.github.io/vtk-examples/site/Cxx/DataStructures/KdTree/)). This example is easily translatable to python and can be used within Slicer.

---

<div class="post-metadata">

**Author:** ![dsa934](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.slicer.org/dsa934/32/17907_2.png) [@dsa934](https://discourse.slicer.org/u/dsa934)\
**Post date:** [February 9, 2023, 7:38am UTC](https://discourse.slicer.org/t/how-to-find-the-closest-mesh-to-a-specific-markups-point-algorithm-idea/27715/4 "2023-02-09T07:38:41Z")

</div>

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?

```auto
# 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])

```

---

<div class="post-metadata">

**Author:** ![RafaelPalomar](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.slicer.org/rafaelpalomar/32/1436_2.png) [@RafaelPalomar](https://discourse.slicer.org/u/RafaelPalomar)\
**Post date:** [February 9, 2023, 11:32am UTC](https://discourse.slicer.org/t/how-to-find-the-closest-mesh-to-a-specific-markups-point-algorithm-idea/27715/5 "2023-02-09T11:32:08Z")

</div>

> [@dsa934](#):
>
> Is there any way to get all points of the inner mesh?

You could use vtkKDTree to query for _N closest points_ ([VTK: vtkKdTree Class Reference](https://vtk.org/doc/nightly/html/classvtkKdTree.html#af5cabd7f0482765792d376ca70b25dd8)) or even find _points within a radius_ ([VTK: vtkKdTree Class Reference](https://vtk.org/doc/nightly/html/classvtkKdTree.html#a7dc6bd5104cb90f333f0985e6f142446))

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.