Значицца появился у меня вопросик.
Есть граф. Каждая вершина у него имеет координаты на плоскости (x y).
Нужно просто получить ячейки (полигоны), образованные рёбрами в графе. (Как в витраже)
Если можете, подскажите алгоритм. Уж с кодом я справлюсь.
Полная версия: Граф на плоскости
Цитата
Нужно просто получить ячейки (полигоны), образованные рёбрами в графе. (Как в витраже)
не ясна цель.
Пример входных и выходных данных.
Нету входных данных.
Просто есть граф. У каждой вершины - координаты на плоскости.
Вершины соединены рёбрами. Рёбра не пересекаются.
Нужно мне получить в графе все полигоны, которые образуют ребра графа.
(полигоны не должны пересекаться)
Просто есть граф. У каждой вершины - координаты на плоскости.
Вершины соединены рёбрами. Рёбра не пересекаются.
Нужно мне получить в графе все полигоны, которые образуют ребра графа.
(полигоны не должны пересекаться)
у программы нет входных данных? 
если я тебя правильно понял (ты не можешь сформулировать задачу точно)
тебе надо провести триангуляцию.
если я тебя правильно понял (ты не можешь сформулировать задачу точно)
тебе надо провести триангуляцию.
Ты знаешь, на Винограде (в разделе Паскаль) по-моему поднималась эта (или очень похожая) проблема, где-то в середине - конце июня прошлого года; насколько я помню, автор темы как раз говорил, что алгоритм у него есть, и ему нужна была реализация... Попробую найти ссылку, если что - свяжись с автором, может он реализовал, или хотя-бы алгоритм возьмешь...
А я и не прошу программы.
Мне нужет только алгоритм. Программку, при наличии алгоритма, набить - без проблем.
Буду очень признателен за помощь.
Я тут подумал. здесь нужно не триангулировать, а как-то хитро обойти вершины.
Мне нужет только алгоритм. Программку, при наличии алгоритма, набить - без проблем.
Буду очень признателен за помощь.
Я тут подумал. здесь нужно не триангулировать, а как-то хитро обойти вершины.
Вот эта тема:
поиск минимальной траектории (хотя, возможно, это не совсем твой случай...)
поиск минимальной траектории (хотя, возможно, это не совсем твой случай...)
Цитата
Если это евклидов граф, т.е. вершины являются точками на плоскости, а ребра - отрезками, то это получается алгоритм построения минимальных полигонов.
Примерно так: начинаем с крайне-левой (например) вершины, в каждом узле выбираем ближайшее (по или против часовой стрелки) ребро, пока не замкнем цикл. Переходим к следущей вершине. И т.д. Ребра по дороге помечаем - каждое ребро можно пройти не более чем дважды.
Однако, это для ненаправленного графа. Для направленного тоже, наверно, как то можно приспособить, но не знаю, как получить все полигоны.
Примерно так: начинаем с крайне-левой (например) вершины, в каждом узле выбираем ближайшее (по или против часовой стрелки) ребро, пока не замкнем цикл. Переходим к следущей вершине. И т.д. Ребра по дороге помечаем - каждое ребро можно пройти не более чем дважды.
Однако, это для ненаправленного графа. Для направленного тоже, наверно, как то можно приспособить, но не знаю, как получить все полигоны.
Примерно к такому же алгоритму я и пришёл. Только что-то мне не понавилось в нём.
Ладно с утреца разберусь. Ато щас соображалка туго варит.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.