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

Douglas-Peucker 简易版 C语言实现

Douglas-Peucker 算法是一种用于简化折线的算法，常用于计算机图形学和地理信息系统中。它通过递归地去除不必要的点来简化折线，同时尽量保持折线的形状。

以下是一个简单的 C 语言实现 Douglas-Peucker 算法的示例代码：

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct {
    double x;
    double y;
} Point;

// 计算点到线段的距离
double pointToSegmentDistance(Point p, Point p1, Point p2) {
    double A = p.x - p1.x;
    double B = p.y - p1.y;
    double C = p2.x - p1.x;
    double D = p2.y - p1.y;

    double dot = A * C + B * D;
    double len_sq = C * C + D * D;
    double param = -1;
    
    if (len_sq != 0) { // 线段长度不为零
        param = dot / len_sq;
    }

    double xx, yy;

    if (param < 0) {
        xx = p1.x;
        yy = p1.y;
    } else if (param > 1) {
        xx = p2.x;
        yy = p2.y;
    } else {
        xx = p1.x + param * C;
        yy = p1.y + param * D;
    }

    double dx = p.x - xx;
    double dy = p.y - yy;
    return sqrt(dx * dx + dy * dy);
}

// Douglas-Peucker 算法
void douglasPeucker(Point* points, int start, int end, double epsilon, int* result, int* resultCount) {
    if (end <= start + 1) {
        return;
    }

    double maxDistance = 0;
    int index = -1;

    // 找到最大距离的点
    for (int i = start + 1; i < end; i++) {
        double distance = pointToSegmentDistance(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);
    } else {
        // 否则只保留起始和结束点
        if (*resultCount == 0 || result[*resultCount - 1] != start) {
            result[(*resultCount)++] = start;
        }
        if (*resultCount == 0 || result[*resultCount - 1] != end) {
            result[(*resultCount)++] = end;
        }
    }
}

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;

    // 调用 Douglas-Peucker 算法
    douglasPeucker(points, 0, numPoints - 1, epsilon, result, &resultCount);

    // 输出结果
    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. pointToSegmentDistance 函数：计算一个点到线段的距离。
3. douglasPeucker 函数：实现 Douglas-Peucker 算法的核心逻辑。
4. main 函数：提供示例数据，调用算法并输出简化后的点。

使用方法：

• 将上述代码复制到 C 语言编译器中，编译并运行。
• 可以根据需要调整 points 数组和 epsilon 值，以测试不同的输入数据和简化程度。