Граф на плоскости, (надо получить циклы) Опции

[hardcase]

Значицца появился у меня вопросик.

Есть граф. Каждая вершина у него имеет координаты на плоскости (x y).
Нужно просто получить ячейки (полигоны), образованные рёбрами в графе. (Как в витраже)

Если можете, подскажите алгоритм. Уж с кодом я справлюсь.

[Altair]

Нужно просто получить ячейки (полигоны), образованные рёбрами в графе. (Как в витраже)

не ясна цель.
Пример входных и выходных данных.

[hardcase]

Нету входных данных.
Просто есть граф. У каждой вершины - координаты на плоскости.
Вершины соединены рёбрами. Рёбра не пересекаются.

Нужно мне получить в графе все полигоны, которые образуют ребра графа.
(полигоны не должны пересекаться)

Сообщение отредактировано: hardcase - 9.01.2006 3:22

[Altair]

у программы нет входных данных?
если я тебя правильно понял (ты не можешь сформулировать задачу точно)
тебе надо провести триангуляцию.

[volvo]

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

[hardcase]

А я и не прошу программы.
Мне нужет только алгоритм. Программку, при наличии алгоритма, набить - без проблем.

Буду очень признателен за помощь.


Я тут подумал. здесь нужно не триангулировать, а как-то хитро обойти вершины.

Сообщение отредактировано: hardcase - 9.01.2006 3:58

[volvo]

Вот эта тема:
поиск минимальной траектории (хотя, возможно, это не совсем твой случай...)

[hardcase]

Если это евклидов граф, т.е. вершины являются точками на плоскости, а ребра - отрезками, то это получается алгоритм построения минимальных полигонов.
Примерно так: начинаем с крайне-левой (например) вершины, в каждом узле выбираем ближайшее (по или против часовой стрелки) ребро, пока не замкнем цикл. Переходим к следущей вершине. И т.д. Ребра по дороге помечаем - каждое ребро можно пройти не более чем дважды.
Однако, это для ненаправленного графа. Для направленного тоже, наверно, как то можно приспособить, но не знаю, как получить все полигоны.

Примерно к такому же алгоритму я и пришёл. Только что-то мне не понавилось в нём.
Ладно с утреца разберусь. Ато щас соображалка туго варит.