Как узнать евклидово минимальное остовное дерево с помощью библиотеки CGAL?

У меня есть набор двумерных точек, и, учитывая каждую точку, соединенную с другой точкой с «ребром» с весом, равным расстоянию между ними, мне нужно найти MST полученного графа.
Я использую тот факт, что EMST всегда является подграфом триангуляции Делоне в этой области. Мне нужны треугольники в виде списка ребер, чтобы сделать из него график, а затем запустить над ним Крускал.

Кроме того, должен ли я идти по пути триангуляции Делоне, или есть прямая функция для этого?

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

1

Решение

В 2D число ребер триангуляции является линейным. Как только триангуляция Делоне рассчитывается с использованием , Вы можете использовать реализацию минимального связующего дерева на графе. Смотрите страницу википедии Евклидово минимальное остовное дерево.

2

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector