Представитель Шуры Люберецкого в ЖЖ (brat_luber) wrote,
Представитель Шуры Люберецкого в ЖЖ
brat_luber

Про рельеф

В продолжение вот этой задачки:

http://shura.luberetsky.ru/2011/07/19/algoritmicheskaya-zadacha/

Я реализовал алгоритм выбора точек, описанный в статье Systematic selection of Very Important Points from Digital Terrain Model for constructing Triangular Irregular Network без каких-либо изменений. Особо не заморачиваясь с производительностью, я добился того, что из миллиарда точек выбиралось порядка миллиона “очень важных” где-то минут за 40. Такое время меня вполне устраивало. Думаю, при желании можно сократить его в два-три раза, но делать этого я не буду, и вот почему.

Во-первых, модель с миллиардом точек оказалась бесполезной. Выяснилось (после выбора “очень важных точек”), что расположены они как-то странно – вдоль сторон и диагоналей квадратиков регулярной сетки. Оказывается, что кто-то взял за основу матрицу высот с большим шагом, преобразовал в триангуляционную модель (тривиальным образом, без выбора “важных точек”), а затем снова преобразовал в растр с меньшим в 10 раз шагом.

Во-вторых, чудес не бывает. Более-менее адекватное количество “важных точек” можно выбрать тогда, когда их количество меньше общего количества точек где-то на два порядка. Итого миллиард точек исходника даст 10 миллионов точек TIN, или около 20 миллионов треугольников. Это много.

Если “сложить” эти пункты, то можно преобразовать исходный миллиард точек в 10 миллионов (с которых все и началось), а затем сделать из них 100 000 “важных точек” – около 200 тысяч треугольников, сущая ерунда по нынешним временам.

Кстати, хочу поплакаться на жизнь. Пол-пятницы искал нормальное описание того, как алгоритмически сделать триангуляцию Делоне. В интернетах встречается описание алгоритма со сложностью O(N2) – последовательно добавляем точки к существующей триангуляции, при необходимости перестраивая ее. Каждый шаг в худшем случае требует перестроения всех треугольников, и это мне не нравится. Иногда в довольно общих чертах описывают алгоритм типа “divide and conquer” – разбиваем множество точек надвое, строим для подмножеств триангуляции, а затем объединяем их. Сложность, как можно показать, асимптотически оптимальная, O(N ln N). Описание того, как именно надо объединять, обычно отсутствует. В книге Препараты и Шеймоса подробно разбирается задача построения диаграммы Вороного – графа, двойственного триангуляции Делоне, и вскользь делается упоминание о том, что построив диаграмму Вороного за асимптотически оптимальное время O(N ln N), можно преобразовать ее в триангуляцию. Этот подход тоже мне не нравится, так как для построения диаграммы Вороного требуется выполнять несколько более сложные операции.

Конечно, я нашел относительно адекватное описание всего этого безобразия, но как-то странно – вроде задача довольно классическая, а описаний решения “для тупых” нет.

Запись опубликована в блоге Шуры Люберецкого. Вы можете оставлять свои комментарии там, используя свое имя пользователя из ЖЖ (вход по OpenID).

Tags: программирование
Subscribe

Comments for this post were disabled by the author