扫描线填充算法c语言

以下是一个简单的扫描线填充算法的C语言实现：

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

// 定义颜色
#define FILL_COLOR WHITE
#define BORDER_COLOR RED

// 定义一个点
typedef struct {
    int x, y;
} POINT;

// 定义一个边界
typedef struct {
    int y_max;
    float x;
    float slope_inv;
} EDGE;

// 定义一个边界链表节点
typedef struct edge_node {
    EDGE edge;
    struct edge_node *next;
} EDGE_NODE;

// 定义边界链表
typedef struct {
    EDGE_NODE *head;
    EDGE_NODE *tail;
} EDGE_LIST;

// 定义扫描线填充函数
void scanline_fill(int n, POINT *points)
{
    EDGE_LIST *edge_table, active_edges;
    EDGE_NODE *edge_node, *prev_node, *curr_node, *next_node;
    EDGE *edge, temp_edge;
    POINT *p1, *p2, *temp_p;
    int i, j, k, y_min, y_max, y, x, nodes_added;
    float m;

    // 寻找最大和最小的y值
    y_min = points[0].y;
    y_max = points[0].y;
    for (i = 1; i < n; i++) {
        if (points[i].y < y_min) {
            y_min = points[i].y;
        }
        if (points[i].y > y_max) {
            y_max = points[i].y;
        }
    }

    // 初始化边界链表
    edge_table = (EDGE_LIST *)calloc(y_max - y_min + 1, sizeof(EDGE_LIST));
    if (edge_table == NULL) {
        return;
    }

    // 构造边界链表
    for (i = 0; i < n; i++) {
        p1 = &points[i];
        p2 = &points[(i + 1) % n];
        if (p1->y == p2->y) {
            continue;
        }

        if (p1->y < p2->y) {
            temp_p = p1;
            p1 = p2;
            p2 = temp_p;
        }

        edge_node = (EDGE_NODE *)malloc(sizeof(EDGE_NODE));
        if (edge_node == NULL) {
            return;
        }

        edge = &edge_node->edge;
        edge->y_max = p1->y;
        edge->slope_inv = ((float)(p1->x - p2->x)) / (p1->y - p2->y);
        edge->x = p1->x;

        // 添加边界节点到边界链表
        j = p1->y - y_min;
        if (edge_table[j].head == NULL) {
            edge_table[j].head = edge_node;
            edge_table[j].tail = edge_node;
            edge_node->next = NULL;
        } else {
            prev_node = NULL;
            curr_node = edge_table[j].head;
            while (curr_node != NULL && curr_node->edge.x < edge->x) {
                prev_node = curr_node;
                curr_node = curr_node->next;
            }

            if (prev_node == NULL) {
                edge_node->next = curr_node;
                edge_table[j].head = edge_node;
            } else {
                edge_node->next = prev_node->next;
                prev_node->next = edge_node;
            }

            if (edge_node->next == NULL) {
                edge_table[j].tail = edge_node;
            }
        }
    }

    // 初始化活动边界链表
    active_edges.head = NULL;
    active_edges.tail = NULL;

    // 扫描线填充
    for (y = y_min; y <= y_max; y++) {
        // 将新的边界添加到活动边界链表
        edge_node = edge_table[y - y_min].head;
        while (edge_node != NULL) {
            nodes_added = 0;
            if (active_edges.head == NULL) {
                active_edges.head = edge_node;
                active_edges.tail = edge_node;
                edge_node->next = NULL;
            } else if (edge_node->edge.x < active_edges.head->edge.x) {
                edge_node->next = active_edges.head;
                active_edges.head = edge_node;
            } else {
                prev_node = active_edges.head;
                curr_node = active_edges.head->next;
                while (curr_node != NULL && edge_node->edge.x > curr_node->edge.x) {
                    prev_node = curr_node;
                    curr_node = curr_node->next;
                }
                edge_node->next = prev_node->next;
                prev_node->next = edge_node;
                if (edge_node->next == NULL) {
                    active_edges.tail = edge_node;
                }
            }
            edge_node = edge_node->next;
        }

        // 删除不再活动的边界
        prev_node = NULL;
        curr_node = active_edges.head;
        while (curr_node != NULL) {
            if (curr_node->edge.y_max == y) {
                if (prev_node == NULL) {
                    active_edges.head = curr_node->next;
                } else {
                    prev_node->next = curr_node->next;
                }
                if (curr_node->next == NULL) {
                    active_edges.tail = prev_node;
                }
                next_node = curr_node->next;
                free(curr_node);
                curr_node = next_node;
                continue;
            }
            prev_node = curr_node;
            curr_node = curr_node->next;
        }

        // 填充扫描线
        curr_node = active_edges.head;
        while (curr_node != NULL && curr_node->next != NULL) {
            for (x = (int)curr_node->edge.x; x < (int)curr_node->next->edge.x; x++) {
                putpixel(x, y, FILL_COLOR);
            }
            curr_node = curr_node->next->next;
        }

        // 更新活动边界的x值
        curr_node = active_edges.head;
        while (curr_node != NULL) {
            edge = &curr_node->edge;
            edge->x += edge->slope_inv;
            curr_node = curr_node->next;
        }
    }

    // 画边界
    for (i = 0; i < n; i++) {
        p1 = &points[i];
        p2 = &points[(i + 1) % n];
        line(p1->x, p1->y, p2->x, p2->y);
    }

    // 释放内存
    for (i = 0; i < y_max - y_min + 1; i++) {
        edge_node = edge_table[i].head;
        while (edge_node != NULL) {
            next_node = edge_node->next;
            free(edge_node);
            edge_node = next_node;
        }
    }
    free(edge_table);
}

// 测试函数
int main()
{
    int gd = DETECT, gm;
    initgraph(&gd, &gm, "");

    POINT points[] = {{100, 100}, {200, 150}, {150, 200}, {50, 150}};
    int n = sizeof(points) / sizeof(points[0]);

    setcolor(BORDER_COLOR);
    scanline_fill(n, points);

    getch();
    closegraph();
    return 0;
}

该实现基于边界表和活动边界表，首先根据给定的多边形顶点构造边界表，然后扫描线从上往下扫描，将跨越扫描线的边界添加到活动边界表中，然后删除不再活动的边界，对活动边界进行排序，填充扫描线上的像素，并更新活动边界的x值，直到扫描完整个多边形。