Построение минимального дерева Штейнера в евклидовой плоскости

Условие:

Даны три точки в евклидовой плоскости с координатами A(x1,y1), B(x2,y2) и C(x3​,y3​). Необходимо построить минимальное дерево, соединяющее эти точки с минимальной общей длиной рёбер.

Разрешается добавление одной дополнительной точки S(xs,ys)(точки Штейнера), которая может уменьшить суммарную длину соединяющих отрезков.

Требования:

1. Найти координаты точки S, которая минимизирует сумму расстояний от неё до заданных точек.
2. Визуализировать полученное дерево с помощью библиотеки SFML.
3. Вывести терминальные точки (красным), точку Штейнера (синим) и соединяющие рёбра (жёлтым).

Формат входных данных:

На вход подаются три пары вещественных чисел (x1,y1), (x2,y2), (x3,y3) — координаты заданных точек.

Формат выходных данных:

Программа должна:

• Вычислить координаты точки Штейнера S(xs,ys).
• Вывести общую длину построенного дерева.
• Открыть графическое окно с визуализацией результата.

Пример работы программы:

Входные данные:

Выходные данные:

Порядок решения задачи о минимальном дереве Штейнера

Шаг 1: Определение входных данных

Заданы три точки A(x1,y1), B(x2,y2) и C(x3,y3) в евклидовой плоскости. Нужно найти минимальное дерево, соединяющее их, с возможностью добавления одной точки Штейнера S(xs,ys), которая минимизирует сумму расстояний.

Шаг 2: Поиск точки Штейнера

Метод градиентного спуска применяется для нахождения оптимальной точки S.

1. Начальная точка
• Используем центр масс терминальных точек в качестве начальной точки

2. Минимизация суммы расстояний

• Вычисляем сумму расстояний от текущего положения S до всех терминалов:

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

Шаг 3: Визуализация графа (SFML)

После нахождения S(xs,ys), строим дерево:

1. Рисуем точки:
• Красные круги для терминальных точек A,B,C.
• Синяя точка для найденной точки Штейнера.
2. Рисуем рёбра:
• Жёлтые линии от точки S к каждой из терминальных точек.
3. Отображение в окне SFML
• Создаём окно SFML.
• Отображаем точки и соединяющие линии.
• Обновляем экран.

Шаг 4: Вывод результатов

1. Вывод координат точки Штейнера
2. Вывод длинны минимального дерева
3. Графическое представление :

- Красные точки — исходные точки

- Синяя точка — точка Штейнера

- Жёлтые линии — минимальное дерево

Код программы

#include <SFML/Graphics.hpp>
#include <iostream>
#include <cmath>
#include <vector>
#include <limits>

using namespace std;
using namespace sf;

struct Point {
    double x, y;
};

// Вычисление расстояния между двумя точками
double distance(Point a, Point b) {
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

// Сумма расстояний от точки p до всех остальных
double totalDistance(Point p, const vector<Point>& terminals) {
    double sum = 0;
    for (const auto& t : terminals) {
        sum += distance(p, t);
    }
    return sum;
}

// Метод градиентного спуска для поиска точки Штейнера
Point steinerPoint(const vector<Point>& terminals) {
    double step = 0.1;
    double precision = 1e-6;
    Point steiner = { 0, 0 };

    for (const auto& t : terminals) {
        steiner.x += t.x;
        steiner.y += t.y;
    }
    steiner.x /= terminals.size();
    steiner.y /= terminals.size();

    double prevDist = totalDistance(steiner, terminals);

    while (step > precision) {
        bool improved = false;

        for (double dx : {-step, step}) {
            for (double dy : {-step, step}) {
                Point newPoint = { steiner.x + dx, steiner.y + dy };
                double newDist = totalDistance(newPoint, terminals);

                if (newDist < prevDist) {
                    steiner = newPoint;
                    prevDist = newDist;
                    improved = true;
                }
            }
        }

        if (!improved) {
            step /= 2;
        }
    }

    return steiner;
}

// Основная функция
int main() {
    // Размер окна
    const int WIDTH = 600, HEIGHT = 600;

    // Исходные точки
    vector<Point> terminals = { {100, 500}, {500, 500}, {300, 100}};

    // Найдём точку Штейнера
    Point s = steinerPoint(terminals);

    // Создание окна SFML
    RenderWindow window(VideoMode(WIDTH, HEIGHT), "Steiner Tree Visualization");

    while (window.isOpen()) {
        Event event;
        while (window.pollEvent(event)) {
            if (event.type == Event::Closed)
                window.close();
        }

        // Очистка экрана
        window.clear(Color::Black);

        // Рисуем рёбра (жёлтые линии)
        for (const auto& t : terminals) {
            Vertex line[] = {
                Vertex(Vector2f(s.x, s.y), Color::Yellow),
                Vertex(Vector2f(t.x, t.y), Color::Yellow)
            };
            window.draw(line, 2, Lines);
        }

        // Рисуем терминальные точки (красные)
        for (const auto& t : terminals) {
            CircleShape terminal(5);
            terminal.setPosition(t.x - 5, t.y - 5);
            terminal.setFillColor(Color::Red);
            window.draw(terminal);
        }

        // Рисуем точку Штейнера (синяя)
        CircleShape steiner(5);
        steiner.setPosition(s.x - 5, s.y - 5);
        steiner.setFillColor(Color::Blue);
        window.draw(steiner);

        // Отображение кадра
        window.display();
    }

    return 0;
}

Итог

Метод использует градиентный спуск для поиска точки Штейнера и SFML для визуализации. Это позволяет эффективно решать задачу и демонстрировать результат в графическом окне.

Телеграмм канал - Программирование игр С++/С#