0

Имеется массив ребер фигуры, ребро хранится как отдельный объект который имеет два поля: точка А и точка Б, каждая точка хранит свои координаты Х и У. Фигура может быть многосвязной и тогда этот массив нужно разбить на количество областей этой фигуры. Как это сделать?

1 ответ 1

3

Ваши входные данные - это очевидное готовое неявное представление графа, где вершины фигуры - это вершины графа, а ребра фигуры - это ребра графа. Задача сводится к ответу на вопрос о связности этого графа и решается любым подходящим алгоритмом.

В качестве off-line алгоритма можно построить граф, сделать его полный обход любым поисковым алгоритмом и проверить, нашли ли мы все его вершины. Каждый такой обход (начинающийся с любой ненайденной вершины) будет давать нам отдельную компоненту связности.

В качестве on-line алгоритма можно рассматривать эту задачу как задачу на слияние множеств. Изначально каждая вершина фигуры принадлежит отдельному множеству. Каждое ребро фигуры вызывает слияние множеств, содержащих его вершины. Если после обработки всех ребер останется только одно множество - то контур фигуры является связным. После обработки всех ребер каждое такое множество - это отдельная компонента связности.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.