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

Я бы порекомендовал вам использовать библиотеку геометрических алгоритмов, например 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]

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

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

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

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

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

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

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

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

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

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