查看“树：R树”的源代码

[[category:数据结构]]

== 关于 ==


== 空间数据 ==
基于实体的模型：
# 0-dimensional objects：一般使用点point来表示那些对于不需要使用到形状信息的实体。
# 1-dimensional objects or linear objects：用于表示一些路网的边，一般用于表示道路road。 (polyline)
# 2-dimensional objects or surfacic objects：用于表示有区域面积的实体。 (polygon)


常用的空间数据查询方式：
# 窗口查询：给定一个查询窗口（通常是一个矩形），返回与查询窗口相重叠的物体。
# 点查询：给定一个点，返回包含这个点的所有几何图形。

=== 空间数据获取的方法 ===
通常，我们不选择去索引几何物体本身，而是采用“最小限定箱”（MBB：minimum bounding box）作为不规则几何图形的 key 来构建空间索引：
# 二维：称之为“'''最小限定矩形'''”（'''MBR'''：minimum bounding retangle）。
#: [[File:“最小限定矩形”（MBR：minimum bounding retangle）.png|200px]]
# 三维：称之为“最小限定箱”（MBB：minimum bounding box）。
#: [[File:“最小限定箱”（MBB：minimum bounding box）.png|200px]]


通过索引操作对象的 MBB 进行查询，步骤：【？？？】
# Filtering：过滤掉 MBB 不相交的数据集，剩下的 MBB 被索引到的称为一个数据的超集。
#: [[File:通过索引操作对象的 MBB 进行查询：Filtering.png|200px]]
# Refinement：测试实际的几何形状会不会满足查询条件，精确化。
#: [[File:通过索引操作对象的 MBB 进行查询：Refinement.png|200px]]


使用：
# 用数据表示一个 MBR：
#: 通常，只需要两个点就可限定一个矩形，也就是矩形某个对角线的两个点（“左下右上”或“左上右下”）就可以决定一个唯一的矩形。
#: [[File:用数据表示一个 MBR.png|200px]]
## 表示一个点的数据：
#: <syntaxhighlight lang="mysql">
　　　　public class Point{ //用一个类来表示一个点
　　　　    public Float x;
　　　　    public Float y
　　　　}
</syntaxhighlight>
## 表示一个 MBR 的数据：
#: <syntaxhighlight lang="mysql">
　　　　public class MBR{
　　　　    public Point BottomLeft;
　　　　    public Point TopRight;
　　　　}
</syntaxhighlight>
# 判断两个 MBR 是否相交：
#:  如果一个MBR的TopLeft或者BottomRight的（x，y）位于另一个MBR的 xRange 和 yRangle 里面，则说明这两个MBR相交。
#:  [[File:判断两个MBR是否相交.png|200px]]

== R树 ==



== R树操作 ==
=== 搜索 ===
----
=== 插入 ===
----
=== 删除 ===
----

== 参考 ==
# [https://zhuanlan.zhihu.com/p/62639268 什么是R树？]
# [https://www.cnblogs.com/cmi-sh-love/p/kong-jian-shud-ju-suo-yinRTree-wan-quan-jie-xi-jiJa.html 空间数据索引RTree（R树）完全解析及Java实现]
# [https://blog.csdn.net/v_JULY_v/article/details/6530142/ 从B树、B+树、B*树谈到R 树]
# []
# []