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

Question

Учитывая карту высот, состоящую из пар лат/lon/elevation, что является самым быстрым способом найти все точки выше заданного уровня высоты (или, еще лучше, только 2D вогнутый корпус)?

Я работаю над приложением GIS, где мне нужно сделать надпись поверх карты, чтобы визуально указать области с более высокой высотой; он определяет этот полигон/регион, который меня озадачил (пока). У меня есть простой массив пар lat/lon/elevation (точнее, файлы DEM GTOPO30), но я могу свободно преобразовать их в любую структуру данных, которую вы бы предложили.

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

Answer 1

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

indices = where(array > value) 

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

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

binary_array[indices] = 1 

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

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

Answer 2

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

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

Answer 3

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

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

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

Answer 4

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

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

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

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

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

Answer 5

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

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

Подумайте о своей сетке как о сборке правильных треугольников.

Допустим, у вас есть 3х3 точек

• AbC
• Защиту
• ГХК

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

• абд часть прямоугольника аЬсй
• BDE другая часть прямоугольника аЬсй
• BEF часть прямоугольника BCFE
• CEF другой части прямоугольника BCFE
• DGe ... и так далее

Ваш алгоритм имеет эти шаги.

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

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

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

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

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

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

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

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

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