return the number of point within a radius

[Xiaojieqiu]

In page 10 of the manual of ANN (https://www.cs.umd.edu/~mount/ANN/Files/1.1.2/ANNmanual_1.1.pdf) . It mentioned that we can return the number of points within a radius when setting the ANNdist to sqRad and k = 0. This is very useful when we are trying to count the number of points for each sample whose distance is within the radius. Can you help to also return this value?

I think ANNkdFRPtsInRange is actually the value we want. But I don't know how can we return that value in the get_NN_2Set and nn2 function

int ANNkd_tree::annkFRSearch(
	ANNpoint			q,				// the query point
	ANNdist				sqRad,			// squared radius search bound
	int					k,				// number of near neighbors to return
	ANNidxArray			nn_idx,			// nearest neighbor indices (returned)
	ANNdistArray		dd,				// the approximate nearest neighbor
	double				eps)			// the error bound
{
	ANNkdFRDim = dim;					// copy arguments to static equivs
	ANNkdFRQ = q;
	ANNkdFRSqRad = sqRad;
	ANNkdFRPts = pts;
	ANNkdFRPtsVisited = 0;				// initialize count of points visited
	ANNkdFRPtsInRange = 0;				// ...and points in the range

	ANNkdFRMaxErr = ANN_POW(1.0 + eps);
	ANN_FLOP(2)							// increment floating op count

	ANNkdFRPointMK = new ANNmin_k(k);	// create set for closest k points
										// search starting at the root
	root->ann_FR_search(annBoxDistance(q, bnd_box_lo, bnd_box_hi, dim));

	for (int i = 0; i < k; i++) {		// extract the k-th closest points
		if (dd != NULL)
			dd[i] = ANNkdFRPointMK->ith_smallest_key(i);
		if (nn_idx != NULL)
			nn_idx[i] = ANNkdFRPointMK->ith_smallest_info(i);
	}

	delete ANNkdFRPointMK;				// deallocate closest point set
	return ANNkdFRPtsInRange;			// return final point count
}

[Xiaojieqiu]

btw, in python, you can do this easily by using query_ball_point, see: https://docs.scipy.org/doc/scipy-0.14.0/reference/generated/scipy.spatial.KDTree.query_ball_point.html#scipy.spatial.KDTree.query_ball_point

[jefferis]

Dear Xiaojie,

Thanks for your interest in ANN. I am afraid I do not currently have time to implement this feature but if you would like to make pull request, I will be happy to consider it.

I think it would probably make sense to have a separate function as in your python example. Best wishes,

Greg Jefferis.

Sent from my iPhone

On 25 May 2017, at 04:08, Xiaojie Qiu [email protected] wrote:

btw, in python, you can do this easily by using query_ball_point, see: https://docs.scipy.org/doc/scipy-0.14.0/reference/generated/scipy.spatial.KDTree.query_ball_point.html#scipy.spatial.KDTree.query_ball_point

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub, or mute the thread.

[romanzenka]

@jefferis I just ran into the same problem. I am trying to implement a particular 2D clustering algorithm that would benefit from locating "most dense" areas. I cannot spare storing a full matrix (100 million points), but I could use an array listing number of closest points within a certain radius.

I will try to look into making this happen and doing a PR if I can...

[jefferis]

OK. Thank you @romanzenka. I'm happy to answer questions.

[jefferis]

PS @romanzenka if you found a patch against https://github.com/jefferis/RANN2 considerably easier (it uses RCpp) then I might consider a CRAN submission for that.

[romanzenka]

@jefferis Okay, I will look into RANN2 first.

[romanzenka]

I sent a preliminary PR into RANN2 just to show what I'm thinking - with your approval I can finish this up in a more complete fashion.