c - 存储带孔凸多边形的库/数据结构

Question

我需要创建建筑物的 map 。该区域是一个凸多边形，具有多个不重叠的凸孔。作为简化，该区域也可以表示为矩形。这些孔也可以建模为矩形。

我首先尝试使用 GEOS 来处理它，这是一个随附的 C++ 库使用低级 C API。但似乎 GEOS 不能处理请求的数量。

处理 map 的最佳数据结构是什么？也许是四叉树？有没有现成的库(超出学术概念验证状态)？该库应该只有 C(不是 C++)。

Answer 1

将 map 存储为有向线段的列表(这样我们就可以确定我们是在线段的前面还是后面):

struct Segment {
    Pos2 p0;
    Pos2 p1;
    int holeIndex; //Which hole this segment delimits
};

然后将段划分为BSP-tree :

struct BSPNode {
    Segment partition;
    BSPNode* infront;
    BSPNode* behind;
};

然后你可以用这段代码找到漏洞:

int
findHole(BSPNode* node, Pos2 pos) {
    if (!node->behind) { // This node is a leaf
        if (isBehind(pos2, node->partition)) {
            return node->partition->holeIndex;
        } else {
            return -1; //Point is not in a hole
        }
    }
    if (isBehind(pos2, node->partition)) {
        return findHole(node->behind, pos);
    } else {
        return findHole(node->infron, pos);
    }
}

int hole = findHole(root, somePos);

如果是每个孔都是一个矩形的情况，您可以对矩形孔集进行 BSP，直到每个分区中都有一个矩形。

struct BSPNode {
    union {
        Rectangle rectangle; //leaf node
        DirectedLine splitter; //branch node
    };
    BSPNode* infront; // If null indicates this is a leaf node
    BSPNode* behind;
};

int
findHole(BSPNode* node, Pos2 pos) {
    if (!node->behind) { // This node is a leaf
        if (isInside(pos2, node->rectangle)) {
            return node->rectangle->holeIndex;
        } else {
            return -1; //Point is not in a hole
        }
    }
    if (isBehind(pos2, node->splitter)) {
        return findHole(node->behind, pos);
    } else {
        return findHole(node->infron, pos);
    }
}