Re: Не могу придумать алгоритм такой сортировки
Добавлено: 23.05.2009 (Сб) 20:43
Хакер писал(а):Да, кстати, при коллапсировании нельзя допускать изменения топологии, т.е. коллапсировать нужно в определённом порядке. На вскидку: составить список вершин и углов, отсоритировать по углу в порядке убывания, убрать последние три пункта из списка, и в путь. После каждого коллапсе одну (устранённую) вершину надо из списка удалять, а для двух других (которые соединили ребром) обновлять угол. При этом, вероятно, придётся изменять их положение в списке.
ADDED: нет, при сортировке по углу тоже возможно нарушение топологии.
Придумал:
Нужно провести триангуляцию фигуры. Коллапсировать можно только те рёбра, которые принадлежат одному триангуляционному треугольнику (тафтология, но всё же). После коллапса полученная новая грань становится частью какого-то другого треугольника. И так до тех пор, пока не останется единственный треугольник.
И ещё один вариант придумал, двух проходный, но пусть автор пока попробует найти контрпример (если такой существует) к вышеописанному способу с триангуляцией.
Сейчас придумал крайне простой по сравнению с оцтитированным способ. Проверю.