лучшие триангуляционные модели рельефа

[АлексЮстасу]

Проблема во многом описана в http://helponline.dgmn.ru/index.html?18 ... ations.htm.
Там и картинки есть! (Это чтобы не скучно читать было ниже).
И это не реклама - я к этой программе отношения не имею

Триангуляционные модели рельефа TIN, если они создаются классической триангуляцией Делоне, не во всем годятся для рельефа. Даже при использовании подготовленных заранее структурных линий рельефа. Хотя бы потому, что сами структурные линии часто вычерчиваются по TIN (по гипсометрическим или иным моделям рельефа, создаваемым по TIN).
Дело в том, что при отсутствии структурных линий формально правильные треугольники могут строиться поперек бровок-подножий, тальвегов-водоразделов, через береговые линии водоемов и водотоков, "размывая" и часто совсем искажая их.
А также дело в том, что и при наличии структурных линий формально правильные треугольники на резких изгибах структурных линий могут строиться только из точек этих структурных линий. Т.е. на изгибах рек и озер могут образовываться площадки на высоте этих рек и озер. И по такой TIN вода "разольется" вширь даже при структурных линиях. На изгибах бровок-подножий (допустим, в местах промоин) могут образовываться площадки, заполняющие эти промоины, вследствие чего промоины сильно исказятся в TIN или исчезнут вообще. И т.п.

Самое интересное, что я нашелв инете - в приведенной вверху ссылке в разделе "Варианты триангуляции при построении модели поверхности". Разработал это горняк для горняков, для которых правильная оценка и подсчет объемов земли существенны. Но для частного случая - когда исходными данными являются горизонтали и структурные линии.
В общем же случае - когда исходными данными является только множество точек земли или множество точек и структурные линии рельефа - эти подходы не будут полноценно работать.

Огульно я вижу решение проблемы построения правильного рельефа по множеству точек XYZ так:
1. автоматическое или автоматизированное выявление структурных линий рельефа по точкам рельефа.
2. построение моделей (триангуляционных, регулярных, горизонталей-отметок) с учетом структурных линий и специализированных алгоритмов, учитывающих особенности рельефа как объекта.
Т.е. очень интересно, какие есть еще достижения в создании лучшей триангуляции или т.п. для рельефа?

[Александр Мурый]

Тема насколько интересная, настолько же математически сложная
К слову: хорошая книжка для знакомства с триангуляцией Делоне -- А.В. Скворцов. Триангуляция Делоне и её применение.

2. Триангуляция с соединением точек в пределах прямой видимости.
3. Триангуляция с добавлением дополнительных точек (тальвегов/водоразделов, седловин, вершин/впадин).
4. Комбинированная триангуляция, при которой производится и соединение точек в пределах прямой видимости и построение дополнительных точек.

В каких-либо ГИС не встречал указанных вариантов триангуляции. Насчёт описания DIGIMINE:
-- не указан (или я не нашёл?) используемый алгоритм триангуляции Делоне с ограничениями ("разделяй и властвуй", инкрементальный, "Fortune's sweepline" и т.п.);
-- нет генерации качественной полигональной сетки (у которой все углы имеют значения от 20 до 140 градусов);
-- нет ограничения на максимальную площадь треугольника.

[АлексЮстасу]

Насчёт описания DIGIMINE:
-- не указан (или я не нашёл?) используемый алгоритм триангуляции Делоне с ограничениями ("разделяй и властвуй", инкрементальный, "Fortune's sweepline" и т.п.);
-- нет генерации качественной полигональной сетки (у которой все углы имеют значения от 20 до 140 градусов);
-- нет ограничения на максимальную площадь треугольника.

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

[gamm]

По-моему, не стоит углубляться в анализ конкретно этого ПО, хотя, лучше решения я еще не нашел. Хотя бы потому, что решение частное - для исходных данных о рельефе в виде горизонталей.

поищите (на вскидку) triangular mesh generator with constraints и около, таких генераторов много, в том числе и свободно распространяемых. Их делали для численных методов (конечные элементы), там линии, аналогичные структурным элементам, используются для задания различного рода граничных условий, границ изменения свойств, и т.д.

[АлексЮстасу]

По-моему, не стоит углубляться в анализ конкретно этого ПО, хотя, лучше решения я еще не нашел. Хотя бы потому, что решение частное - для исходных данных о рельефе в виде горизонталей.

поищите (на вскидку) triangular mesh generator with constraints и около, таких генераторов много, в том числе и свободно распространяемых. Их делали для численных методов (конечные элементы), там линии, аналогичные структурным элементам, используются для задания различного рода граничных условий, границ изменения свойств, и т.д.

На всякий случай: ключевое слово в этой теме - рельеф. Т.е. интересуют не методы и реализации триангуляции сами по себе и не методы и реализации оптимальной триангуляции вообще, а именно для рельефа. "Чтобы текли куда надо каналы, и в конце куда надо впадали"
Раньше я думал, что для лучшего моделировании рельефа не хватает только структурных линий. Но учет структурных линий не компенсирует недостаточности для рельефа классической триангуляции Делоне - см., ссылку в первом сообщении. Тем более, что сами структурные линии часто производны от триангуляционных моделей рельефа - вычерчиваются по триангуляционным моделям. Которыми бровки-подножия, береговые линии, тальвеги-водоразделы уже искажены. Но даже если структурные линии получены иным образом (вычерчены по ортофотопланам, взяты с карт или т.п.), то и после их учета описанная недостаточность классической триангуляции Делоне для рельефа ведь сохраняется. И рельеф ей искажается.
Можно было бы возразить, что просто нужно больше структурных линий. Но, во-первых, выделение структурных линий - процесс вообще трудоемкий и ответственных, во-вторых, примеры из http://helponline.dgmn.ru/index.html?18 ... ations.htm показывают, что в самих исходных точках и линиях уже содержится достаточно информации для лучшего отображения рельефа. Вычертить дополнительные структурные линии для каждого "опасного" поворота основных структурных линий увеличит трудоемкость в разы. И - опять-таки - не гарантирует полноценного результата.

[gamm]

На всякий случай: ключевое слово в этой теме - рельеф.

тогда не нужно мешать задачу и инструмент. Обычную триангуляцию Делоне для рельефа не используют, в нее структурные элементы не включишь. Зачем ее обсуждать?

[АлексЮстасу]

тогда не нужно мешать задачу и инструмент. Обычную триангуляцию Делоне для рельефа не используют, в нее структурные элементы не включишь. Зачем ее обсуждать?

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

[gamm]

Получается, что для построения треугольников необходимо уже знать об уклонах и условных линиях изменения уклонов.

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

Методов моделирования рельефа много, начиная с работ Хатчинсона (которые прикупила ESRI и вставила в GRID) или реализованных в GRASS сплайнов с натяжением. Можно "натягивать" на триангуляцию сплайн и моделировать кривизну - метод Renke. Есть методы, которые идут от изолиний, их разрабатывали, например, в МГУ, они позволяют строить модели, полностью воспроизводящие карту (включая откосы и овраги). Для изолиний есть методы, которые строят векторное поле по нормалям к изолиниям, и вдоль них интерполируют (некоторая модификация fast marching).

[АлексЮстасу]

Свет клином не сошелся на триангуляции Делоне, даже если программистам ее использовать проще - для моделирования рельефа она не очень годится
Методов моделирования рельефа много, начиная с работ Хатчинсона (которые прикупила ESRI и вставила в GRID) или реализованных в GRASS сплайнов с натяжением. Можно "натягивать" на триангуляцию сплайн и моделировать кривизну - метод Renke. Есть методы, которые идут от изолиний, их разрабатывали, например, в МГУ, они позволяют строить модели, полностью воспроизводящие карту (включая откосы и овраги). Для изолиний есть методы, которые строят векторное поле по нормалям к изолиниям, и вдоль них интерполируют (некоторая модификация fast marching).

Предлагаю в этой теме остановиться пока на триангуляции. В первую очередь потому, что триангуляция - прямой способ представления рельефа непосредственно по исходным точкам. И хотя бы потому, что TIN - один из постоянно востребованных видов продукции.
Дело же не в методах моделирования. Правильно отобразить рельеф можно и "плохой" триангуляцией. И неправильно - самыми изысканными методами.
Пока что у меня получилось, что для правильного моделирования рельефа необходимо знать об уклонах рельефа. Т.е. либо уже его смоделировать в виде полей уклонов, полигонов указанных диапазонов уклонов. Либо определять уклоны "на лету" в небольших окрестностях непосредственно анализируемых точек.

[АлексЮстасу]

поищите (на вскидку) triangular mesh generator with constraints и около, таких генераторов много, в том числе и свободно распространяемых. Их делали для численных методов (конечные элементы), там линии, аналогичные структурным элементам, используются для задания различного рода граничных условий, границ изменения свойств, и т.д.

Все не мог вклинить свое "спасибо" за этот совет. Наверняка (судя по картинкам), можно найти подходящее.
Только я по-вражески не понимаю (