Douglas-Peucker 算法的 C 语言实现示例

Douglas-peucker 算法 C语言实现

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;
}

代码说明：

1. Point 结构体：用于表示二维点的结构体。
2. perpendicularDistance 函数：计算一个点到一条线段的垂直距离。
3. douglasPeucker 函数：实现 Douglas-Peucker 算法的递归函数。
4. main 函数：定义了一组点，调用 Douglas-Peucker 算法，并输出简化后的点。

使用方法：

• 将上述代码复制到一个 C 语言编译器中，编译并运行。
• 可以通过修改 points 数组和 epsilon 值来测试不同的输入和简化程度。

希望这个实现对你有帮助！如果有任何问题，请随时问我。