GPU 只认三角形，地图面要素无论凹或带洞都得先切。耳切法加 z-order 加速，是渲染的隐形功臣。
前言
你可能没想过：地图上一个再复杂的"面"（湖泊、行政区、地块），到了 GPU 眼里都只是一堆三角形。GPU 只认三角形，其他一切几何——多边形、带洞的多边形、凹多边形——都必须在上传前被"切"成三角形。
这个切的过程叫三角化。它藏在每次地图渲染的背后，却又很少有人讲清楚。而它处理的输入往往一点都不友好：可能是凹的、带洞的、甚至有点自相交的。这套地图引擎采用的正是业界著名的耳切法（ear clipping），并做了大量工程优化。本篇就拆开讲讲。
一、根因：为什么非要把多边形切成三角形
OpenGL 的光栅化器（把顶点变成像素的那一步）只原生支持三角形。三角形是"最简单、永远凸、好插值"的基本单元。
所以任何多边形在送进 GPU 前，都要先拆成三角形。而这个"拆"是有讲究的：
- 凹多边形：不能直接当成一个三角形扇来画，否则会画出凹口外面的部分。
- 带洞多边形：外环里面还挖了洞（比如湖泊中间有岛），洞得处理掉。
- 性能：三角形数量越少越好，多余的三角形浪费显存和绘制时间。
三角化算法的质量，直接影响 GPU 的绘制效率和渲染正确性。
三角化质量直接决定了 GPU 的绘制效率与渲染正确性。
二、解法：耳切法 + 哈希加速 + 洞消除
2.1 基本思想：不断"切耳朵"
"耳"是这么定义的：多边形里一个顶点，它的前一个顶点、它自己、后一个顶点组成的三角形，完全位于多边形内部，且中间没有其他顶点。这样的"凸耳朵"切下来不会出错。
算法很直观：找到一只耳朵，切成一个三角形，把那个顶点从多边形里删掉；剩下的多边形继续找耳朵、切、删……直到只剩最后一个三角形。
下面这段就是耳切的主循环：
fun earcut(vertices: DoubleArray): List<Int> {
val triangles = mutableListOf<Int>()
val ring = buildRing(vertices) // 环形双向链表
while (ring.hasMoreThan3()) {
val ear = findEar(ring) // 找一个凸耳朵
if (ear == null) break
triangles += listOf(prev(ear), ear, next(ear)) // 切成三角形
ring.remove(ear) // 删掉耳朵顶点
}
return triangles
}
关键步骤是"判断某顶点是否形成合法耳朵"：既要凸（叉积符号正确），又要保证三角形内部没有其他顶点。
2.2 用 z-order 哈希加速"找耳朵"
朴素实现里，每次判断"耳朵里有没有别的点"都要遍历整个剩余多边形，O(n²) 在大多边形上会卡。这里的优化是：先算出所有顶点的 z-order 曲线（一种把 2D 坐标映射成一维有序数的空间填充曲线），让空间上靠近的点在 z 值上也靠近。
z-order 编码的示意如下：
// z-order 编码（示意）：把 (x,y) 映射成一维整数
fun zOrder(x: Double, y: Double, minX: Double, minY: Double, invSize: Double): Double {
var ix = (32767 * (x – minX) * invSize).toInt()
var iy = (32767 * (y – minY) * invSize).toInt()
// 位交错编码
ix = spread(ix); iy = spread(iy)
return (ix or (iy shl 1)).toDouble()
}
找耳朵时，根据耳朵三角形的包围盒算出 z 范围，只在这个范围内的点里检查是否落在三角形内——把大部分无关顶点一次性排除，接近 O(n log n)。
2.3 消除洞：找一座"桥"把洞接进外环
带洞多边形不能直接切。做法是找一条把"洞"和"外环"连起来的边（叫桥），把洞"焊"进外环，变成单个环，再整体耳切。
找桥并焊入外环的逻辑如下：
fun eliminateHoles(holes: List<Node>, outer: Node): Node {
// 按最左点排序，从左到右逐个焊入
val sorted = holes.sortedBy { it.leftmost.x }
var ring = outer
for (hole in sorted) {
val bridge = findHoleBridge(hole, ring) // 找桥
if (bridge != null) ring = splitPolygon(bridge, hole)
}
return ring
}
找桥用的是"从洞的最左点向左射一条射线，找与它相交的最近外环边"这类几何判断，属于这个算法里最精巧的一部分。
2.4 兜底策略：耳切找不到耳朵时的三层降级
真实数据总有刁钻情况——自相交、退化、共线点。耳切法主循环可能"切不下去"，这时按三层策略降级：
这三层兜底保证了算法在极端输入下也不会失败或无限循环，工程健壮性很重要。
三层兜底让耳切法在极端输入下也不会失败或死循环。
三、升华：三角化不止一种，耳切法的定位
耳切法不是唯一三角化算法，还有更复杂的约束 Delaunay 三角剖分。两者取舍：
- 耳切法：实现相对简单、快，适合地图面要素这种"简单多边形为主"的输入。
- CDT：能处理更复杂的约束（如强制某些边存在），但实现和开销都高。
地图面要素大多是简单多边形，耳切法在性能和复杂度之间是很好的平衡。它甚至被做成了独立的小工具库被广泛移植——这套引擎里的实现就是一次经典移植，附带完整的三层兜底。
结论
- GPU 只画三角形，任何多边形都必须先三角化，这一步藏在每次渲染背后。
- 耳切法本质是"找凸耳朵 → 切下 → 删顶点"，循环直到只剩一个三角形。
- 用 z-order 曲线哈希加速"耳朵内是否有别的点"的判断，从 O(n²) 降到接近 O(n log n)。
- **带洞多边形通过"找桥焊入外环"**变成一个环再整体切。
- 自相交等刁钻输入靠"过滤 → 局部修复 → 拆分"三层兜底保证不失败。
你处理过哪些"带洞""自相交"的复杂面要素？在评论区聊聊你用什么方案三角化吧。
关键词标签：#Android #三角化 #耳切法 #GIS #OpenGL #z-order #地图渲染 #Kotlin
