У меня есть набор двумерных точек, и, учитывая каждую точку, соединенную с другой точкой с «ребром» с весом, равным расстоянию между ними, мне нужно найти MST полученного графа.
Я использую тот факт, что EMST всегда является подграфом триангуляции Делоне в этой области. Мне нужны треугольники в виде списка ребер, чтобы сделать из него график, а затем запустить над ним Крускал.
Кроме того, должен ли я идти по пути триангуляции Делоне, или есть прямая функция для этого?
Пожалуйста, дайте пример кода для определения того, какие заголовки включить, какое пространство имен использовать и т. Д. С вашим ответом на любой вопрос, если это возможно.
В 2D число ребер триангуляции является линейным. Как только триангуляция Делоне рассчитывается с использованием CGAL, Вы можете использовать реализацию минимального связующего дерева на графе. Смотрите страницу википедии Евклидово минимальное остовное дерево.
Других решений пока нет …