一、矢量数据压缩
1、隔点抽样法
（1）基本原理：最简单粗暴的压缩方式。设定一个步长 n（例如 n = 2），从起点开始，每隔 n-1 个点保留一个点，其余点全部剔除。首尾两点通常强制保留。
（2）实现思路：遍历坐标点数组，利用索引取模（index % n == 0）来判断是否将该点加入新数组。
（3）优缺点：计算极快，但在地形复杂、曲率变化大的地方会严重失真，在平直的地方又保留了过多没必要的点。
（4）代码：
i == 0 || i = n – 1表示一定保持头尾节点
2、垂距法
（1）基本原理：一种顺序化简法。连接曲线的起点 A 和终点 B 作为基线。计算中间所有点到这条基线的垂直距离（垂距）d。如果 d > 阈值，则保留该点。如果 d < 阈值 ，则该点被认为不重要，予以剔除。
（2）实现思路：依次遍历中间点，利用点到直线的距离公式计算垂距并与阈值比较。
3、道格拉斯-普克算法 (DP算法)
（1）基本原理：这是目前最经典、效果最好的线化简算法，本质是一个分治算法 (Divide and Conquer)。
（2）实现步骤：
连接起点 A 和终点 B 形成一条基线。
计算曲线上所有中间点到这条基线的垂距，找到距离最大且大于给定阈值 的点 C。
如果最大的垂距也小于阈值，则中间所有点都舍弃，化简结束。
如果找到了点 C（保留点 C），则以 C 为界，将曲线分为 AC 和 CB 两段。
对 AC 和 CB 两段递归重复上述步骤，直到没有点满足条件为止。
（3）实现思路：非常适合用递归函数来实现。输入点集、起始索引、结束索引和容差阈值。
（4）代码：
4、光栏法 (Corridor Method)
1. 初始光束（打开手电筒）
- 你站在起点 P_1，看向下一个点 P_2。
- 你从起点 P_1 向 P_2 周围的那个“容差圆”发射两根相切的射线。这两根射线之间形成了一个扇形的区域，这就是你的“初始光栏”或者说初始的探照灯光束）。
- 只要后面的点能落在这个光束里，说明折线还算平直，没有发生太大的弯折。
2. 光束收缩（不断取交集）
- 接着你站在原地看向第三个点 P_3。同样地，从 P_1 向 P_3 的“容差圆”发射切线，形成一个新的扇形。
- 核心动作来了：你必须把旧的“光栏”和新的扇形取交集（重叠部分），作为新的“有效光栏”。
- 因为要同时满足穿过 P_2 的容差圆和 P_3 的容差圆，你的手电筒光束就会被迫变得越来越窄。
3. 触发断点（光照不到的地方）
- 你继续往下扫描 P_4、P_5…… 每次都用 P_1 到新点的扇形去和当前的光栏取交集。光栏越来越窄。
- 直到扫描到某一个点 P_n 时，你发现：从 P_1 到 P_n 容差圆形成的扇形，跟当前的“有效光栏”完全没有重叠了（交集为空）！
- 这意味着折线在这个地方发生了极其剧烈的拐弯，之前的光束已经“照不到”它了。
4. 保留并重启
- 既然 P_n 偏离太远，我们就把导致光束失效的前一个点——即 P_{n-1}——强制保留下来。
- 然后，你把起点移动到 P_{n-1}，把它当成新的 P_1，重新打开手电筒，对着下一个点继续重复上面的过程，直到整条线扫描完毕。
5、Li & Openshaw 算法
1、确定网格大小（关键点）
网格的大小（每个小格子的边长 g）不是随便定的，它是根据目标比例尺计算出来的。
比如：如果你要把 1:1 万的地图缩减到 1:5 万，网格就会变大。这个网格代表了人类眼睛在那个比例尺下能看清的“最小细节”。
2、叠加（栅格化视角的介入）
把你的矢量线“躺”在这个网格阵列里。此时，这条线会穿过很多个小格子。
3、筛选（每个格子只留一个代表）
这是该算法最核心的“自然法则”：在一个网格的范围内，人的视觉无法分辨太细微的抖动。
- 算法会检查每一个被线条穿过的格子。
- 如果一条线在一个格子里绕了好几个弯（有好几个坐标点），算法只会在这个格子里保留一个点。
- 选哪个点？ 通常有几种策略：
- 最靠近格子中心的原有坐标点。
- 线条进入格子的进入点和离开点的中点。
- 格子内所有点的平均位置。
4、重连
将每个格子选出的“代表点”按原顺序连接起来，就得到了一条平滑且数据量极大的简化的矢量线。
5、如果两个点离得太近，近到在目标比例尺下连成了一个像素点，那保留两个点就没有意义。
二、栅格数据压缩
1、游程编码 (Run-length Encoding, RLE)
（1）基本原理：逐行扫描栅格，将相邻且属性值相同的像元合并，记录“属性值”和“连续出现的次数（游程长度）”。
- 示例：某一行像元值为
A A A A B B C C C，游程编码后变为(A, 4), (B, 2), (C, 3)。
（2）实现思路：使用双指针或计数器遍历二维数组的每一行，当当前值与前一个值不同时，记录前一个值的总数并重置计数器。
（3）代码实现：
/* 游程编码 */
Run* rle_encode(char* data, int n, int* out_len) {
Run* runs = (Run*)malloc(n * sizeof(Run));
int j = 0;
int i = 0;
while (i < n) {
int cnt = 1;
while (i + cnt < n && data[i + cnt] == data[i]) {
cnt++;
}
runs[j].value = data[i];
runs[j].count = cnt;
j++;
i += cnt;
}
*out_len = j;
return runs;
}/* 对二维字符串按行进行游程编码 */
void rle_encode_2d(char* data[], int rows, int cols) {
for (int r = 0; r < rows; r++) {
int run_len = 0;
Run* runs = rle_encode(data[r], cols, &run_len);
for (int i = 0; i < run_len; i++) {
printf("(%c, %d) ", runs[i].value, runs[i].count);
}
free(runs);
}
}2、块状编码
基本原理：游程编码是二维数据的一维化压缩，而块码是真正的二维压缩。它将具有相同属性的相邻多边形区域划分成正方形的“块”。数据结构中记录正方形的中心点（或左下角）坐标、正方形的边长（或半径）以及属性值。
3、四叉树编码
- 基本原理：一种递归划分空间的树状结构。将整个栅格区域均分为四个象限（子区域）。
- 如果某个子区域内所有像元的属性值完全一致，该区域就不再划分，成为树的叶子节点，并记录该属性值。
- 如果子区域内包含不同的属性值，则将其继续等分为四个更小的子区域，直到划分出的区域属性单一，或者达到了像元的最小分辨率。
- 这在空间数据库索引和海量图像压缩中极其常用。
4、链码 (Chain Code)
基本原理：主要用于记录面状要素的边界。它不记录内部所有像元，而是从边界上的某一起点开始，按照特定的方向（通常使用 0 – 7 代表八个方向）一步步追踪边界，记录下移动的方向序列。
- 示例：沿着边界走，可能记录为
起点坐标 + 方向序列(0, 1, 1, 2, 4...)。