[andrik75]

Доброго времени суток всем!
Есть у меня задача над решением которой я бьюсь уже год с лишним и все никак.
Выходные данные: растровая карта месности или же выкопировка с горизонталями.
Задача: По этой карте построить цифровую модель рельефа. "Оцифровать" можно и вручную, тоесть ввести в программу нужные горизонтали и отметки высот. В результате программа на области карты должна построить некую гладкую функцию вида z=f(x,y), имея которую я бы мог уже анализировать рельеф местности. Визуализация не нужна. Нужна идея и алгоритм самой реализации на любом языке программирования, так как я сам програмер и разобраться в этом смогу.
Интересует: алгоритм триангуляции, применимый для геодезии, или модернизированная триангуляция Делонэ, а также алгоритм быстрого поиска попадания точки P(x,y) в ккакой то из треугольников триангуляции.
А вопщем интересует все, что с этим связано!

[hwd]

Триангуляция.

[andrik75]

hwd
Спасибо! С лиспом я разберусь как то, перепишу на С++ или Делфи.
Но всеже! Ткнуть в любую точку на листе и узнать к какому треугольнику триангуляции она принадлежит как? Простой перебор не подходит! Нужно что то поизящнее. А как?

[ShaggyDoc]

Если "на любом языке программирования", то программисту надо знать про существование

http://algolist.manual.ru/
http://alglib.sources.ru/

Для Delphi - на torry есть библиотечные реализации.
На LISP - лучше всего у Евгения, ссылка в #2

[andrik75]

то программисту надо знать про существование

А кто сказал, что программист про эти ресерсы не знает!? Знает! Но именно того, что мне нужно там нету. www.torry.net "заточена" в основном под визуальность, а мне нужна практически чистая математика.
Ну есть одна идея: разбить область на равномерную прямоугольную сетку, посчитать какие треугольники попадают в каждую ячейку сетки, а потом при работе попадание точки в ячейку прямоугольной сетки вычисляется элементарно и найти найти нужный треуголик не составит труда.
Еще варианты в студию!

[Supermax]

Можно и мне свои пять копеек вставить?
Начну с постановки задачи

...растровая карта месности или же выкопировка с горизонталями...

кусок бумаги или скан с нее, что еще хуже в котором единственное полезное, что можно оставить, это горизонтали и отметки их высот. Точность - мягко говоря, плюс минус два ведра.
Либо просто точки с отметками высот, как на всех геоподосновах, что в рельеф перевести вообще получается черте что.
Предполагается эту лабуду держать в виде математической модели. Ладно. Триангуляция говорите? - А зачем? Для компактности? или для облегчения математических вычислений высоты и координат точки, на которую вы ткнули?
Если взять и все горизонтали сделать сплайнами, а сплайн самая компактная форма матиматического описания кривой, да еще и расбросать эти сплайны по вертикали, то какая триангуляция вам еще нужна?
А между прочим, 3D солид самая компактная математическая модель описания объема и именно по этому математическому описанию строится визуализация. 3D солид не только компактно упакованная математическая модель, но и шикарный инструмент определения точек пересечения с другими математическими объектами.
Дело не в визуализации, как цели построения пространственной фигуры, а как инструмента решения конкретных задач.
Берем горизонтали, переводим их в сплайны, разносим по вертикали и командой _loft (2010 кад) строим математическую модель рельефа.

[andrik75]

Supermax
Очень хорошо! Про сплайны, горизонтали и разнос по вертикали понял, да и сам в курсе. Но только как найти высоту точки между сплайнами (горизонталями)? Математику в студию, плиз. А так идея конечно супер.
Мне бы желательно смастерить что то такое свое чтоб не использовало сторонние програмные продукты. И главное: на выходе должно всегда быти что то типа z=f(x,y)!!! По другому не подходит.

[Supermax]

Если смотреть на хранение данных о рельефе без привязки к программам, то это хранение может быть интересно только историкам, а в реальном строительстве геоподоснова теряет свою реальность еще на стадии создания. Архивные данные почти всегда не соответствуют натуре. Геодезисты порой просто халтурят и упрощают себе работу надписями типа "изрыто". Вот как такую надпись перевести в математическую модель?
Не привязываться к программам имеет смысл только изходя из того, что они устаревают и заменяются другими, которые старые форматы файлов и макросы не переваривают. Но всегда, я подчеркиваю, всегда математика находит себе выход в программу. Ее только в программе можно хоть как-то использовать. Создав объемную модель рельефа в любом формате файла вы всегда прочтете этот файл, даже если умрут фирмы, которые писали ПО для вас. Это ПО у вас на компе никто не сотрет, руки коротки. И компьютер вы выбросите только тогда, кода купите другой, который может все ваши файлы читать.
3D солиды придумали не в AutoDesk. Есть описание их структуры и рельеф там можно делать как сеть сплайнов, причем в трех плоскостях.
все разбито не на треугольники, а на квадратики (хотя можно и треугольниками, больше сплайнов потребуется), где каждая грань - участок сплайна.
Но эти все сложности не нужны. Надо упрощать, а не усложнять, тем более, что исходный материал -
Если вы понимаете, что математику тоже прийдется хранить в файле, и что DWG или DXF ничем не хуже, то как найти точку на сплайне ближайшую к вектору Z с координатами такими-то, затем к другому сплайну и затем нахождение искомой точки, родим с божей помощью.

Есть два сплайна. Задаем точность и переводим описание сплайна в 3D полилинию или кучу отдельных линий. Находим ближайшую по XY к XY вектора Z и вычисляем на этой линии XYZ точку кратчайшего расстояния.
Проделываем то же самое с другим сплайном.
Имеем две точки и координаты нашего вектора Z. Находим точку на отрезке между двумя точками на сплайнах ближайшую к вектору Z. Z этой точки и есть искомый Z на нашем векторе.
Надеюсь понятно?

[Valery Brelovsky]

Всякая идея должна кудато вести. Для обработки растров есть к примеру
AUTODESK.AUTOCAD.RASTER.DESIGN.V2011. Но вёравно он не строит модель местности. Нужно полученные линии тобишь горизонтали разнести по высотам в ручную. Есть программы которые по эти горизонталям построят рельеф местности и дадут возможность ткнув в любую точку получить x,y,z к примеру autocad_civil_3d_2011.
И уже на самое последнее в autocad_civil_3d_2011 и 2010 имеется функция Import Google Earth &Surface...

[Supermax]

Во! И я о том же. Использовать чей-то продукт и затачивать под него архив не значит ангажировать конкретного производителя ПО. На 14 каде до сих пор многие работают (так архивы сделаны) Хотя в этот формат можно и на более продвинутых кадах все записывать (денег на ПО жалко).
Когда архив разросся, его влом на другой формат переделывать, но если перевести описание чего-то в математическую модель и хранить в текстовом формате (он кажется вечным), то все равно надо писать прогу перегоняющую текст в формат современных ПО. Если все хранится не в тексте, то все равно писать конвертер придется. Так какая разница в чем хранить? Все одно, что понос, что золотуха.

[Disney]

Сообщение от Supermax Геодезисты порой просто халтурят и упрощают себе работу надписями типа "изрыто"

А Руками разводители ни когда не халтурят?
Надпись изрыто, лишь говорит о том, что горизонтали там проводить не стоит, а отметка дона для общего понимания, т.к. на 2 метра вправо она (отметка) может быть уже на 0.5 метра выше, а на 2 метра влево на 0.5 метра ниже, потому, что там "изрыто". Кстати, ещё бывают "Навалы грунта" они вам тоже не понравятся

[Supermax]

Я не говорю о тех ситуациях, когда в самом деле нет смысла описывать данный участок, но когда геодезисту просто было влом попасть на охраняемую территорию и он на ровном месте, без ям и куч написал "изрыто", чему я много раз сам был свидетелем, поскольку теплотрассами часто озабочен, то уж сами понимаете.
Один раз было в Москве, почти в центре. Строение задом примыкает к крутому склону и участок за строением порос колючими кустами, так на геоподоснове там написано "изрыто" пришлось самим отметки снимать.

[andrik75]

)) ой люди добрые, да чтоб ж вы все такие прикладники, Поймите же, мне нужно "сделать рельеф" в моей собственной программе, дя того чтоб она проводила расчеты так как нужно, а вы мне про автокады, цивилы и прочее. Да, они умеют, но математика там есть, и я хочу знать какая. Мне не нужен рельеф с точностью до кинутой горстьи песка, мне нужно описать примерно на участке метров максимум 300х300, взял карту 1:2000, перерисовал ручками с нее изолинии и отметки высот, программа пощаманила-пошаманила и смогла выдавать z=f(x,y). И всего то! Можна чтоб не очень точно но зато универсально.

[Valery Brelovsky]

Тогда есть программа MathCAD, которая обрабатывает функции и строит поверхность и графики.

[zamtmn]

В результате программа на области карты должна построить некую гладкую функцию вида z=f(x,y)

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

а также алгоритм быстрого поиска попадания точки P(x,y) в ккакой то из треугольников триангуляции.

Сколько у вас планируется треугольников? погуглите "разбиение пространства" например octree, b-tree.

[ShaggyDoc]

ой люди добрые, да чтоб ж вы все такие прикладники

А здесь все такие. Здесь все понимают то, что является "военной тайной" для программистов - самое сложное это получить по растровой "карте" правильные горизонтали и отметки точек. Вот эта часть задачи практически, в подавляющем большинстве случаев, нерешаема.

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

Карта я пишу в кавычках, потому что это понятие для "бабушек на скамейке". Если работаете действительно с картой, т.е. отображением поверхности планеты с учетом её формы, задача и теоретически нерешаема. Надо говорить про план, т.е. представление местности из предположения, что земля плоская и покоится на спинах слонов.

А когда есть идеализированная модель местности, где можно горизонтали представить в виде "некую гладкую функцию вида z=f(x,y)", остальное - дело техники программирования.

Геодезические алгоритмы триангуляции изложены в учебниках по геодезии. Без привязки вообще к программирования. Есть и старая книжка "Решение массовых геодезических задач на микроЭВМ" (еще 1991 год). Там достаточно подробно. В доступной плоской форме.

И не стоит игнорировать ссылку в #2 на сайт Евгения Елпанова. Там и реализации. Весьма квалифицированнные.

Свои функции не прилагаю. "Из прынцыпа" (С). У Евгения лучше.

[bernata]

http://dwg.ru/dnl/8629

[andrik75]

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

[Li6-D]

Если требование гладкости (это очень нужно?) заменить непрерывностью рельефа, самое простое решение с моей точки зрения такое:
На план накладываем прямоугольную сетку, каждая клетка которой имеет постоянную высоту, ширину и разделена диагональю
на два прямоугольных треугольника, допустим из левого верхнего угла в правый нижний. Внутри каждого треугольника (ячейки) считаем рельеф плоским. Для любой указанной пользователем точки плана P по координатам Xp,Yp можно легко найти адрес ячейки, которой эта точка принадлежит. И если известны координаты Zv вершин ячейки можно найти требуюмую Zp. Математика действительно здесь очень проста. В принципе об этом говорит автор темы (пост #5).
Сложнее подготовить план, т.е. решить апроксимационную задачу и найти Zлополучные координаты Zv для вершин сетки по имеющимся данным: по изолиниям ли, просто по списку известных точек рельефа, нерегулярным образом расположенных на карте.

[zamtmn]

Далее просто: тыкаем в любом месте карты, по бинарному дереву определяем..... даааа... пишу пишу ..... ниче не определяем, всплывают загвоздки которые сводят на нет весь труд ((

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

разбить на бинарное дерево, в конце каждой ветки будет только одна точка (ну или сделать ограничение на максимальное количество подветок).

оставлять в ноде только одну точку смысла никакого нет, только вред. обычно ограничивают глубину дерева и минимальное количество примитивов в ноде. Вообще хранить в дереве точки неправильно ИМХО, нужно хотябы треугольники.