C語言實現四叉樹用於空間索引與快速查詢

四叉樹簡介

四叉樹是一種樹形數據結構，將二維空間遞歸劃分為四個象限（NE、NW、SW、SE），常用於空間索引、碰撞檢測、圖像壓縮等場景。本文提供一個完整的 C 語言實現，支持矩形邊界框插入與區域查詢，具備重疊區域處理機制以減少邊界邊緣對象的重複存儲。

核心數據結構

/* 象限枚舉 */
typedef enum { NE=0, NW=1, SW=2, SE=3 } QuadrantEnum;

/* 邊界框 */
typedef struct {
    double _xmin, _ymin, _xmax, _ymax;
} quadbox_t;

/* 四叉樹節點 */
typedef struct _quadnode_t {
    quadbox_t _box;           // 節點邊界框
    list_t *_lst;             // 存儲對象 ID 的鏈表
    struct _quadnode_t *_sub[4]; // 四個子節點指針
} quadnode_t;

/* 四叉樹 */
typedef struct {
    quadnode_t *_root;
    int _depth;               // 最大深度 (4~8)
    float _overlap;           // 子節點重疊比例 (0.02~0.4)
} quadtree_t;

關鍵算法

1. 邊界框分裂與重疊處理

為避免邊界邊緣對象頻繁上移至父節點，子節點邊界框向外擴展 overlap 比例：

static void quadbox_split(const quadbox_t* qb,
    quadbox_t* ne, quadbox_t* nw, quadbox_t* se, quadbox_t* sw,
    float overlap) {
    double dx = quadbox_width(qb) * (1.0 + overlap) / 2;
    double dy = quadbox_height(qb) * (1.0 + overlap) / 2;
    quadbox_init(ne, qb->_xmax-dx, qb->_ymax-dy, qb->_xmax, qb->_ymax);
    quadbox_init(nw, qb->_xmin, qb->_ymax-dy, qb->_xmin+dx, qb->_ymax);
    quadbox_init(sw, qb->_xmin, qb->_ymin, qb->_xmin+dx, qb->_ymin+dy);
    quadbox_init(se, qb->_xmax-dx, qb->_ymin, qb->_xmax, qb->_ymin+dy);
}

2. 插入邏輯

遞歸下降：若對象框完全包含於某子節點且未達最大深度，則進入該子節點；否則存入當前節點鏈表。

static quadnode_t* quadtree_insert_node(quadtree_t *tree,
    quadnode_t *parent, long node_key, quadbox_t *node_box, int *depth) {
    if (quadbox_is_inside(node_box, &parent->_box)) {
        if (++(*depth) < tree->_depth) {
            if (!quadnode_has_child(parent))
                quadnode_create_child(parent, tree->_overlap, *depth);
            // 嘗試四個象限
            if (quadbox_is_inside(node_box, &parent->_sub[NE]->_box))
                return quadtree_insert_node(tree, parent->_sub[NE], node_key, node_box, depth);
            if (quadbox_is_inside(node_box, &parent->_sub[NW]->_box))
                return quadtree_insert_node(tree, parent->_sub[NW], node_key, node_box, depth);
            if (quadbox_is_inside(node_box, &parent->_sub[SW]->_box))
                return quadtree_insert_node(tree, parent->_sub[SW], node_key, node_box, depth);
            if (quadbox_is_inside(node_box, &parent->_sub[SE]->_box))
                return quadtree_insert_node(tree, parent->_sub[SE], node_key, node_box, depth);
        }
    }
    quadnode_add_data(parent, node_key); // 存入當前節點
    return parent;
}

3. 區域查詢

深度優先搜索：若查詢框與節點框重疊，收集節點數據並遞歸搜索子節點。

static void quadtree_search_nodes(quadnode_t *node,
    quadbox_t *search_box, list_t *results) {
    if (quadbox_is_overlapped(&node->_box, search_box)) {
        if (quadnode_has_data(node))
            list_append_node(results, list_node_create(node));
        if (quadnode_has_child(node)) {
            quadtree_search_nodes(node->_sub[NE], search_box, results);
            quadtree_search_nodes(node->_sub[NW], search_box, results);
            quadtree_search_nodes(node->_sub[SW], search_box, results);
            quadtree_search_nodes(node->_sub[SE], search_box, results);
        }
    }
}

公共 API

• quadtree_create(box, depth, overlap)：創建樹，自動擴展根節點邊界。
• quadtree_destroy(qtree)：遞歸釋放所有節點與鏈表內存。
• quadtree_insert(qtree, node_key, node_box)：插入對象，返回存儲節點指針。
• quadtree_search(qtree, search_box, results_list)：查詢區域內對象，結果追加至鏈表。

依賴與編譯

需配合簡單單向鏈表實現（list.h/list.c）及 unistd.h。代碼遵循 C89 標準，可直接集成至項目。

優缺點對比

本實現適合對象分佈相對均勻、查詢允許少量誤報（後續精細過濾）的場景。