Преобразование областей с векторными контурами (границ) в растровую карту (пиксельную сетку)

Question

У меня есть карта, которая разделена на несколько регионов границами (контурами), как страны на карте мира.Каждый регион имеет определенный класс поверхностного покрытия S (например,0 для воды, 0,03 для травы ...).Границы определяются:

• какая ценность S находится по обе стороны от него (0,03 с одной стороны, 0,0 с другой, в примере ниже)
• из скольких точек состоит граница (n=7 в примере ниже), и
• n пары координат (x, y).

Это один из примеров.

0.0300      0.0000           7
2660607.5   6332685.5   2660565.0   6332690.5   2660541.5   6332794.5 
2660621.7   6332860.5   2660673.8   6332770.5   2660669.0   6332709.5 
2660607.5   6332685.5

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

Обратите внимание, что границы представляют шаг изменения в S.Различные значения S представляют собой дискретные классы (например,трава или вода), и не являются значениями, которые могут быть усреднены (т.е.никакой мокрой травы!).

Также обратите внимание, что не все границы являются замкнутыми циклами, как в примере выше.Это немного похоже на границы стран:например ,граница между США и Канадой - это не замкнутый контур, а скорее линия, соединяющаяся на каждом конце с двумя другими границами:"границы" Канада-океан и США-океан.(Границы замкнутого цикла действительно существуют тем не менее!)

Кто-нибудь может указать мне на алгоритм, который может это сделать?Я не хочу изобретать велосипед!

Answer 1

Способ, которым я решил эту проблему, заключается в следующем:

1. Маршируйте вдоль каждого сегмента;останавливайтесь через регулярные промежутки времени L.
2. При каждой остановке размещайте точку трассировки непосредственно слева и справа от сегмента (на определенном небольшом расстоянии d из сегмента).Точкам трассировки присваиваются левое и правое S-значения соответственно.
3. Выполните интерполяцию ближайшего соседа.Каждой точке на растровой сетке присваивается S ближайшей точки трассировки.

Это работает даже при наличии незамкнутых линий, напримерна краю карты.

Это не "идеальный" аналитический алгоритм.Есть два параметра: L и d.Алгоритм работает прекрасно до тех пор, пока d << L.В противном случае вы можете получить неточности (обычно однопиксельные) вблизи соединений сегментов, особенно с острыми углами.

Answer 2

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

Аппроксимацию диаграммы Вороного можно выполнить графически в OpenGL, нарисовав каждый отрезок линии в виде пары квадратов, образующих форму шатра.Z-буфер используется для того, чтобы ближайший квадратик имел приоритет и, таким образом, окрашивал пиксель в зависимости от того, какая строка находится ближе всего.Разница здесь в том, что вы захотите раскрасить полигоны в зависимости от того, на какой стороне линии они находятся, а не от того, какую линию они представляют.Хорошей статьей, в которой обсуждается подобный алгоритм, является работа Хоффа и др. Быстрое вычисление обобщенных диаграмм Вороного с использованием графического оборудования

3d геометрия будет выглядеть примерно как этот эскиз с 3 красно-желтыми сегментами и 1 сине-зеленым сегментом:

Эта процедура не требует от вас ничего преобразовывать в замкнутый цикл и не требует каких-либо причудливых библиотек геометрии.Все обрабатывается z-буфером и должно быть достаточно быстрым, чтобы работать в режиме реального времени на любой современной видеокарте.Уточнением было бы использовать однородные координаты, чтобы базы проецировались на бесконечность.

Я реализовал этот алгоритм в скрипте Python по адресу http://www.pasteall.org/9062/python.Одно интересное предостережение заключается в том, что использование конусов для перекрытия концов линий не работало без искажения формы конуса, потому что конусы, представляющие конечные точки сегментов, были z-образными.Для предоставленного вами примера геометрии выходные данные выглядят следующим образом:

Answer 3

Я бы порекомендовал вам использовать библиотеку геометрических алгоритмов, такую как CGAL.Особенно второй пример на странице "2D полигоны" справочного руководства должно быть предоставлено то, что вам нужно.Вы можете определить каждую "границу" как многоугольник и проверить, находятся ли определенные точки внутри полигонов.Так что в принципе это было бы что-то вроде

for every y in raster grid
  for every x in raster grid
    for each defined polygon p
      if point(x,y) is inside polygon p
        pixel[X][Y] = inside_color[p]

Я не совсем уверен в том, что делать с outside_color, потому что внешние области будут перекрываться, не так ли?В любом случае, глядя на ваш пример, каждая внешняя область может быть водой, так что вы просто могли бы сделать окончательный

    if pixel[X][Y] still undefined then pixel[X][Y] = water_value

(или, в качестве альтернативы, установите pixel[X][Y] в значение water_value перед повторением списка полигонов)

Answer 4

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

Answer 5

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