Library / Data Structure to store convex polygon with holes

Question

I need to create a map of a building. The area is a convex polygon that has several non-overlapping convex holes. As a simplification, the area can also be expressed as a rectangle. The holes can also be modelled as rectangles.

I first tried to handle it with GEOS, a C++ library that comes with a low level C API. But it seemed that GEOS is not able to handle the amount of requests.

What is the best data structure to handle the map? Perhaps a quadtree? Is there any ready-to-use library (beyond academical proof-of-concept state)? The library should be C only (not C++).

Answer 1

Store the map as a list of directed line segments (so that we can determine if we're infront of or behind a segment):

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

Then partition the segments into a BSP-tree:

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

Then you can find the hole with this code:

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

If it is the case that each hole is a single rectangle you could BSP the set of rectangular holes until you have a single rectangle in each partition.

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

Answer 2

Since the number of holes is very small (less than 30), I used an array and did a linear search on this array. I was underestimating the speed of C, this approach is "fast enough".