Быстро найти и визуализировать местность выше заданной высоты

Question

Учитывая карту высот, состоящую из пар широта / долгота / высот, какой самый быстрый способ найти все точки выше заданного уровня высот (или, что еще лучше, только 2D вогнутый корпус)?я работаю над приложением ГИС, где мне нужно визуализировать наложение поверх карты, чтобы визуально указать области, которые имеют более высокую высоту;это определяет этот многоугольник / область, которая поставила меня в тупик (на данный момент).У меня есть простой массив пар широта / долгота / высота (точнее, файлы GTOPO30 DEM), но я могу преобразовать это в любую структуру данных, которую вы предложите.

Мы были направлены на триангулированные нерегулярные сети (TIN), но я не уверен, как эффективно запрашивать эти данные после того, как мы сгенерировали TIN.Я не удивлюсь, если бы наша проблема могла быть решена аналогично тому, как можно было бы создать контурную карту, но у меня нет никакого опыта с этим.Любые предложения будут потрясающими.

Answer 1

Похоже, вы пытаетесь создать полигональное представление границы возвышенности.

Если вы работаете с растровыми данными (сэмплированными по прямоугольной сетке), попробуйте это.

Думайте о вашей сетке как о совокупности прямоугольных треугольников.

Скажему вас есть сетка очков 3x3

• abc
• def
• ghk

Ваши треугольники:

• abd часть прямоугольника abed
• bde другая часть прямоугольника abed
• bef часть прямоугольника bcfe
• cef другая часть прямоугольника bcfe
• dge ... и т. Д.

Ваш алгоритм имеет следующие шаги.

1. Создайте список треугольников, которые находятся выше порога высот.

2. Возьмите объединение этих треугольников, чтобы сделать многоугольную область.

3. Определите границу многоугольника.

4. Если необходимо, сгладьте границу многоугольника, чтобы ваш слой выглядел нормально при отображении.

Если вы пытаетесь создать красивый конлинии обхода, шаг 4 очень трудно направо.

Шаг 1 является ключом к этой проблеме.

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

Для остальных этапов вам понадобится приличная библиотека 2d обработки геометрии.

Если ваши точки не находятся на регулярной сетке, начните с использования алгоритма Делоне (который вы можете посмотреть), чтобы организовать ваши точки в треугольники.Затем следуйте тому же алгоритму, который я упоминал выше.Предупреждение.Это будет выглядеть отрывочно, если у вас мало очков.

Answer 2

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

Самое простое решение - просто сохранить точки в массиве, отсортированные по высоте. Поиск всех точек в определенном диапазоне высот - это просто двоичный поиск, и вам нужно выполнить сортировку только один раз.

Если вам нужно выполнить запрос только один раз, просто выполните линейный поиск в массиве в том порядке, в котором вы его получили. В любом случае создание более сложной структуры данных из массива будет O (n), так что вы не получите лучших результатов, усложнив вещи.

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

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

Answer 3

Я бы использовал вложенные C-квадраты , где каждый квадрат имел заранее рассчитанную максимальную высоту земли. Это позволило бы мне сканировать на высоком уровне, отбрасывая любые квадраты, где максимальная высота не выше высоты поиска, и углубляясь в те квадраты, где части земли были выше высоты поиска.

Если вы работаете с различными заданными уровнями высоты поиска, вы можете предварительно рассчитать выпуклый корпус для различных предопределенных уровней для наименьших квадратов, которые вы решили использовать (или все квадраты, если на то пошло.)

Answer 4

Я не уверен, находятся ли ваши точки широты / долготы / высоты на обычной сетке или нет, но если нет, возможно, их можно было бы интерполировать для представления даже приращений высоты 100 футов и равномерного деления широты / долготы (азимутИмейте в виду, что это не дает равномерного разделения расстояния).Но если это сработает, почему бы не рассчитать трехмерный массив, где индексы представляют собой высоту, широту и долготу соответственно.Затем, когда летательному аппарату требуются данные о точках на высоте или выше, для конкретного участка местности, код должен считывать только небольшую часть данных в этом массиве, которая индексируется, чтобы сделать смежные «воксели» смежными всхема индексации.

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

Не думаю, что будет более быстрый способ поиска этих данных.

Answer 5

Предполагая, что у вас есть данные широты / долготы / высоты, которые хранятся в массиве (или трех отдельных массивах), вы сможете использовать методы запросов к массиву, чтобы выбрать все точки, где высота превышает определенный порог. Например, в python с numpy вы можете сделать:

indices = where(array > value)

И переменная indices будет содержать индексы всех элементов на array больше порога value. Подобные команды доступны на различных других языках (например, в IDL есть команда WHERE(), и аналогичные вещи можно выполнять в Matlab).

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

binary_array[indices] = 1

(Предполагается, что вы создали пустой массив того же размера, что и исходный широта / долгота / высота и назвали его binary_array.

Если вы работаете с растровыми данными (которые я бы порекомендовал для этого типа работы), вы можете обнаружить, что вы можете просто наложить этот массив на карту и получить хороший набор областей. Однако, если вам нужно преобразовать области выше порога высот в векторные полигоны, вы можете использовать один из многих встроенных методов ГИС для преобразования растра-> вектора.