Как получить диаграмму Вороного, учитывая ее набор точек и триангуляцию Делоне?

Question

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

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

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

Answer 1

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

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

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

Answer 2

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

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 при отображении вывода.

Answer 3

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

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

Answer 4

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

Answer 5

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

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

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

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