Douglas-Peucker 算法是一种用于简化折线的算法，常用于计算机图形学和地理信息系统中。它通过递归地去除不必要的点来简化折线，同时尽量保持折线的形状。
以下是一个简单的 Douglas-Peucker 算法的 C 语言实现示例：
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef struct {
double x;
double y;
} Point;
// 计算点到线段的距离
double perpendicularDistance(Point p, Point start, Point end) {
double nom = fabs((end.y - start.y) * p.x - (end.x - start.x) * p.y + end.x * start.y - end.y * start.x);
double denom = sqrt(pow(end.y - start.y, 2) + pow(end.x - start.x, 2));
return denom == 0 ? 0 : nom / denom;
}
// Douglas-Peucker 算法
void douglasPeucker(Point* points, int start, int end, double epsilon, int* result, int* resultCount) {
if (end <= start + 1) {
return;
}
double maxDistance = 0.0;
int index = -1;
// 找到最大距离的点
for (int i = start + 1; i < end; i++) {
double distance = perpendicularDistance(points[i], points[start], points[end]);
if (distance > maxDistance) {
maxDistance = distance;
index = i;
}
}
// 如果最大距离大于 epsilon，递归
if (maxDistance > epsilon) {
douglasPeucker(points, start, index, epsilon, result, resultCount);
result[(*resultCount)++] = index; // 添加中间点
douglasPeucker(points, index, end, epsilon, result, resultCount);
}
}
// 主函数
int main() {
Point points[] = {
{0, 0},
{1, 1},
{2, 0},
{3, 1},
{4, 0},
{5, 1},
{6, 0}
};
int numPoints = sizeof(points) / sizeof(points[0]);
double epsilon = 0.5; // 允许的误差
int* result = (int*)malloc(numPoints * sizeof(int));
int resultCount = 0;
// 添加起始点
result[resultCount++] = 0;
douglasPeucker(points, 0, numPoints - 1, epsilon, result, &resultCount);
// 添加结束点
result[resultCount++] = numPoints - 1;
// 输出结果
printf("简化后的点:\n");
for (int i = 0; i < resultCount; i++) {
printf("(%f, %f)\n", points[result[i]].x, points[result[i]].y);
}
free(result);
return 0;
}
代码说明：
- Point 结构体：用于表示二维点的结构体。
- perpendicularDistance 函数：计算一个点到一条线段的垂直距离。
- douglasPeucker 函数：实现 Douglas-Peucker 算法的递归函数。
- main 函数：定义了一组点，调用 Douglas-Peucker 算法，并输出简化后的点。
使用方法：
- 将上述代码复制到一个 C 语言编译器中，编译并运行。
- 可以通过修改
points 数组和 epsilon 值来测试不同的输入和简化程度。
希望这个实现对你有帮助！如果有任何问题，请随时问我。