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

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

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

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

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

• a b c
• d e f
• g h k

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

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

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

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

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

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

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

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

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

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

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

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

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

indices = where(array > value)

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

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

binary_array[indices] = 1

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

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

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

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

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

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

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

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

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

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

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

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