Как построить полную сетку из не полной?

Question

[vitvov]

Здравствуйте.
Стоит задача нарисовать изолинии на карте, по известным точкам. Одна точка хранит в себе данные долготы, широты и число.
Найденные мною алгоритмы для C# conrec и contours работают хорошо, но, для их использования нужна полностью заполненная равномерная сетка (двумерный массив значений, где индексы массива считаются его координатами).
Проблема заключается в том, что мои данные располагаются не равномерно, и нужно построить по ним равномерную сетку. Уже неделю борюсь с этим и не могу побороть (знания в математике подводят).
Так же смотрел в сторону триангуляции, но все четно.
Подскажите, как я могу нарисовать изолинии по неравномерной сетке, или как перейти от неравномерной сетке в равномерную?

Comments

[xmoonlight]

Я не могу понять, что вы именно хотите (хотя работал с ГЕО).
Что значит "данные располагаются не равномерно"?
Можете изображения привести: как есть и как нужно, чтобы было?

[vitvov]

xmoonlight: Есть просто точки на карте. Они расположены хаотично, на разном расстоянии друг от друга (это gps координаты полета вертолета). По этим точкам нужно нарисовать изолинии (высотная карта). Алгоритмы которые я привел работают только с равномерной сеткой, то есть, если точки располагаются на пересечении прямоугольников на равных расстояниях друг от друга (как листок в клеточку), соответственно нужно по имеющимся точкам найти все неизвестные точки.

[xmoonlight]

vitvov: Вам нужно построить кривую Бизье в трёхмерном пространстве на основе каждых 3-х промежуточных точках.

[xmoonlight]

vitvov: потом сделать проекцию на сферу на основе заданного шага сетки и получите все высоты на пересечении клеток.

Answer 1

[Mrrl]

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

Comments

[vitvov]

В общем удалось найти алгоритм триангуляции. Получил набор триугольников. Не совсем понятно как по вот этому method.meteorf.ru/publ/tr/tr346/k_alf.pdf методу обходить эти триугольники и рисовать.

[Mrrl]

vitvov: На страницах 71-72 приведён полный алгоритм построения изолиний.

[vitvov]

Там ошибка была во втором пункте. Искать нужно не по вершинам а по ребрам треугольника. В общем все получилось. Осталось оптимизировать все это дело, так, как данных очень много и изолиний так же много.

[Mrrl]

vitvov: Пункт 2 нужен, чтобы изолиния не уткнулась в вершину. Там удачный результат поиска - плохая ситуация, которую приходится специально обходить. Так что ошибки нет.
А насчёт "оптимизировать" - то если нужно только рисовать, и при этом устроят изолинии в виде ломаной, то всё просто: перебираете треугольники, для каждого смотрите максимальное и минимальное значение в вершинах и рисуете все изолинии, попавшие между ними (на каждую - один отрезок).
Если надо сглаживать или уметь проходить по изолиниям, то, конечно, сложнее - нужен быстрый поиск соседнего треугольника.

[vitvov]

Под оптимизацией имеется в виду именно рисование этих линий на элементе управления (Bing Map Control for WPF), так как линий очень много, плюс, по ТЗ должно быть 16 изолиний от минимального до максимального значения, а это жрет много ресурсов.

Answer 2

[Станислав Макаров]

Тоже не совсем поменял что такое неравномерная сетка, может вам просто брать среднее из ближайших значений в той точке, где значения нет? Ну или как-то иначе интерполировать..