# rtree-master

**Repository Path**: zy_john/rtree-master

## Basic Information

- **Project Name**: rtree-master
- **Description**: com.hisense.project-private 
- **Primary Language**: Java
- **License**: Apache-2.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 1
- **Forks**: 0
- **Created**: 2021-06-11
- **Last Updated**: 2025-10-27

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# RTree Master 使用指南

本项目是一个以 RxJava 为核心接口、可序列化、支持可视化的不可变 R-Tree 实现，提供多种分裂策略（Guttman Quadratic、R*-tree）、批量加载（STR packing）、最近邻查询（k-NN）、以及 FlatBuffers/Kryo 的序列化框架。本文面向开发者，系统说明项目目录、算法实现、RxJava 的应用、如何创建与查询 RTree，以及性能与最佳实践。

## 目录结构
- `src/main/fbs/rtree.fbs`：FlatBuffers schema
- `src/main/java/com/hisense/davidmoten/rtree/` 核心模块
  - 基础：`RTree.java`、`Context.java`、`Entry.java`、`Factory.java`、`Factories.java`
  - 算法：`Selector*.java`、`Splitter*.java`、`Backpressure.java`、`OnSubscribeSearch.java`
  - 几何：`geometry/`（`Point`、`Rectangle`、`Circle`、`Line` 及双/浮点实现）
  - 内部：`internal/`（默认节点实现、比较器、工具、优先队列、k-NN 算子）
  - FlatBuffers：`fbs/`（`FactoryFlatBuffers`、`SerializerFlatBuffers`、`LeafFlatBuffers`、`NonLeafFlatBuffers`、`generated/*`）
  - Kryo：`kryo/SerializerKryo.java`（实验性，不完整）
  - 可视化：`Visualizer.java`、`ImageSaver.java`
- `src/main/java/com/hisense/davidmoten/service/` 示例服务接口

## 核心概念
- `Entry<T,S>`：值 `T` 与几何 `S extends Geometry` 的二元组（如点、矩形、圆、线）。
- `RTree<T,S>`：不可变树；`add/delete/search/nearest/entries/visualize` 等方法返回新的树或 Observable 序列。
- `Context`：运行时参数（`minChildren`、`maxChildren`、`selector`、`splitter`、`factory`）。
- `Factory`：节点创建工厂。默认实现为 `FactoryDefault`；内存友好实现为 `FactoryFlatBuffers`。

## 构建与配置
- 快速创建：`RTree.create()` 返回空树。默认：`splitter=Quadratic`、`selector=MinimalAreaIncrease`。
- 默认容量：`maxChildren=4`、`minChildren=round(4*0.4)=2`。`star()` 切换到 R*-tree 的选择器与分裂器，但不改变上述默认容量。
- Builder API（静态）：
  - `RTree.maxChildren(int)`、`RTree.minChildren(int)`、`RTree.splitter(Splitter)`、`RTree.selector(Selector)`、`RTree.star()`、`RTree.create()`
  - 批量加载：`RTree.create(List<Entry<T,S>> entries)` 使用 STR（Sort-Tile-Recursive）打包，缺省 `loadingFactor=0.7`（每叶子填充约 `maxChildren*0.7`）。
  - 自定义工厂：`RTree.Builder.factory(Factory<?,? extends Geometry>)` 可切换 FlatBuffers 节点以降低内存占用。

## 分裂算法实现
- Guttman Quadratic（`SplitterQuadratic`）：
  - 通过枚举两两组合选出“最差组合”（使 MBR 扩张最大的两个条目）作为两个组的初始种子；
  - 其余条目按“对当前组 MBR 的面积增量最小”原则分配；
  - 保证每组满足最小容量（`minChildren`），必要时为满足容量进行倾斜分配。
- R*-tree Split（`SplitterRStar`）：
  - 对 x-/y- 轴的下/上边界分别排序（四种维度），选择使重叠最小的切分；如重叠相同则选择面积和较小者；
  - 更适用于查询负载高、需要更少重叠的场景。
- 选择策略（`Selector*`）：
  - `SelectorMinimalAreaIncrease`：插入/搜索时优先选择使 MBR 面积增量最小的分支；
  - `SelectorMinimalOverlapArea`：叶子层优先选择重叠面积更小的分支；
  - `SelectorRStar`：非叶用面积增量，叶用重叠面积（R*-tree 策略）。

## RxJava 集成与背压
- 所有查询方法返回 `Observable<Entry<T,S>>`（或 `Observable<RTree<T,S>>` 用于增删的逐步结果）。
- 背压：
  - `OnSubscribeSearch` 根据下游 `Subscriber` 的请求量选择无背压快速路径（`searchWithoutBackpressure`）或受控路径（`Backpressure.search`）；
  - 受控路径内部维护显式栈并遵循请求配额，确保在高吞吐查询中不发生上游过载。
- 阻塞收集：`tree.search(rect).toList().toBlocking().single()` 返回 `List<Entry<T,S>>`。

## 创建 RTree
示例（值为 `String`）：
```java
import com.hisense.davidmoten.rtree.*;
import com.hisense.davidmoten.rtree.geometry.*;

RTree<String, Rectangle> tree = RTree.create();

// 添加若干条目（不可变，返回新树）
tree = tree.add(Entries.entry("A", Geometries.rectangle(0,0,1,1))
                ).toBlocking().last(); // 通过 Observable.add 的 scan 形式逐步构建
// 或者使用批量加载（推荐大量数据时）：
List<Entry<String, Rectangle>> entries = new ArrayList<>();
entries.add(Entries.entry("A", Geometries.rectangle(0,0,1,1)));
entries.add(Entries.entry("B", Geometries.rectangle(2,2,3,3)));
RTree<String, Rectangle> packed = RTree.create(entries); // STR 打包
```

配置 R*-tree 与容量：
```java
RTree<String, Rectangle> t = RTree.star() // R*-tree 的 selector/splitter
    .maxChildren(8)
    .minChildren(3)
    .create();
```

FlatBuffers 工厂（降低内存占用）：
```java
import com.hisense.davidmoten.rtree.fbs.FactoryFlatBuffers;
import java.nio.charset.StandardCharsets;

FactoryFlatBuffers<String, Geometry> factory = new FactoryFlatBuffers<>(
    s -> s.getBytes(StandardCharsets.UTF_8),
    bytes -> new String(bytes, StandardCharsets.UTF_8)
);
RTree<String, Rectangle> tfb = RTree.maxChildren(8)
    .minChildren(3)
    .factory(factory)
    .create();
```

## 空间查询
- 交集搜索：
```java
Rectangle r = Geometries.rectangle(0,0,2,2);
List<Entry<String, Rectangle>> list = tree.search(r)
    .toList().toBlocking().single();
```
- 点邻域搜索（半径）：
```java
Point p = Geometries.point(1,1);
List<Entry<String, Rectangle>> near = tree.search(p, /*maxDistance*/ 5.0)
    .toList().toBlocking().single();
```
- 圆与线：`tree.search(Geometries.circle(...))`、`tree.search(Geometries.line(...))`。

## 最近邻查询（k-NN）
- 点或矩形最近邻（限定最大距离与返回数量）：
```java
List<Entry<String, Rectangle>> knn = tree.nearest(p, /*maxDistance*/ 100.0, /*maxCount*/ 10)
    .toList().toBlocking().single();
```
- 结果按距离升序返回，内部通过有界优先队列（`OperatorBoundedPriorityQueue`）。

## 批量加载（STR Packing）
- 算法流程：
  - 以 `capacity = round(maxChildren * loadingFactor)`（默认 `0.7`）为叶子容量；
  - 计算需要的叶子数 `nodeCount = ceil(N / capacity)`；
  - 对对象按中点 x 排序并切片（`sliceCount`），每片内按中点 y 排序；
  - 每片按 `capacity` 切分为叶子，递归打包为非叶直至根。
- 适用场景：静态/离线大量数据加载，构建较为紧凑的树以提升查询效率。

## 序列化/反序列化
- FlatBuffers（推荐）：
```java
import com.hisense.davidmoten.rtree.Serializers;
import com.hisense.davidmoten.rtree.InternalStructure;

Serializer<String, Rectangle> ser = Serializers.flatBuffers().utf8();
// 写
ser.write(tree, new FileOutputStream("tree.fbs"));
// 读（需传入字节大小与内部结构选项）
File f = new File("tree.fbs");
RTree<String, Rectangle> read = ser.read(new FileInputStream(f), f.length(),
    InternalStructure.SINGLE_ARRAY);
```
- Kryo：目前代码处于实验状态，读取节点尚未实现；`Serializers.SerializerBuilder.method(Method.KRYO)` 也被保护性禁用。建议使用 FlatBuffers。

## 可视化
- 生成并保存树结构图片：
```java
Visualizer v = tree.visualize(800, 600); // 自动计算视窗
// 或自定义视窗：Visualizer v = tree.visualize(800, 600, Geometries.rectangle(minX,minY,maxX,maxY));
BufferedImage img = v.createImage();
ImageSaver.save(img, new File("target/tree.png"), "PNG");
```

## 几何类型与精度
- 支持 `Point`、`Rectangle`、`Circle`、`Line` 等基础几何，双精度与浮点实现（`geometry/internal/*Double|*Float`）。
- `Geometries.*` 提供便捷构造方法与 MBR（最小外包矩形）计算。

## 性能与最佳实践
- 容量：`maxChildren` 直接影响树的高度与每节点扇出；一般较大的 `maxChildren` 可以降低高度，但需权衡每节点重叠增多的影响。
- 分裂策略：查询密集型场景优先 `R*-tree`（`RTree.star()`）；插入密集、简单场景 `Quadratic` 更轻量。
- 批量加载：静态数据建议 STR；动态流的场景使用逐步添加（Observable 的 `scan`）。
- 背压：大规模查询在 Rx 链路中保持有界消费（如 `buffer`/`observeOn` 结合），本库内部已对 `search` 做了背压支持。
- 内存：FlatBuffers 工厂（`FactoryFlatBuffers`）在大容量节点（较大 `maxChildren`）下可显著降低内存占用。

## 参考服务接口示例
```java
import com.hisense.davidmoten.service.impl.RTreeQuery;

RTreeQuery<String, Rectangle> svc = new RTreeQuery<>(packed);
List<Entry<String, Rectangle>> found = svc.queryByRectangle(Geometries.rectangle(0,0,5,5));
```

---
如需进一步扩展（自定义选择器/分裂器、更多几何类型、不同内部结构），请参考对应包中的实现：`Selector*`、`Splitter*`、`geometry/*`、`internal/*`。以上示例均基于当前代码的真实默认行为（默认 `maxChildren=4`、`minChildren=2`、`loadingFactor=0.7`）。