C++ 实现两点间最短可见路线算法

#include #include #include #include #include #include <SFML/Graphics.hpp>

struct Point { float x; float y; };

struct Line { Point start; Point end; bool isBroken; };

float dist(Point p1, Point p2) { return std::sqrt(std::pow(p2.x - p1.x, 2) + std::pow(p2.y - p1.y, 2)); }

std::vector generateLines(Point p1, Point p2, int n) { std::vector lines;

// Generate random lines
for (int i = 0; i < n; i++) {
    Line line;
    line.start.x = static_cast<float>(rand()) / RAND_MAX * (p2.x - p1.x) + p1.x;
    line.start.y = static_cast<float>(rand()) / RAND_MAX * (p2.y - p1.y) + p1.y;
    line.end.x = static_cast<float>(rand()) / RAND_MAX * (p2.x - p1.x) + p1.x;
    line.end.y = static_cast<float>(rand()) / RAND_MAX * (p2.y - p1.y) + p1.y;
    line.isBroken = (rand() % 2 == 0);
    lines.push_back(line);
}

return lines;

}

bool isLineVisible(Line line, std::vector lines) { for (const auto& otherLine : lines) { if (otherLine.start.x == line.start.x && otherLine.start.y == line.start.y && otherLine.end.x == line.end.x && otherLine.end.y == line.end.y) { continue; }

    if (!otherLine.isBroken) {
        // Check if line is blocked
        if ((line.start.x >= otherLine.start.x && line.start.x <= otherLine.end.x &&
             line.start.y >= otherLine.start.y && line.start.y <= otherLine.end.y) ||
            (line.end.x >= otherLine.start.x && line.end.x <= otherLine.end.x &&
             line.end.y >= otherLine.start.y && line.end.y <= otherLine.end.y) ||
            (line.start.x <= otherLine.start.x && line.end.x >= otherLine.end.x &&
             line.start.y >= otherLine.start.y && line.start.y <= otherLine.end.y) ||
            (line.start.x >= otherLine.start.x && line.start.x <= otherLine.end.x &&
             line.start.y <= otherLine.start.y && line.end.y >= otherLine.end.y)) {
            return false;
        }
    }
}

return true;

}

Line findShortestLine(Point p1, Point p2, int n) { std::vector lines = generateLines(p1, p2, n); Line shortestLine; float shortestDist = std::numeric_limits::max();

// Find shortest visible line
for (const auto& line : lines) {
    if (isLineVisible(line, lines)) {
        float d = dist(line.start, line.end);
        if (d < shortestDist) {
            shortestDist = d;
            shortestLine = line;
        }
    }
}

return shortestLine;

}

int main() { srand(static_cast(time(nullptr)));

// Create window
sf::RenderWindow window(sf::VideoMode(800, 600), 'Shortest Line');

while (window.isOpen()) {
    sf::Event event;
    while (window.pollEvent(event)) {
        if (event.type == sf::Event::Closed) {
            window.close();
        }
    }
    
    // Generate random points
    Point p1;
    p1.x = static_cast<float>(rand()) / RAND_MAX * 600;
    p1.y = static_cast<float>(rand()) / RAND_MAX * 400;
    Point p2;
    p2.x = static_cast<float>(rand()) / RAND_MAX * 600;
    p2.y = static_cast<float>(rand()) / RAND_MAX * 400;
    
    // Find shortest line
    Line shortestLine = findShortestLine(p1, p2, 40);
    
    // Draw lines
    window.clear();
    for (const auto& line : generateLines(p1, p2, 40)) {
        sf::VertexArray vertices(sf::Lines, 2);
        vertices[0].position = sf::Vector2f(line.start.x, line.start.y);
        vertices[1].position = sf::Vector2f(line.end.x, line.end.y);
        if (line.isBroken) {
            vertices[0].color = sf::Color::Red;
            vertices[1].color = sf::Color::Red;
        }
        window.draw(vertices);
    }
    
    // Draw shortest line
    sf::VertexArray shortestVertices(sf::Lines, 2);
    shortestVertices[0].position = sf::Vector2f(shortestLine.start.x, shortestLine.start.y);
    shortestVertices[1].position = sf::Vector2f(shortestLine.end.x, shortestLine.end.y);
    shortestVertices[0].color = sf::Color::Green;
    shortestVertices[1].color = sf::Color::Green;
    shortestVertices[0].thickness = 5;
    shortestVertices[1].thickness = 5;
    window.draw(shortestVertices);
    
    window.display();
}

return 0;