Как получить диаграмму Вороного с учетом ее набора точек и триангуляции Delaunay?

Я работаю над игрой, где создаю случайную карту провинций (a la Risk или Diplomacy). Чтобы создать эту карту, я сначала создаю серию полуслучайных точек, а затем вычисляю триангуляции Деланея этих точек.

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

Я видел несколько способов сделать это в Интернете, но большинство из них связано с тем, как был получен Delaunay. Мне бы хотелось найти что-то, что не нужно интегрировать в Delaunay, но может работать только на основе данных. В противном случае я ищу что-то приемлемое для новичков с относительной геометрией, а не для оптимальной скорости. Спасибо!

Ответ 1

Диаграмма Вороного - это просто двойной граф триангуляции Делоне.

Итак, ребра диаграммы Вороного расположены вдоль перпендикулярных биссектрис краев триангуляции Делоне, поэтому вычислите эти линии.
Затем вычислим вершины диаграммы Вороного, найдя пересечения соседних ребер.
Наконец, ребра - это подмножества вычисленных строк, которые лежат между соответствующими вершинами.

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

Ответ 2

Если оптимальная скорость не учитывается, следующий код psuedo будет генерировать диаграмму Вороного трудным образом:

for yloop = 0 to height-1
  for xloop = 0 to width-1

    // Generate maximal value
    closest_distance = width * height

    for point = 0 to number_of_points-1
      // calls function to calc distance
      point_distance = distance(point, xloop, yloop)

      if point_distance < closest_distance
        closest_point = point
      end if
    next

  // place result in array of point types
  points[xloop, yloop] = point

  next
next

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

Ответ 3

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

Статья в Википедии о алгоритме Fortune содержит свежие ссылки на исходный код на C, С# и Javascript. Все они были первоклассными и сопровождались прекрасными примерами.

Ответ 4

Я уверен, что "треугольник" http://www.cs.cmu.edu/~quake/triangle.html может генерировать voronoi

Ответ 5

Ну, причина, по которой вещи связаны друг с другом, состоит в том, что триангуляция Делоне и диаграмма Вороного являются двойственными структурами. Это означает, что это не разумно переходить от ворона к delaunay и наоборот.

Это означает, что если у вас есть диаграмма voronoi, все, что вам нужно сделать, это подключить точки, которые разделяют край, и у вас будет триангуляция delaunay (и наоборот).

Ответ 6

Каждый из треугольников Delaunay содержит одну точку диаграммы Вороного.

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

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

Как вы планируете приближаться к краям?