title: How to Efficiently Find a Neighbor Point in a List?
body: <p>I have a large list of Points in an Image and I want to find the Point Nearest to a given Point.</p>
  <p><strong>Existing Approach Tried:</strong>
  Divide the Image into Tiles and search only within the Region of Interest by building a Table. The light blue cloured one are the points I'm comparing.</p>
  <p><a href="https://i.stack.imgur.com/ppPMK.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/ppPMK.png" alt="enter image description here" /></a>
  <strong>Problems</strong>
  Even with very fewer comparisons, my algorithm is taking more than the actual time. Is there any scope for improvement in my current approach? Is there any other better approach?</p>
  <p>Run Times in my Machine:
  Time Taken for</p>
  <pre><code>FindNearestPoint  : 0.021145 ms  
  FindNearestPointV2: 0.047953 ms
  </code></pre>
  <p><strong>PC Config:</strong> Intel(R) Core(TM) i7-6820HQ CPU @ 2.70 GHZ</p>
  <pre><code>// Feature Comparision.cpp : Defines the entry point for the console application.
  //
  
  #include &quot;stdafx.h&quot;
  //
  #include &lt;iostream&gt;
  #include &lt;cstdlib&gt;
  #include &lt;cstring&gt;
  #include &lt;vector&gt;
  #include &quot;Timer.h&quot; //http://www.songho.ca/misc/timer/files/timer.zip
  
  #include &quot;opencv2\opencv.hpp&quot;
  #include &quot;opencv2\opencv_modules.hpp&quot;
  
  using namespace cv;
  using namespace std;
  
  bool FindNearestPoint(const Point2f Point, const vector&lt;Point2f&gt;vPoints, int &amp;Index )
  {
      CV_Assert(vPoints.size() != 0);
  
      float PrevDistance = FLT_MAX;
      Index = -1;//Error Case
      for (size_t i = 0; i &lt; vPoints.size(); i++)
      {
          float Distance = cv::norm(Point - Point2f(vPoints[i].x, vPoints[i].y));
  
          if (Distance &lt; PrevDistance)
          {
              Index = i;
              PrevDistance = Distance;
          }
      }
      return true;
  
  }
  
  static inline bool GetListofClustersToProcess(const Point2f Pt, const Point2f szTileSize, const Size GridSize, vector&lt;Point&gt; &amp;ClusterIndices)
  {
      Point Index(Pt.x* szTileSize.x, Pt.y * szTileSize.y);
      vector&lt;Point&gt; vClusterIndices;
  
      //Prev Tile
      vClusterIndices.push_back(Index + Point(-1, -1));//Prev Tile
      vClusterIndices.push_back(Index + Point(-1, 0)); //Curr Tile
      vClusterIndices.push_back(Index + Point(-1, 1)); //Next Tile
  
      vClusterIndices.push_back(Index + Point(0, -1)); //Prev Tile
      vClusterIndices.push_back(Index + Point(0, 0)); //Curr Tile
      vClusterIndices.push_back(Index + Point(0, 1)); //Next Tile
  
      vClusterIndices.push_back(Index + Point(1, -1)); //Prev Tile
      vClusterIndices.push_back(Index + Point(1, 0));     //Curr Tile
      vClusterIndices.push_back(Index + Point(1, 1));     //Next Tile
  
      for (size_t i = 0; i &lt; vClusterIndices.size(); i++)
      {
          Index = vClusterIndices[i];
          if ((Index.x &lt; 0) || (Index.x &gt;= GridSize.width) || (Index.y &lt; 0) || (Index.y &gt;= GridSize.height))
          {
              continue;
          }
          ClusterIndices.push_back(Index);
      }
  
      return true;
  }
  
  bool FindNearestPointV2(const Point2f Point, const vector&lt;Point2f&gt;vPoints,const vector&lt;vector&lt;vector&lt;int&gt;&gt;&gt;vClusters,const Point2f szTileSize, const Size GridSize, int &amp;Index,Mat &amp;mDebugImage)
  {
      #define EnableDebug 0
  
      CV_Assert(vPoints.size() != 0);
  
      vector&lt;cv::Point&gt; ClusterIndices;
      ClusterIndices.clear();
  
      GetListofClustersToProcess(Point, szTileSize,GridSize, ClusterIndices);
  
      float PrevDistance = FLT_MAX;
  
      Index = -1;//Error Case
      int KeypointIdx = 0;
  
      for (size_t iClusterIdx = 0; iClusterIdx &lt; ClusterIndices.size(); iClusterIdx++)
      {
          cv::Point Cluster(ClusterIndices[iClusterIdx]);
  
          CV_Assert((Cluster.x &gt;= 0)&amp;&amp;(Cluster.x &lt; GridSize.width));
          CV_Assert((Cluster.y &gt;= 0) &amp;&amp; (Cluster.y &lt; GridSize.height));
  
          for (size_t i = 0; i &lt; vClusters[Cluster.y][Cluster.x].size(); i++)
          {
              KeypointIdx = vClusters[Cluster.y][Cluster.x][i];
  
              CV_Assert(KeypointIdx &lt; vPoints.size());
  
              float Distance = cv::norm(Point - Point2f(vPoints[KeypointIdx].x, vPoints[KeypointIdx].y));
  
  #if EnableDebug
              circle(mDebugImage, vPoints[KeypointIdx], 2, Scalar(255, 255, 0), 2);
  
              imshow(&quot;Input Features&quot;, mDebugImage);
  #endif
              //New Optimized Implementation
              //waitKey();
  
              if (Distance &lt; PrevDistance)
              {
                  Index = KeypointIdx;
                  PrevDistance = Distance;
              }
          }
      }
      return true;
  
  }
  
  int main(int argc, char* argv[])
  {
      /*TestKNN();
      return 0;*/
  
      Size ImageSize(900, 300);
      Mat mInputImage(ImageSize, CV_8UC3, Scalar::all(0));
      RNG rng(0xFFFFFFFF);
      vector&lt;Point2f&gt;vKeypoints;
      int MaxNoOfKeypoints = 2000;
      uint16_t maxFilteredKeypoints = 350;
      int TileSize = 32;//Tile Size in Pixels
      Size GridSize((ImageSize.width / TileSize)+1, (ImageSize.height / TileSize)+1);
      vector&lt;vector&lt;vector&lt;int&gt;&gt;&gt;vClusters;
      Point ptTileIdx(0,0);
      Point2f PtQuery,PtNearestPoint, PtNearestPointV2;
      Point2f GridScale((float)GridSize.width / (float)ImageSize.width, (float)GridSize.height / (float)ImageSize.height);
      int NoOfTestPoints = 100, Iteration = 0;
  
      for (;;)
      {
          vKeypoints.clear();
          vClusters.clear();
          mInputImage.setTo(0);
          //Generating Random Keypoints
          for (size_t i = 0; i &lt; MaxNoOfKeypoints; i++)
          {
              vKeypoints.push_back(Point2f(rng.uniform(0, ImageSize.width), rng.uniform(0, ImageSize.height)));
          }
  
          cout &lt;&lt; &quot;Grid Size :&quot; &lt;&lt; GridSize &lt;&lt; &quot;\n&quot;;
          for (size_t iVerTile = 0; iVerTile &lt; GridSize.height; iVerTile++)
          {
              vector&lt;vector&lt;int&gt;&gt;HorTiles;
              Scalar color = Scalar(rng.uniform(0, 255), rng.uniform(0, 255), rng.uniform(0, 255));
              for (size_t iHorTile = 0; iHorTile &lt; GridSize.width; iHorTile++)
              {
                  Rect TileRect(iHorTile*TileSize, iVerTile*TileSize, TileSize, TileSize);
                  rectangle(mInputImage, TileRect, color, 1);
                  color += Scalar(0, 0, 10);
                  HorTiles.push_back(vector&lt;int&gt;());
              }
              vClusters.push_back(HorTiles);
          }
          printf(&quot;Cluster Size : %d , %d \n&quot;,vClusters.size(),vClusters[0].size());
          
          //Classify Tile Idx for all the Keypoints
          for (size_t i = 0; i &lt; MaxNoOfKeypoints; i++)
          {
              ptTileIdx.x = (int)(vKeypoints[i].x / TileSize);
              ptTileIdx.y = (int)(vKeypoints[i].y / TileSize);
              vClusters[ptTileIdx.y][ptTileIdx.x].push_back(i);
          }
  
          //Displaying the Keypoints
          for (size_t i = 0; i &lt; MaxNoOfKeypoints; i++)
          {
              circle(mInputImage, vKeypoints[i], 2, Scalar(255, 0, 0), 2);
          }
          Mat mInputTestImage = mInputImage.clone();
          Iteration = 0;
          while (Iteration&lt;NoOfTestPoints)
          {
              PtQuery = Point2f(rng.uniform(0, ImageSize.width), rng.uniform(0, ImageSize.height));
  
              circle(mInputTestImage, PtQuery, 4, Scalar(0, 255, 0), 4);
              circle(mInputTestImage, PtQuery, 2, Scalar(0, 0, 255), 2);
              
              int NearestPointIndex = -1, NearestPointIndexV2 = -1;
              Timer t_FindNearestPt;
              t_FindNearestPt.start();
  
              FindNearestPoint(PtQuery, vKeypoints, NearestPointIndex);
  
              t_FindNearestPt.stop();
  
              PtNearestPoint = vKeypoints[NearestPointIndex];
  
              Timer t_FindNearestPtV2;
              t_FindNearestPtV2.start();
              //New Optimized Implementation
              FindNearestPointV2(PtQuery, vKeypoints, vClusters, GridScale, GridSize, NearestPointIndexV2,mInputTestImage);
  
              t_FindNearestPtV2.stop();
  
              PtNearestPointV2 = vKeypoints[NearestPointIndexV2];
  
              if (NearestPointIndexV2 != -1)
              {
                  circle(mInputTestImage, PtNearestPointV2, 2, Scalar(0, 0, 255), 2);
              }
              if (NearestPointIndex != -1)
              {
                  circle(mInputTestImage, PtNearestPoint, 2, Scalar(0, 255, 0), 2);
              }
  
              if (NearestPointIndex != NearestPointIndexV2)
              {
                  printf(&quot;[Error] Closest Point not Matching! \n&quot;);
                  cout &lt;&lt; &quot;Point&quot; &lt;&lt; PtQuery &lt;&lt;  &quot; Org&quot; &lt;&lt; PtNearestPoint &lt;&lt; &quot;!= V2 &quot; &lt;&lt; PtNearestPointV2 &lt;&lt; &quot;\n&quot;;
                  float Distance = cv::norm(PtQuery - PtNearestPoint);
                  float DistanceV2 = cv::norm(PtQuery - PtNearestPointV2);
                  printf(&quot;Distance : %f - %f  \n&quot;, Distance, DistanceV2);
              }
              /*else
              {
                  printf(&quot;[Passed] Closest Point Matching! \n&quot;);
              }*/
              float TimeTaken_C = t_FindNearestPt.getElapsedTimeInMilliSec();
              printf(&quot;Time Taken for FindNearestPoint  : %f ms\t&quot;, TimeTaken_C);
              printf(&quot;FindNearestPointV2: %f ms\t&quot;, t_FindNearestPtV2.getElapsedTimeInMilliSec());
              printf(&quot;Speed: %f x\n&quot;, TimeTaken_C/t_FindNearestPtV2.getElapsedTimeInMilliSec());
  
              imshow(&quot;Input Features&quot;, mInputTestImage);
              Iteration++;
              char key = (char)waitKey();
              if (key == 27 || key == 'q' || key == 'Q') // 'ESC'
                  break;
              mInputTestImage= mInputImage.clone();
          }
      
          char key = (char)waitKey();
          if (key == 27 || key == 'q' || key == 'Q') // 'ESC'
              break;
      }
  
  
      return 0;
  }
  </code></pre>