2
\$\begingroup\$

This a solution to the shortest bitonic tour using dynamic programming. Bitonic tour starts at the leftmost point then goes strictly rightward to the rightmost point and finally strictly leftward to the starting point. The complexity of this algorithm is . I also use sfml to draw it (Just started using it, this part is not my main focus).

Note: This algorithms assumes that no point has the same x coordinates and the input points are sorted by their x coordinates.

Bitonic tour:

namespace BT {

    struct Point {

        double x;
        double y;

        double distance(const Point& point) const {
            auto x_d = (x - point.x);
            auto y_d = (y - point.y);
            return std::sqrt((x_d * x_d) + (y_d * y_d));
        }

    };
    class Bitonic_details {
       static void bitonic_tour_build(const std::vector<Point>& points,
            std::vector<double>& lengths,
            std::vector<int>& last_stops) {

            if (points.size() < 2) {
                return;
            }
            last_stops[1] = -1;
            lengths[1] = points[0].distance(points[1]);
            for (int i = 2, size = points.size(); i < size; ++i) {
                double sum = 0;
                for (int k = i - 2; k >= 0; --k) {
                    double length = points[i].distance(points[k])
                                  + lengths[k + 1]
                                  + sum;

                    if (lengths[i] > length) {
                        lengths[i] = length;
                        last_stops[i] = k;
                    }
                    sum += points[k].distance(points[k + 1]);
                }
            }
        }

        static std::list<Point>* build_path(const std::vector<Point>& points, const std::vector<int>& last_stops) {

            std::list<Point> *path_A = new std::list<Point>();
            std::list<Point> *path_B = new std::list<Point>();

            int n = points.size() - 1;
            while (n > 0) {
                int k = last_stops[n];

                std::list<Point> temp;
                for (int j = k + 2; j < n; ++j) {
                    temp.push_back(points[j]);
                }
                path_B->splice(path_B->begin(), temp);
                path_A->push_front(points[n]);

                std::swap(path_A, path_B);
                n = k + 1;
            }
            path_B->reverse();
            path_B->splice(path_B->begin(), *path_A);
            if (!points.empty()) {
                path_B->push_back(points[0]);
                path_B->push_front(points[0]);
            }
            delete path_A;
            return path_B;
        }

        friend std::list<Point>* bitonic_tour(const std::vector<Point>& points);
    };

    std::list<Point>* bitonic_tour(const std::vector<Point>& points) {
        auto n = points.size();
        std::vector<double> lengths(n, DBL_MAX);
        std::vector<int> last_stops(n, 0);
        Bitonic_details::bitonic_tour_build(points, lengths, last_stops);
        return Bitonic_details::build_path(points, last_stops);
    }
}

Client (sfml):

#include "BitonicTour.h"
#include <iostream>
#include <random>
#include <SFML/Graphics.hpp>

void draw_points(sf::RenderWindow& rw,
                 const std::vector<BT::Point>& points,
                 double radius) {

    double offset = radius / 2;
    sf::CircleShape circle(1);

    for (const auto& p : points) {
        circle.setPosition(p.x - offset, p.y - offset);
        rw.draw(circle);
    }
}

void draw_path(sf::RenderWindow& rw,
               std::list<BT::Point>* path) {

    auto init    = path->front();
    auto vertex1 = sf::Vertex(sf::Vector2f(init.x, init.y));
    auto vertex2 = sf::Vertex();
    for (auto p : *path) {
        vertex2 = sf::Vertex(sf::Vector2f(p.x, p.y));
        sf::Vertex line[] = { vertex1, vertex2 };
        rw.draw(line, 10, sf::Lines);
        vertex1 = vertex2;
    }
}

std::vector<BT::Point> random_points(int size) {
    std::random_device                      rand_dev;
    std::mt19937                            generator(rand_dev());
    std::uniform_real_distribution<double>  distr(0, 200);
    std::uniform_real_distribution<double>  distr2(1, 10);
    std::vector<BT::Point>                  points;

    double inc = distr2(generator);
    for (int i = 0; i < size; ++i) {
        inc += distr2(generator);
        points.push_back(BT::Point{ inc, distr(generator) });
    }
    return points;
}
int main()
{
    auto             points = random_points(25);
    auto             path   = BT::bitonic_tour(points);
    sf::RenderWindow window  (sf::VideoMode(200, 200), "SFML works!");

    while (window.isOpen()) {
        sf::Event event;
        while (window.pollEvent(event)) {
            if (event.type == sf::Event::Closed) {
                window.close();
            }
        }
        window.clear();
        draw_points(window, points, 2);
        draw_path(window, path);
        window.display();
    }
    return 0;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.