Я создаю видеоигру, в которой двухмерный планарный граф строится ребром за ребром, и грани графа должны быть известны в любой заданной точке. Под «гранями» я подразумеваю циклы графа, которые не имеют ребер, пересекающих их на 2D-плоскости. Существовали ли алгоритмы / структуры данных, которые поддерживали инвариант при постепенном построении набора граней, в то время как граф также строился.
Для справки, вот видео, которое я нашел на YouTube .
Я буду sh, чтобы понять, как / если это возможно сделать с минимальными вычислениями при каждом добавлении одного ребра к графу. Я также пробовал смотреть на реализации полуребер и крылатых ребер двумерного плоского графа, но пока я не нашел ничего, что дало бы мне представление об этом. Большое спасибо!