В продолжение вот этой задачки:
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), можно преобразовать ее в триангуляцию. Этот подход тоже мне не нравится, так как для построения диаграммы Вороного требуется выполнять несколько более сложные операции.
Конечно, я нашел относительно адекватное описание всего этого безобразия, но как-то странно — вроде задача довольно классическая, а описаний решения «для тупых» нет.