given my present position (lat,lengthy) I wish to rapidly discover the nearest neighbor inside a sights problem. Thus I plan to make use of an R-Tree database, which enables for convenient research. However, first the database should be populated - obviously. Therefore, I have to determine the rectangular regions that covers the region, where each region consists of one priority.

My real question is how do you preprocess the information, i.e. how do you subdivide the region in to these rectangular sub-regions? (I would like rectangular regions since they're easily put into the RTree - as opposed to more general Voronoi regions).


Oracle Spatial Cartridge documentation describes tessellation formula that may do what you would like. In a nutshell:

  • enclose all of your points in square
  • if square consists of 1 point - index square
  • if square doesn't contain points - neglected
  • if square consists of more then 1 point
    • split square into 4 equal squares and repeat analysis for every new square

Result ought to be something similar to this:
alt text

Edit: The below approach works, but ignores the critical feature of R-trees -- the splitting behavior of R-tree nodes is well defined, and keeps a well-balanced tree (through B-tree-like qualities). So actually, all you want do is:

  1. Select the most of rectangles per page
  2. Create seed rectangles (use points farthest from one another, centroids, whatever).
  3. For every point, select a rectangle to place it into
    1. Whether it already falls right into a single rectangle, place it inside
    2. If it doesn't, extend the rectangle that should be extended least (various ways to measure "least" exits -- area works)
    3. If multiple rectangles apply -- pick one depending on how full it's, as well as other heuristic
  4. If overflow happens -- make use of the quadratic split to maneuver things around...
  5. And so forth, using R-tree calculations straight from a text book.

I believe the technique below is alright for locating your initial seed rectangles but you won't want to populate all of your R-tree this way. Doing the splits and rebalancing constantly could be a little costly, which means you will most likely wish to perform a decent slice of the job using the KD approach below just not every one of the job.

The KD approach: enclose my way through a rectangle.

If the amount of points within the rectangle is > threshold, sweep in direction D before you cover half the points.

Divide into rectangles right and left (or over and below) the splitting point).

Call exactly the same procedure recursively around the new rectangles, using the next direction (should you be going left to right, you'll now go head to feet, and the other way around).

The benefit it has within the divide-into-squares approach provided by another poster is it benefits skewed point distributions better.

I believe a missing something within the problem statement. Assume you've N points (x, y) so that every location includes a unique x- and y-coordinate. You are able to divide your neighborhood into N rectangles then just by dividing it into N vertical posts. But that doesn't enable you to solve the closest POI problem easily, will it? And So I think you are looking at something concerning the rectangle structure that you simply haven't articulated yet.


| | | | |5| | |
|1| | | | |6| |
| | |3| | | | |
| | | | | | | |
| |2| | | | | |
| | | | | | |7|
| | | |4| | | |

The amounts are POIs and also the vertical lines show a subdivision into 7 rectangular areas. But clearly there is not much "interesting" information within the subdivision. Can there be some additional qualifying criterion around the subdivision that you simply haven't pointed out?