Сохранить карту в виде списка направленных отрезков (чтобы мы могли определить, находимся ли мы перед сегментом или позади него):
struct Segment {
Pos2 p0;
Pos2 p1;
int holeIndex; //Which hole this segment delimits
};
Затем разделите сегменты на BSP-дерево :
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);
}
}