convex-hull-visualizer/Game.cpp

#include <GL/glew.h>
#include <GLFW/glfw3.h>
#include <iostream>
#include <algorithm>
#include <chrono>
#include <fstream>
#include <cmath>

#include "Game.h"
#include "utils/Random.h"

constexpr float EPS = 0.00000001f;

bool compare(float a, float b) {
    return std::abs(a - b) < EPS;
}

bool Point::operator<(const Point& other) const {
    if(x == other.x) {
        return y < other.y;
    }
    return x < other.x;
}

float Point::distance(const Point& other) const {
    return (x - other.x) * (x - other.x) + (y - other.y) * (y - other.y);
}

Game::Game(Keys& keys, const char* file, bool steps) : keys(keys), keyNext(keys.add(GLFW_KEY_N)), active(0),
state(SPLIT) {
    if(file == nullptr) {
        Random r;
        int amount = steps ? 50 : 100000;
        for(int i = 0; i < amount; i++) {
            data.push_back({r.nextFloat(), r.nextFloat()});
        }
    } else {
        std::ifstream in;
        in.open(file);
        if(!in.good()) {
            std::cout << "cannot read '" << file << "'\n";
            return;
        }
        int count;
        in >> count;
        while(in.get() != '\n');
        for(int i = 0; i < count; i++) {
            float x;
            float y;
            in >> x;
            in.get();
            in >> y;
            while(!in.eof() && in.get() != '\n');
            data.push_back({x, y});
        }
    }

    if(data.size() > 0) {
        minX = data[0].x;
        maxX = data[0].x;
        minY = data[0].y;
        maxY = data[0].y;
        for(const Point& p : data) {
            if(p.x < minX) {
                minX = p.x;
            }
            if(p.x > maxX) {
                maxX = p.x;
            }
            if(p.y < minY) {
                minY = p.y;
            }
            if(p.y > maxY) {
                maxY = p.y;
            }
        }
    }

    if(!steps) {
        skip();
    }
}

bool Game::merge() {
    auto start = groups[active].begin();
    auto end = groups[active].end();
    if(start == end) {
        if(groups[1 - active].begin() == groups[1 - active].end() ||
                groups[1 - active].begin() + 1 == groups[1 - active].end()) {
            return false;
        }
        active = 1 - active;
    } else if(start + 1 == end) {
        std::vector<Point> group = groups[active].front();
        groups[active].pop_front();
        groups[1 - active].push_back(group);
        return merge();
    }

    hullA = groups[active].front();
    groups[active].pop_front();
    hullB = groups[active].front();
    groups[active].pop_front();

    lowerIndexA = findMaxX(hullA);
    lowerIndexB = findMinX(hullB);

    upperIndexA = lowerIndexA;
    upperIndexB = lowerIndexB;
    return true;
}

void Game::finalizeMerge() {
    std::vector<Point> mergedHull;
    mergedHull.reserve(hullA.size() + hullB.size());

    while(lowerIndexA != upperIndexA) {
        mergedHull.push_back(hullA[lowerIndexA]);
        lowerIndexA = (lowerIndexA + 1) % hullA.size();
    }
    mergedHull.push_back(hullA[upperIndexA]);

    while(upperIndexB != lowerIndexB) {
        mergedHull.push_back(hullB[upperIndexB]);
        upperIndexB = (upperIndexB + 1) % hullB.size();
    }
    mergedHull.push_back(hullB[lowerIndexB]);

    groups[1 - active].push_back(mergedHull);
}

void Game::split() {
    std::sort(data.begin(), data.end());

    int index = 0;
    while(index + 2 < static_cast<int> (data.size())) {
        groups[active].push_back(std::vector<Point>());
        std::vector<Point>& v = groups[active].back();
        Point& a = data[index];
        Point& b = data[index + 1];
        Point& c = data[index + 2];
        float f = det(a, b, c);
        if(compare(f, 0.0f)) {
            v.push_back({std::min(a.x, std::min(b.x, c.x)), std::min(a.y, std::min(b.y, c.y))});
            v.push_back({std::max(a.x, std::max(b.x, c.x)), std::max(a.y, std::max(b.y, c.y))});
        } else if(f > 0.0f) {
            v.push_back(a);
            v.push_back(c);
            v.push_back(b);
        } else {
            v.push_back(a);
            v.push_back(b);
            v.push_back(c);
        }
        index += 3;
    }
    int diff = data.size() - index;
    if(diff > 0) {
        groups[active].push_back(std::vector<Point>());
        std::vector<Point>& v = groups[active].back();
        while(index < static_cast<int> (data.size())) {
            v.push_back(data[index++]);
        }
    }
}

bool Game::isLowerTangent(const std::vector<Point>& hull) const {
    for(const Point& p : hull) {
        float f = det(hullA[lowerIndexA], hullB[lowerIndexB], p);
        if(f < -EPS) {
            return false;
        }
    }
    return true;
}

bool Game::isUpperTangent(const std::vector<Point>& hull) const {
    for(const Point& p : hull) {
        float f = det(hullA[upperIndexA], hullB[upperIndexB], p);
        if(f > EPS) {
            return false;
        }
    }
    return true;
}

bool Game::findLowerTangent() {
    if(!isLowerTangent(hullA)) {
        lowerIndexA = (lowerIndexA + 1) % hullA.size();
    } else if(!isLowerTangent(hullB)) {
        lowerIndexB = (lowerIndexB == 0) ? hullB.size() - 1 : lowerIndexB - 1;
    }
    if(!isLowerTangent(hullA) || !isLowerTangent(hullB)) {
        return true;
    }
    for(int i = 0; i < static_cast<int> (hullA.size()); i++) {
        if(i != lowerIndexA && compare(det(hullA[lowerIndexA], hullB[lowerIndexB], hullA[i]), 0.0f)) {
            if(hullB[lowerIndexB].distance(hullA[i]) > hullB[lowerIndexB].distance(hullA[lowerIndexA])) {
                lowerIndexA = i;
            }
        }
    }
    for(int i = 0; i < static_cast<int> (hullB.size()); i++) {
        if(i != lowerIndexB && compare(det(hullA[lowerIndexA], hullB[lowerIndexB], hullB[i]), 0.0f)) {
            if(hullA[lowerIndexA].distance(hullB[i]) > hullA[lowerIndexA].distance(hullB[lowerIndexB])) {
                lowerIndexB = i;
            }
        }
    }
    return false;
}

bool Game::findUpperTangent() {
    if(!isUpperTangent(hullA)) {
        upperIndexA = (upperIndexA == 0) ? hullA.size() - 1 : upperIndexA - 1;
    } else if(!isUpperTangent(hullB)) {
        upperIndexB = (upperIndexB + 1) % hullB.size();
    }
    if(!isUpperTangent(hullA) || !isUpperTangent(hullB)) {
        return true;
    }
    for(int i = 0; i < static_cast<int> (hullA.size()); i++) {
        if(i != upperIndexA && compare(det(hullA[upperIndexA], hullB[upperIndexB], hullA[i]), 0.0f)) {
            if(hullB[upperIndexB].distance(hullA[i]) > hullB[upperIndexB].distance(hullA[upperIndexA])) {
                upperIndexA = i;
            }
        }
    }
    for(int i = 0; i < static_cast<int> (hullB.size()); i++) {
        if(i != upperIndexB && compare(det(hullA[upperIndexA], hullB[upperIndexB], hullB[i]), 0.0f)) {
            if(hullA[upperIndexA].distance(hullB[i]) > hullA[upperIndexA].distance(hullB[upperIndexB])) {
                upperIndexB = i;
            }
        }
    }
    return false;
}

int Game::findMaxX(const std::vector<Point>& hull) const {
    if(hull.size() == 0) {
        return -1;
    }
    int index = 0;
    for(int i = 1; i < static_cast<int> (hull.size()); i++) {
        if(hull[i].x > hull[index].x) {
            index = i;
        }
    }
    return index;
}

int Game::findMinX(const std::vector<Point>& hull) const {
    if(hull.size() == 0) {
        return -1;
    }
    int index = 0;
    for(int i = 1; i < static_cast<int> (hull.size()); i++) {
        if(hull[i].x < hull[index].x) {
            index = i;
        }
    }
    return index;
}

void Game::tick() {
    if(keys.getDownTime(keyNext) == 1) {
        next();
    }
    if(keys.getDownTime(keyNext) >= 60) {
        for(int i = 0; i < 100; i++) {
            next();
        }
    }
}

void Game::next() {
    switch(state) {
        case SPLIT:
            split();
            state = MERGE;
            break;
        case MERGE:
            if(merge()) {
                state = FIND_LOWER_TANGENT;
            } else {
                state = END;
                hullA.clear();
                hullB.clear();
            }
            break;
        case FIND_LOWER_TANGENT:
            if(!findLowerTangent()) {
                state = FIND_UPPER_TANGENT;
            }
            break;
        case FIND_UPPER_TANGENT:
            if(!findUpperTangent()) {
                state = FINALIZE_MERGE;
            }
            break;
        case FINALIZE_MERGE:
            finalizeMerge();
            state = MERGE;
            break;
        default:
            break;
    }
}

void Game::render(float lag, Renderer& renderer) const {
    (void) lag;
    renderer.setPointSize(7);
    for(const Point& p : data) {
        renderer.drawPoint(normalizeX(p.x), normalizeY(p.y), 0x707070);
    }

    for(int k = 0; k < 2; k++) {
        for(const std::vector<Point> group : groups[k]) {
            renderGroup(renderer, group, 0xFFFFFF);
        }
    }

    renderGroup(renderer, hullA, 0xFF00FF);
    renderGroup(renderer, hullB, 0xFFFF00);

    if(state == FIND_LOWER_TANGENT || state == FIND_UPPER_TANGENT || state == FINALIZE_MERGE) {
        renderer.drawLine(
                normalizeX(hullA[lowerIndexA].x), normalizeY(hullA[lowerIndexA].y),
                normalizeX(hullB[lowerIndexB].x), normalizeY(hullB[lowerIndexB].y),
                0x00FFFF);
        renderer.drawLine(
                normalizeX(hullA[upperIndexA].x), normalizeY(hullA[upperIndexA].y),
                normalizeX(hullB[upperIndexB].x), normalizeY(hullB[upperIndexB].y),
                0x00FFFF);
    }
}

bool Game::isRunning() const {
    return true;
}

float Game::det(const Point& a, const Point& b, const Point& c) const {
    return (a.x - c.x) * (b.y - c.y) - (b.x - c.x) * (a.y - c.y);
}

void Game::renderGroup(Renderer& renderer, const std::vector<Point>& group, uint color) const {
    static unsigned int colorMap[] = {
        0xFF0000, 0x00FF00, 0x0000FF
    };
    for(int i = 0; i < static_cast<int> (group.size()); i++) {
        int next = (i + 1) % group.size();
        renderer.drawLine(
                normalizeX(group[i].x),
                normalizeY(group[i].y),
                normalizeX(group[next].x),
                normalizeY(group[next].y),
                color);
    }
    for(int i = 0; i < static_cast<int> (group.size()); i++) {
        renderer.drawPoint(normalizeX(group[i].x), normalizeY(group[i].y), colorMap[i % 3]);
    }
}

void Game::skip() {
    long time = std::chrono::high_resolution_clock::now().time_since_epoch().count();
    split();
    while(merge()) {
        while(findLowerTangent());
        while(findUpperTangent());
        finalizeMerge();
    }
    time = std::chrono::high_resolution_clock::now().time_since_epoch().count() - time;
    std::cout << "Took " << (time / 1000000.0) << "ms\n";
    state = END;
    hullA.clear();
    hullB.clear();
}

float Game::normalizeX(float f) const {
    if(compare(maxX, minX)) {
        return 0.0f;
    }
    f = (f - minX) / (maxX - minX);
    return f * 1.90f - 0.95f;
}

float Game::normalizeY(float f) const {
    if(compare(maxY, minY)) {
        return 0.0f;
    }
    f = (f - minY) / (maxY - minY);
    return f * 1.90f - 0.95f;
}