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

Question

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

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

Я видел несколько способов сделать это в Интернете, но большинство из них связаны с тем, как был получен Delaunay.Я бы с удовольствием нашел что-то, что не нужно интегрировать в 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", если вы присвоите им случайные цвета, то при отображении выходных данных вы увидите знакомый рисунок Вороного.

Answer 3

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

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

Answer 4

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

Answer 5

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

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

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

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