An approach to solve this type of queries uses a couple of distance measures, search pruning criteria, and a search algorithm
- Min-distance(P,R)
is zero if P is inside of R or on its boundary. If P is outside of R,
then min-distance(P,R) is the Euclidean distance between P and any side
of R
- Min-Max distance(P,R)
is the distance to P from the farthest point on any face of R that
contain the vertex closest from R to P. The construction of the R-tree
guarantee that there is an object O inside of R in the R-tree such that
distance(O,P) ≤ Min-Max distance(P,R)
Some search pruning strategies are:
- An MBR M can be eliminated if if there is another MBR M’ such that min-distance(P,M) > min-max distance(P,M’)
- An MBR M can be eliminated if if there is an object O such that distance(P,O) < min- distance(P,M)
- An object O can be eliminated if if there is an MBR M such that distance(P,O) > min-max distance(P,M)
|
Última modificación: Saturday, 19 de November de 2005, 09:11