TG的Natural索引原理剖析：为何仅用7%额外内存就让point-in-polygon查询提速百倍

TG的Natural索引原理剖析：为何仅用7%额外内存就让point-in-polygon查询提速百倍

【免费下载链接】tgGeometry library for C - Fast point-in-polygon项目地址: https://gitcode.com/gh_mirrors/tg3/tg

TG 是一个专为实时地理空间场景设计的 C 语言几何库，其招牌能力是极速的 point-in-polygon（点在多边形内）判断——这正是地理围栏、流式监控等场景最核心的操作。而这一切的幕后功臣，是它独创的 Natural 索引结构：仅用约 7% 的额外内存，就能让大型多边形的查询速度提升上百倍。本文将以通俗易懂的方式，为你层层剖析 Natural 索引的原理与实战表现。

什么是 point-in-polygon：先从射线投射算法说起

point-in-polygon 问题看似简单：给定一个点和一块多边形区域，判断这个点落在区域内还是区域外。TG 内部采用的是经典的射线投射（ray casting）算法：从被测点沿 X 轴方向画一条无限延伸的虚拟射线，然后统计这条射线与多边形各条线段的交点数量——交点数为奇数则点在多边形内，偶数则在外部。

这个算法逻辑清晰，但有一个致命短板：为了找到射线与哪些线段相交，朴素实现必须逐条扫描多边形的所有线段。对于只有几十个点的小多边形，这当然很快；可当地理数据动辄上万、甚至十几万个顶点时（比如一个国家或省份的边界），每次判断都要遍历全部线段，耗时随顶点数线性增长，性能急剧恶化。

TG 的官方文档 docs/POLYGON_INDEXING.md 中，用一组动图直观展示了射线的扫描过程，感兴趣的读者可以对照查看。

朴素方案的痛点：O(n) 全量扫描有多慢？

让我们用一组真实基准数据感受一下"无索引"的代价。TG 的测试基准 docs/BENCHMARKS.md 中，使用巴西（Brazil）边界多边形进行 point-in-polygon 测试，该多边形拥有39914 个顶点：

方案	每秒操作数	单次耗时	索引构建时间	总内存
tg 无索引	96,944	10,315 ns	46.73 µs	638,720 B
tg Natural 索引	10,143,419	99 ns	53.17 µs	681,360 B
tg YStripes 索引	15,174,761	66 ns	884.06 µs	1,059,548 B
GEOS 无索引	29,708	33,661 ns	135.18 µs	958,104 B
GEOS Prepared 索引	7,885,512	127 ns	2,059.94 µs	3,055,496 B

可以看到，无索引时单次判断需要约 10 微秒，而启用 Natural 索引后骤降至99 纳秒，提速超过 100 倍；同时内存仅从 638,720 字节增至 681,360 字节，增幅约 6.7%——这正是"7% 额外内存"说法的由来。构建索引本身也只多了约 6 微秒的开销，几乎可以忽略。

传统 R-tree：能加速，但代价不小

既然全量扫描太慢，一个自然的思路是引入空间索引。业界最常见的方案是 R-tree：把多边形的每条线段用其最小包围矩形（MBR）表示，再将这些矩形组织成一棵树。查询时只需沿着树向下搜索与射线相交的矩形，就能跳过大量无关线段，把复杂度从 O(n) 降到 O(log n)。

然而传统 R-tree 有两个难以忽视的缺点。其一，构建代价高：建树需要对线段进行排序、划分叶节点、逐层创建分支节点，整个过程相当耗时；其二，内存占用大：树节点中要额外存储大量指针和矩形信息，索引体积常常超过原始多边形本身的两倍。对于追求实时性的场景，这显然不够优雅。

下图展示了有无索引时，随着多边形线段数量增加，单次操作耗时的对比——无索引（绿色）耗时随段数线性飙升，而索引后（红色）几乎保持水平：

Natural 索引：长得像 R-tree，却几乎不花内存

TG 的 Natural 索引正是为解决上述痛点而生，它在 tg.h 中以TG_NATURAL枚举形式对外暴露。其核心设计理念可以概括为两句话：矩形存得紧凑，叶子不重复存。

传统 R-tree 把矩形散落在各个树节点中，而 Natural 索引把所有分支矩形按层级连续存放在内存中，形成类似"多级数组"的结构；更精妙的是，最底层的"叶子级"根本不需要额外存储——它直接复用多边形线段数组本身，让线段保持其"自然顺序"，索引只负责记录每一层矩形的边界信息。

这种设计带来两个直接收益：

• 内存极小：整个 Natural 索引的额外内存仅为原始多边形的 7% 左右，远低于传统 R-tree。
• 构建飞快：由于索引大小和每层矩形数量都能在扫描线段前精确算出，构建过程只需对线段做单趟遍历，一边读取一边填充矩形即可完成。官方文档给出的数据是：现代硬件上每秒可索引超过 10GB 的点数据。

此外，叶子级与线段数组共享内存还有一个隐藏优势——减少内存读取次数，让 CPU 缓存命中率更高，查询自然更快。相关实现细节集中在 tg.c 的索引构建核心循环中，配合 docs/POLYGON_INDEXING.md 中的原理说明（含动画演示）可以看得更明白。

与 YStripes、GEOS 的横向对比

除了 Natural，TG 还提供了另一种索引 YStripes（TG_YSTRIPES），它把线段偏移量组织成类似哈希表的"条带"结构，point-in-polygon 速度比 Natural 再快约 50%。但天下没有免费的午餐：YStripes 的内存占用约为原多边形的 50%，构建时间更是比 Natural 慢约 20 倍。

而对比成熟的 GIS 库 GEOS：其 PreparedGeometry 索引虽然也能把查询提速到 7.8M ops/sec，但内存占用高达 3MB（是 TG Natural 方案的 4 倍以上），构建耗时更是达到 2 毫秒级。也就是说，TG 用更小的内存和更快的构建，实现了更快的查询。

两者的取舍很清楚：Natural 适合日常全面使用，YStripes 适合点查询占绝对主导、且对峰值性能有极致要求的场景——两者甚至可以叠加使用。

开箱即用：默认开启，无需任何配置

对普通开发者来说，最友好的部分是：Natural 索引默认就是开启的。TG 在 tg.c 中将默认索引类型设置为TG_NATURAL，凡是顶点数不少于 32 个的多边形，都会在创建时自动完成索引构建，开发者无需修改任何代码即可享受百倍提速。若想手动控制，也可以通过tg_env_set_index()、tg_ring_new_ix()等 API 显式指定索引类型，完整的接口说明见 docs/API.md。

总结

• 慢的根源：射线投射算法朴素实现需全量扫描线段，复杂度 O(n)。
• R-tree 的遗憾：能降到 O(log n)，但构建慢、内存可能翻倍。
• Natural 的巧妙：分支矩形连续存储、叶子级共享线段数组，内存仅多 7%。
• 实测战绩：39K 顶点多边形，point-in-polygon 从 96,944 提升到 10,143,419 ops/sec，提速逾百倍，构建开销微乎其微。
• 零成本接入：默认开启，32 点以上多边形自动索引。

如果你正在为地理围栏、实时监控或流式空间分析寻找高性能的几何计算方案，TG 的 Natural 索引无疑是一个值得尝试的答案——用 7% 的内存，换来百倍的查询速度，这笔账怎么算都划算。

【免费下载链接】tgGeometry library for C - Fast point-in-polygon项目地址: https://gitcode.com/gh_mirrors/tg3/tg