Searching in an area . this is the quest of this short algorithm.
The range search is an interesting approach. searching in the area of your bubble to a sub bubble, etc ...
selecting the object in the area and searching again for other.
Triangular approach is the key of searching in an area.
Imaginating that Rq was our Search radius, Q our query object and N the root node or actual interesting node (recursivity).
The node N has a radius and we have selected them because to be on the actual nearest area .
Searching node is to select distance between our sub node of N and the selected radius added to the radius of our sub node . At each insertion in a Mtree we save the distance between the parent and the actual node to be fast in calculation.
If the distance between our subnode and the Q searched object are inferior to the Selected radius and the radius of the sub node node of N, we can add them added to their sub node to our selection.If the actual is a leaf node we add their last sub node to the returned object if the distance correspond.
public List<MTreeObject> RangeSearch (MTreeNode N, MTreeObject Q /*query_object*/, double Rq/*search_radius*/)
{
MTreeObject Op=N.parent;
List <MTreeObject> allRangeResult=new ArrayList();
if (!N.isLeafNode)
{
for(MTreeObject Or:N.objects)
{
if(Math.abs(Q.distanceFromParent-Or.distanceFromParent)<=Rq+Or.radius)
{
double distances=distance(Or,Q);
if(distances<=Rq+Or.radius)
{
Q.distanceFromParent=distances;
allRangeResult.addAll(RangeSearch (Or.subtree, Q , Rq));
}
}
}
}
else
{
for(MTreeObject Oj:N.objects)
{
if (Math.abs(Q.distanceFromParent-Oj.distanceFromParent)<=Rq)
{
if (distance(Oj,Q)<=Rq)
{
allRangeResult.add(Oj);
}
}
}
}
return allRangeResult;
}
