Based on this paper Finkel and Bentley Point Quadtree i am trying to implement their datastructure but i dont really understand some points.
- the function REGIONSEARCH and the procedure RECTANGLE_OVERLAPS_REGION
The procedure RECTANGLE_OVERLAPS_REGION takes 4 parameteres, namely L,R,B,T
but what areLP,RP,BP,TP? (the region boundaries?)
Everytime i compute this algorithm by hand i have the feeling that 1. i dont understand (or have misread) or 2. the algorithm is wrong, which i highly doubt.
So for Example if the SE Quadrant is considered number 4 then creating a new search rectangle (to search the subtree) with XC,R,B,YC and calling se.REGIONSEARCH(XC,R,B,YC) will create a new window in which the point of SE lies in. This will falsely add the point inside SE to the result.(Please consider the above link)
How does the region search in the above paper work?