# vtkCellLocator::FindClosestPoint: returns incorrect results for certain dataset

**URL:** <https://discourse.vtk.org/t/vtkcelllocator-returns-incorrect-results-for-certain-dataset/11576>\
**Category:** Development\
**Created:** [May 30, 2023, 9:47am UTC](https://discourse.vtk.org/t/vtkcelllocator-returns-incorrect-results-for-certain-dataset/11576 "2023-05-30T09:47:35Z")\
**Posts on this page:** 8\
**Page:** 1

<div class="post-metadata">

**Author:** ![lukas](https://discourse.vtk.org/letter_avatar_proxy/v4/letter/l/e9a140/32.png) [@lukas](https://discourse.vtk.org/u/lukas)\
**Post date:** [May 30, 2023, 9:47am UTC](https://discourse.vtk.org/t/vtkcelllocator-returns-incorrect-results-for-certain-dataset/11576/1 "2023-05-30T09:47:35Z")

</div>

Hello,

I am using the method vtkCellLocator::FindClosestPoint and get incorrect results for certain input point coordinates and polydata.

The example code loads a polydata file and uses a vtkCellLocator to find the closest point to the input point with coordinates (110000, 110000, 0). See here:

```auto
#include <vtkCellLocator.h>
#include <vtkNew.h>
#include <vtkXMLPolyDataReader.h>

int main(int argc, char *argv[]) {
  // Parse command line arguments
  if (argc != 2) {
    std::cerr << "Usage: " << argv[0] << " Filename(.vtp) e.g. Torso.vtp"
              << std::endl;
    return EXIT_FAILURE;
  }

  std::string filename = argv[1];

  // Read all the data from the file
  vtkNew<vtkXMLPolyDataReader> reader;
  reader->SetFileName(filename.c_str());
  reader->Update();

  // Create the tree
  vtkNew<vtkCellLocator> cellLocator;
  cellLocator->SetDataSet(reader->GetOutputAsDataSet());
  cellLocator->BuildLocator();

  double testPoint[3] = {110000, 110000, 0};

  // Find the closest points to TestPoint
  double closestPoint[3]; // the coordinates of the closest point will be
                            // returned here
  double closestPointDist2; // the squared distance to the closest point will be
                            // returned here
  vtkIdType cellId; // the cell id of the cell containing the closest point will
                    // be returned here
  int subId; // this is rarely used (in triangle strips only, I believe)
  cellLocator->FindClosestPoint(testPoint, closestPoint, cellId, subId,
                                closestPointDist2);

  std::cout << "Coordinates of closest point: " << closestPoint[0] << " "
            << closestPoint[1] << " " << closestPoint[2] << std::endl;
  std::cout << "Squared distance to closest point: " << closestPointDist2
            << std::endl;
  std::cout << "CellId: " << cellId << std::endl;

  return EXIT_SUCCESS;
}

```

The input polydata was created with the plane source in paraview.

For a plane with 4 cells

[plane\_4cells.vtp](https://discourse.vtk.org/uploads/short-url/3jdnUNe21tKYVINN4TLPb4lCrVS.vtp) (4.6 KB)

the expected result is returned:

```auto
Coordinates of closest point: 10.5 10.5 0
Squared distance to closest point: 2.41954e+10
CellId: 3

```

However for a plane with the same bounds but finer mesh

[plane\_56cells.vtp](https://discourse.vtk.org/uploads/short-url/rGRMOwGXr12wiHlbZGySupjq847.vtp) (8.7 KB)

the result is incorrect:

```auto
Coordinates of closest point: 2.122e-314 2.54639e-313 0
Squared distance to closest point: -1
CellId: 20

```

Note that switching to vtkStaticCellLocator also does not work for plane\_56cells.vtp. The results are:

```auto
Coordinates of closest point: 7.90505e-323 1.35808e-312 9.88131e-324
Squared distance to closest point: inf
CellId: 80

```

I am using VTK9.2.6 on Ubuntu 22.04.

Are there any limitations on FindClosestPoint that need to be considered or is this a bug?

---

<div class="post-metadata">

**Author:** ![spyridon97](https://discourse.vtk.org/user_avatar/discourse.vtk.org/spyridon97/32/7069_2.png) [@spyridon97](https://discourse.vtk.org/u/spyridon97)\
**Post date:** [May 30, 2023, 8:59pm UTC](https://discourse.vtk.org/t/vtkcelllocator-returns-incorrect-results-for-certain-dataset/11576/2 "2023-05-30T20:59:10Z")

</div>

what do you mean by incorrect/

How did you figure out what the correct result is?

---

<div class="post-metadata">

**Author:** ![lukas](https://discourse.vtk.org/letter_avatar_proxy/v4/letter/l/e9a140/32.png) [@lukas](https://discourse.vtk.org/u/lukas)\
**Post date:** [May 31, 2023, 11:34am UTC](https://discourse.vtk.org/t/vtkcelllocator-returns-incorrect-results-for-certain-dataset/11576/3 "2023-05-31T11:34:50Z")

</div>

Hi Spiros,

Thanks for replying, I will try to clarify what I mean.

The 2 files I send in my original post contain the same shape (a square located in the xy plane with its edges oriented parallel to the x- and y-axis) with the same bounds. The only difference is the amount of cells that the square is meshed with. Here are screenshots from Paraview:

 ![Screenshot from 2023-05-31 09-02-31](https://discourse.vtk.org/uploads/default/original/2X/9/91d543d7f50cda503fd5aff7a859ffba87a4336a.png)

 ![Screenshot from 2023-05-31 07-28-41](https://discourse.vtk.org/uploads/default/original/2X/6/6cbc36d66f30085383363d75b95c8c373ed628e7.png)

The test point in the source code has coordinates (110000, 110000, 0), so the closest point on the mesh should be the point with coordinates (10.5, 10.5, 0), which is the top right corner of the square as indicated in pink in the screenshots. The squared distance from the test point to this point is 2\*(110000-10.5)^2=24195380220.5.

This is the result I get, when using the file plane\_4cells.vtp with the code in the original post. But with the finer mesh in plane\_56cells.vtp, no point is found even though the location of the expected closest point is the same between the 2 vtp files.

Does this clarify the issue?

---

<div class="post-metadata">

**Author:** ![will.schroeder](https://discourse.vtk.org/user_avatar/discourse.vtk.org/will.schroeder/32/233_2.png) [@will.schroeder](https://discourse.vtk.org/u/will.schroeder)\
**Post date:** [May 31, 2023, 1:11pm UTC](https://discourse.vtk.org/t/vtkcelllocator-returns-incorrect-results-for-certain-dataset/11576/4 "2023-05-31T13:11:09Z")

</div>

Do I have this correct: the bounds of your test data is (10,10.5, 10,10.5, 0,0), and your test point is 24,195,380,220.5 distant^2? it is almost certainly a numerical issue. You may have to use a different approach with this kind of variation in scale.

---

<div class="post-metadata">

**Author:** ![will.schroeder](https://discourse.vtk.org/user_avatar/discourse.vtk.org/will.schroeder/32/233_2.png) [@will.schroeder](https://discourse.vtk.org/u/will.schroeder)\
**Post date:** [June 1, 2023, 10:06am UTC](https://discourse.vtk.org/t/vtkcelllocator-returns-incorrect-results-for-certain-dataset/11576/5 "2023-06-01T10:06:34Z")

</div>

Can you explain why you are testing points so far from the dataset/locator? If I understand your application I might be able to offer suggestions. For example, why are you using CellLocator rather than PointLocator to determine closest points?

Typically in application the locators closely “fit” around the dataset, and subsequent operations on the locator are within, or in close proximity to the dataset (e.g., streamline generation, probing). Operating on a locator/dataset at a far removed distance is not typical, and numerics problems would not surprise me at extreme scale.

---

<div class="post-metadata">

**Author:** ![lukas](https://discourse.vtk.org/letter_avatar_proxy/v4/letter/l/e9a140/32.png) [@lukas](https://discourse.vtk.org/u/lukas)\
**Post date:** [June 1, 2023, 11:44am UTC](https://discourse.vtk.org/t/vtkcelllocator-returns-incorrect-results-for-certain-dataset/11576/6 "2023-06-01T11:44:21Z")

</div>

Thank you for taking interest in the issue. I am using vtkCellLocator::FindClosestPoint because I am interested in the closest location on the mesh surface, which is not necessarily a point of the mesh.

You are correct that the first example was a bit extreme in terms of the length scales. Here is a second attempt to illustrate the problem.

I have a small quad mesh and 2 points (green and red) for which I want to find the closest point on the mesh.

 ![Screenshot from 2023-06-01 13-11-59](https://discourse.vtk.org/uploads/default/original/2X/7/7fdb913ff6a043518aa73b3e84a0d994a1116c58.png)

This is the input polydata:  
[cellLocatorTest.vtp](https://discourse.vtk.org/uploads/short-url/gOVyw3Q0XhenCEiFItWVhmVe6FN.vtp) (6.7 KB)

The code I am using is as follows:

```auto
#include <vtkCellLocator.h>
#include <vtkNew.h>
#include <vtkXMLPolyDataReader.h>

int main(int argc, char *argv[]) {
  // Parse command line arguments
  if (argc != 2) {
    std::cerr << "Usage: " << argv[0] << " Filename(.vtp)" << std::endl;
    return EXIT_FAILURE;
  }

  std::string filename = argv[1];

  // Read all the data from the file
  vtkNew<vtkXMLPolyDataReader> reader;
  reader->SetFileName(filename.c_str());
  reader->Update();

  // Create the tree
  vtkNew<vtkCellLocator> cellLocator;
  cellLocator->SetDataSet(reader->GetOutputAsDataSet());
  cellLocator->BuildLocator();

  double closestPoint[3];
  double closestPointDist2;
  vtkIdType cellId;
  int subId;

  {
    double testPoint1[3] = {47990.9, -30695.5, 2041.02};
    cellLocator->FindClosestPoint(testPoint1, closestPoint, cellId, subId,
                                  closestPointDist2);

    std::cout << "testPoint1: " << testPoint1[0] << " " << testPoint1[1] << " "
              << testPoint1[2] << std::endl;
    std::cout << " Coordinates of closest point: " << closestPoint[0] << " "
              << closestPoint[1] << " " << closestPoint[2] << std::endl;
    std::cout << " Squared distance to closest point: " << closestPointDist2
              << std::endl;
    std::cout << " CellId: " << cellId << std::endl;
  }

  {
    double testPoint2[3] = {48000.4, -30689., 2041.17};
    cellLocator->FindClosestPoint(testPoint2, closestPoint, cellId, subId,
                                  closestPointDist2);

    std::cout << "testPoint2: " << testPoint2[0] << " " << testPoint2[1] << " "
              << testPoint2[2] << std::endl;
    std::cout << " CellId: " << cellId << std::endl;
    std::cout << " Coordinates of closest point: " << closestPoint[0] << " "
              << closestPoint[1] << " " << closestPoint[2] << std::endl;
    std::cout << " Squared distance to closest point: " << closestPointDist2
              << std::endl;
    std::cout << " CellId: " << cellId << std::endl;
  }

  return EXIT_SUCCESS;
}

```

Running this with cellLocatorTest.vtp as command line parameter gives the following output on my machine (Ubuntu 22.04, VTK9.2.6):

```auto
testPoint1: 47990.9 -30695.5 2041.02
  Coordinates of closest point: 47990.9 -30695.5 2041.18
  Squared distance to closest point: 0.0254294
  CellId: 17
testPoint2: 48000.4 -30689 2041.17
  Coordinates of closest point: 0 0 6.95331e-310
  Squared distance to closest point: -1
  CellId: 4

```

Note that vtkStaticCellLocator returns results for both points. The output for testPoint1 is the same and for testPoint2 I get:

```auto
testPoint2: 48000.4 -30689 2041.17
  CellId: 23
  Coordinates of closest point: 48000.4 -30689 2041.29
  Squared distance to closest point: 0.0163977
  CellId: 23

```

So the question is: Why is there no closest point for testPoint2 with vtkCellLocator?

---

<div class="post-metadata">

**Author:** ![will.schroeder](https://discourse.vtk.org/user_avatar/discourse.vtk.org/will.schroeder/32/233_2.png) [@will.schroeder](https://discourse.vtk.org/u/will.schroeder)\
**Post date:** [June 1, 2023, 2:21pm UTC](https://discourse.vtk.org/t/vtkcelllocator-returns-incorrect-results-for-certain-dataset/11576/7 "2023-06-01T14:21:58Z")

</div>

I’m using VTK master on Ubuntu and things seem to be working fine for me. The results are identical for vtkCellLocator and vtkStaticCellLocator. (FYI I removed the duplicate std::cout in your code.)

/ClosestPoint Data/cellLocatorTest.vtp  
testPoint1: 47990.9 -30695.5 2041.02  
Coordinates of closest point: 47990.9 -30695.5 2041.18  
Squared distance to closest point: 0.0254294  
CellId: 17  
testPoint2: 48000.4 -30689 2041.17  
Coordinates of closest point: 48000.4 -30689 2041.29  
Squared distance to closest point: 0.0163977  
CellId: 23

I’m not sure what’s going on. Since you seem to be code savvy I recommend that you debug through the code to see what’s going on.

---

<div class="post-metadata">

**Author:** ![lukas](https://discourse.vtk.org/letter_avatar_proxy/v4/letter/l/e9a140/32.png) [@lukas](https://discourse.vtk.org/u/lukas)\
**Post date:** [June 1, 2023, 5:16pm UTC](https://discourse.vtk.org/t/vtkcelllocator-returns-incorrect-results-for-certain-dataset/11576/8 "2023-06-01T17:16:55Z")

</div>

I can confirm that the example with cellLocatorTest.vtp works with the vtkCellLocator from the current master branch (commit: 9e6555bad864e1db941773591cb97c0fa82e0d8c). I get the same results as you for both points.

Comparing master with v9.2.6 shows that a change was made to the vtkCellLocator in this commit:

[https://gitlab.kitware.com/vtk/vtk/-/commit/08fb2a1d5e56170c7f4b0eee14f15348f30dfda3](https://gitlab.kitware.com/vtk/vtk/-/commit/08fb2a1d5e56170c7f4b0eee14f15348f30dfda3)

Good to know that this is fixed. Thank you for the feedback!