Density-based clustering of image keypoints I have implemented the DBSCAN algorithm for clustering image keypoints.  I have been following the pseudocode on the wiki page pretty strictly, and it's working, but I get the feeling its a very naive implementation and could be improved in terms of performance.  I was hoping you could offer me some feedback on how to improve it.

/* DBSCAN - density-based spatial clustering of applications with noise */

vector&lt;vector&lt;KeyPoint&gt;&gt; DBSCAN_keypoints(vector&lt;KeyPoint&gt; *keypoints, float eps, int minPts)
{
vector&lt;vector&lt;KeyPoint&gt;&gt; clusters;
vector&lt;bool&gt; clustered;
vector&lt;int&gt; noise;
vector&lt;bool&gt; visited;
vector&lt;int&gt; neighborPts;
vector&lt;int&gt; neighborPts_;
int c;

int noKeys = keypoints-&gt;size();

//init clustered and visited
for(int k = 0; k &lt; noKeys; k++)
{
    clustered.push_back(false);
    visited.push_back(false);
}

//C =0;
c = 0;
clusters.push_back(vector&lt;KeyPoint&gt;()); //will stay empty?

//for each unvisted point P in dataset keypoints
for(int i = 0; i &lt; noKeys; i++)
{
    if(!visited[i])
    {
        //Mark P as visited
        visited[i] = true;
        neighborPts = regionQuery(keypoints,&amp;keypoints-&gt;at(i),eps);
        if(neighborPts.size() &lt; minPts)
            //Mark P as Noise
            noise.push_back(i);
        else
        {
            clusters.push_back(vector&lt;KeyPoint&gt;());
            c++;
            //expand cluster
            // add P to cluster c
            clusters[c].push_back(keypoints-&gt;at(i));
            //for each point P' in neighborPts
            for(int j = 0; j &lt; neighborPts.size(); j++)
            {
                //if P' is not visited
                if(!visited[neighborPts[j]])
                {
                    //Mark P' as visited
                    visited[neighborPts[j]] = true;
                    neighborPts_ = regionQuery(keypoints,&amp;keypoints-&gt;at(neighborPts[j]),eps);
                    if(neighborPts_.size() &gt;= minPts)
                    {
                        neighborPts.insert(neighborPts.end(),neighborPts_.begin(),neighborPts_.end());
                    }
                }
                // if P' is not yet a member of any cluster
                // add P' to cluster c
                if(!clustered[neighborPts[j]])
                    clusters[c].push_back(keypoints-&gt;at(neighborPts[j]));
            }
        }

    }
}
return clusters;
}

vector&lt;int&gt; regionQuery(vector&lt;KeyPoint&gt; *keypoints, KeyPoint *keypoint, float eps)
{
float dist;
vector&lt;int&gt; retKeys;
for(int i = 0; i&lt; keypoints-&gt;size(); i++)
{
    dist = sqrt(pow((keypoint-&gt;pt.x - keypoints-&gt;at(i).pt.x),2)+pow((keypoint-&gt;pt.y - keypoints-&gt;at(i).pt.y),2));
    if(dist &lt;= eps &amp;&amp; dist != 0.0f)
    {
        retKeys.push_back(i);
    }
}
return retKeys;
}
Just for correctness and not for performance reasons:
You nowhere mark any key as being clustered. As a result, keys may be clustered multiple times. In case all keys shall be clustered maximum one time, one may do the following modifications to the code above:

Add a following first line 

clustered[i] = true; 


behind

// add P to cluster c
clusters[c].push_back(keypoints-&gt;at(i));


and a following second line

clustered[neighborPts[j]] = true;


after

clusters[current_cluster].push_back(keypoints-&gt;at(neighborPts[j]));


Concerning the second line, make sure that it is inserted within the if-statement.