Библиотека / Структура данных для хранения выпуклого многоугольника с отверстиями - PullRequest
2 голосов
/ 02 декабря 2009

Мне нужно создать карту здания. Область представляет собой выпуклый многоугольник, имеющий несколько непересекающихся выпуклые отверстия. Для упрощения область также может быть выражена в виде прямоугольника. Отверстия также могут быть смоделированы как прямоугольники.

Сначала я попытался справиться с этим с помощью GEOS, библиотеки C ++, с низким уровнем C API. Но казалось, что GEOS не умеет обрабатывать количество запросов.

Какая структура данных лучше всего подходит для обработки карты? Возможно квадри? Есть ли готовая библиотека? (за пределами академического доказательства концепции)? Библиотека должна быть только C (не C ++).

Ответы [ 2 ]

2 голосов
/ 02 декабря 2009

Сохранить карту в виде списка направленных отрезков (чтобы мы могли определить, находимся ли мы перед сегментом или позади него):

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);
    }
}
1 голос
/ 12 декабря 2009

Поскольку количество отверстий очень мало (менее 30), Я использовал массив и сделал линейный поиск по этому массиву. Я недооценивал скорость C, этот подход «достаточно быстр».

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...