KDTree Find The Closest Distance From Test Point To Points Set

We had used vtkImplicitPolyDataDistance to calculate the distance from a point to the target points set in the post Calculate Distance From A Point To PolyData In VTK.
We will try a new way using KD-Tree to find the closest point to the test point.
The following example puts a sphere that radius is 1 and origin is (0, 0, 0) in the renderer. Our test point is (1.5, 0, 0), so the ideal distance is 0.5.

#include <vtkVersion.h>
#include <vtkImplicitPolyDataDistance.h>
#include <vtkActor.h>
#include <vtkFloatArray.h>
#include <vtkPointData.h>
#include <vtkPolyDataMapper.h>
#include <vtkProperty.h>
#include <vtkRenderer.h>
#include <vtkRenderWindow.h>
#include <vtkRenderWindowInteractor.h>
#include <vtkSmartPointer.h>
#include <vtkSphereSource.h>
#include <vtkVertexGlyphFilter.h>
#include <vtkLineSource.h>
#include <vtkKdTree.h>

#include "../vtkLearn/tool.h"

int main(int, char *[])
{
    vtkSmartPointer<vtkSphereSource> sphereSource =
    vtkSmartPointer<vtkSphereSource>::New();
    sphereSource->SetCenter(0.0, 0.0, 0.0);
    sphereSource->SetRadius(1.0f);
    sphereSource->Update();

    vtkSmartPointer<vtkPolyDataMapper> sphereMapper =
    vtkSmartPointer<vtkPolyDataMapper>::New();
    sphereMapper->SetInputConnection( sphereSource->GetOutputPort() );
    sphereMapper->ScalarVisibilityOff();

    vtkSmartPointer<vtkActor> sphereActor =
    vtkSmartPointer<vtkActor>::New();

    sphereActor->SetMapper( sphereMapper );
    sphereActor->GetProperty()->SetOpacity(.3);
    sphereActor->GetProperty()->SetColor(1,0,0);

    // Create the tree
    vtkSmartPointer<vtkKdTree> kDTree = vtkSmartPointer<vtkKdTree>::New();
    kDTree->BuildLocatorFromPoints( sphereSource->GetOutput() );

    PointStruct pt0( 1.5, 0, 0 ), closetPoint;
    double dist2;
    vtkIdType id = kDTree->FindClosestPoint( pt0.point, dist2 );
    closetPoint = PointStruct( sphereSource->GetOutput()->GetPoint( id ) );

    vtkSmartPointer<vtkLineSource> lineSource = vtkSmartPointer<vtkLineSource>::New();
    lineSource->SetPoint1( pt0.point );
    lineSource->SetPoint2( closetPoint.point );
    lineSource->Update();
    vtkSmartPointer<vtkPolyDataMapper> lineMapper = vtkSmartPointer<vtkPolyDataMapper>::New();
    lineMapper->SetInputData( lineSource->GetOutput() );
    vtkSmartPointer<vtkActor> lineActor = vtkSmartPointer<vtkActor>::New();
    lineActor->SetMapper( lineMapper );

    cout << "dist2: " << sqrt(dist2) << endl;
    cout << "closetPoint: " << closetPoint;

    // ========= compare with test result =========
    vtkPolyData *sPd = sphereSource->GetOutput();
    double absDis = VTK_DOUBLE_MAX;
    for( int i = 0; i < sPd->GetNumberOfPoints(); ++i )
    {
      PointStruct pt( sPd->GetPoint( i ) );
      PointStruct vec = pt - pt0;
      if( absDis > vec.Length() )
      {
          absDis = vec.Length();
      }
    }
    cout << "absDis: " << absDis << endl;
    // ======== finish: compare ==========

    vtkSmartPointer<vtkRenderer> renderer =
    vtkSmartPointer<vtkRenderer>::New();
    renderer->AddViewProp(sphereActor);
    renderer->AddActor( lineActor );

    vtkSmartPointer<vtkRenderWindow> renderWindow =
    vtkSmartPointer<vtkRenderWindow>::New();
    renderWindow->AddRenderer( renderer );

    vtkSmartPointer<vtkRenderWindowInteractor> renWinInteractor =
    vtkSmartPointer<vtkRenderWindowInteractor>::New();
    renWinInteractor->SetRenderWindow( renderWindow );

    renderWindow->Render();
    renWinInteractor->Start();
    return EXIT_SUCCESS;
}

Output:

dist2: 0.570277
closetPoint: PointStruct [0.974928, 0, 0.222521]
absDis: 0.570277