Алгоритм идентификации "замкнутых поверхностей" в графе

У меня есть приложение для рисования, где пользователи могут создавать узлы или ребра, вводя данные (без "прямого рисования" с помощью курсора):

Node(double xpos, double ypos)
Edge(Node startNode, Node endNode)

Теперь я ищу алгоритм, который идентифицирует замкнутые поверхности, созданные графом пользователя. Под замкнутой поверхностью я подразумеваю все области, которые полностью окружены ребрами. Например, наименьшая возможная поверхность была бы треугольником с тремя узлами и тремя ребрами (1->2, 2->3, 3->1). Конечно, это может усложниться, например, когда несколько ребер совместно используют один узел.

Я уверен, что для этого должно быть несколько алгоритмов, но пока мои поиски не увенчались успехом (возможно, потому, что английский не мой родной язык, и я не знаком со специальным словарем в этой области). Так что любая помощь, которая подтолкнет меня в правильном направлении, будет высоко оценена.

Следующим шагом будет наличие вложенных поверхностей и всех возможных комбинаций. Я создал пример изображения, но мне не хватает представителя, чтобы опубликовать его здесь, так что это ссылка: пример изображения с вложенными поверхностями. На рисунке показаны два прямоугольника, которые создают три возможных поверхности, которые можно назвать И (синим), ИЛИ (красным) и ХОР (зеленым). Существуют ли настолько простые алгоритмы, что их реализация не превратится в тезис информатики? Или вы бы порекомендовали перейти на существующие решения?

0 ответов

Другие вопросы по тегам