图书馆/数据结构存储带孔的凸多边形

Question

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

我第一次试图用GEOS来处理它，这是一个C++库，它带有一个低级的C API 。但GEOS似乎无法处理请求数量。

什么是处理地图的最佳数据结构？ 也许是四叉树？是否有任何现成的图书馆 （超出学术概念证明状态）？ 该库应该只有C（而不是C++）。

Answer 1

由于孔的数量是非常小（小于30）， 我用的阵列，这样做，阵列上的线性搜索。 我低估了C的速度，这种方法“足够快”。

Answer 2

存储地图的指示线段的列表（这样我们就可以判断，如果我们是盈方的或后面的段）：

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