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

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

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

Answer 3

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

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

Answer 4

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

Answer 5

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

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

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

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

Answer 6

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

Сначала найдите все центры описанных окружностей (из всех треугольников), то есть красные точки:

Затем соедините центры описанных окружностей каждого соседнего треугольника линиями, чтобы получить мозаику: