给定我当前的位置（纬度，经度），我想快速找到兴趣点问题中的最近邻居。 因此我打算使用 R-Tree 数据库，它可以快速查找。 然而，当然，首先必须填充数据库。 因此，我需要确定覆盖该区域的矩形区域，其中每个区域包含一个兴趣点。
我的问题是如何预处理数据，即如何将区域细分为这些矩形子区域？ （我想要矩形区域，因为它们很容易添加到 RTree - 与更一般的 Voronoi 区域相比）。
/约翰
given my current position (lat,long) I want to quickly find the nearest neighbor in a points of interest problem. Thus I intend to use an R-Tree database, which allows for quick lookup. However, first the database must be populated - of course. Therefore, I need to determine the rectangular regions that covers the area, where each region contains one point of interest.
My question is how do I preprocess the data, i.e. how do I subdivide the area into these rectangular sub-regions? (I want rectangular regions because they are easily added to the RTree - in contrast to more general Voronoi regions).
/John
发布评论
评论（3）
编辑：下面的方法有效，但忽略了 R 树的关键特征——R 树节点的分裂行为被明确定义，并维护平衡树（通过类似 B 树的方式）特性）。 所以事实上，您所要做的就是：
我认为下面的方法可以找到你的初始种子矩形； 但您不想以这种方式填充整个 R 树。 一直进行拆分和重新平衡可能会有点昂贵，因此您可能希望使用下面的 KD 方法来完成大部分工作； 只是不是所有的工作。
KD 方法：将所有内容都包含在一个矩形中。
如果矩形中的点数> 阈值，沿 D 方向扫描，直到覆盖一半的点。
将分割点左右（或上方和下方）分成矩形。
在新矩形上递归调用相同的过程，并使用下一个方向（如果您从左到右，现在将从上到下，反之亦然）。
与另一张海报提供的划分为正方形的方法相比，这种方法的优点是它可以更好地适应倾斜的点分布。
Edit: The below approach works, but ignores the critical feature of R-trees -- that The splitting behavior of R-tree nodes is well defined, and maintains a balanced tree (through B-tree-like properties). So in fact, all you have to do is:
I think the method below is ok for finding your initial seed rectangles; but you don't want to populate your whole R-tree that way. Doing the splits and rebalancing all the time can be a bit expensive, so you will probably want to do a decent chunk of the work with the KD approach below; just not all of the work.
The KD approach: enclose everything in a rectangle.
If the number of points in the rectangle is > threshold, sweep in direction D until you cover half the points.
Divide into rectangles left and right (or above and below) the splitting point).
Call the same procedure recursively on the new rectangles, with the next direction (if you were going left to right, you will now go top to bottom, and vice versa).
The advantage this has over the divide-into-squares approach offered by another poster is that it accommodates skewed point distributions better.
Oracle Spatial Cartridge 文档描述了可以做你想做的事情的曲面细分算法。 简而言之：
结果应如下所示：
替代文本 http://download- uk.oracle.com/docs/cd/A64702_01/doc/cartridg.805/a53264/sdo_ina5.gif
Oracle Spatial Cartridge documentation describes tessellation algorithm that can do what you want. In short:
Result should be something like this:
alt text http://download-uk.oracle.com/docs/cd/A64702_01/doc/cartridg.805/a53264/sdo_ina5.gif
我认为你在问题陈述中遗漏了一些东西。 假设有 N 个点 (x, y)，每个点都有唯一的 x 和 y 坐标。 您可以将您的区域划分为 N 个矩形，然后将其划分为 N 个垂直列。 但这并不能帮助你轻松解决最近的 POI 问题，不是吗？ 所以我认为你正在考虑一些关于矩形结构的事情，但你还没有阐明。
插图：
数字是 POI，垂直线显示细分为 7 个矩形区域。 但显然细分中并没有太多“有趣”的信息。 关于细分还有一些您没有提到的附加标准吗？
I think you a missing something in the problem statement. Assume you have N points (x, y) such that every point has a unique x- and y-coordinate. You can divide your area into N rectangles then by just dividing it into N vertical columns. But that does not help you to solve the nearest POI problem easily, does it? So I think you are thinking about something about the rectangle structure which you haven't articulated yet.
Illustration:
The numbers are POIs and the vertical lines show a subdivision into 7 rectangular areas. But clearly there isn't much "interesting" information in the subdivision. Is there some additional criterion on the subdivision which you haven't mentioned?