convex-hull-visualizer/Game.cpp

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

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

bool Game::Point::operator<(const Point& other) {
    if(std::abs(x - other.x) < 0.0001f) {
        return y < other.y;
    }
    return x < other.x;
}

Game::Game(Keys& keys) : keys(keys), keyNext(keys.add(GLFW_KEY_N)), active(0) {
    std::cout << "register on " << keys.add(GLFW_KEY_W) << "\n";

    Random r(6476);
    for(int i = 0; i < 25; i++) {
        data.push_back({r.nextFloat() * 1.9f - 0.95f, r.nextFloat() * 1.9f - 0.95f});
        //float f = r.nextFloat() * 1.9f - 0.95f;
        //data.push_back({f * 0.8f, f});
        //data.push_back({r.nextFloat() * 1.9f - 0.95f, 0});
        //data.push_back({0, r.nextFloat() * 1.9f - 0.95f});
    }

    std::cout << data.size() << "\n";

    split();
}

void Game::merge() {
    auto start = groups[active].begin();
    auto end = groups[active].end();
    if(start == end) {
        if(groups[1 - active].begin() + 1 == groups[1 - active].end()) {
            return;
        }
        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;
    }

    std::vector<Point> hullA = groups[active].front();
    groups[active].pop_front();
    std::vector<Point> hullB = groups[active].front();
    groups[active].pop_front();

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

    int lowerIndexA;
    int lowerIndexB;
    findLowerTangent(hullA, hullB, lowerIndexA, lowerIndexB);

    int upperIndexA;
    int upperIndexB;
    findUpperTangent(hullA, hullB, upperIndexA, upperIndexB);

    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();
        v.push_back(data[index++]);
        v.push_back(data[index++]);
        v.push_back(data[index++]);
        float f = det(groups[active].back()[0], groups[active].back()[1], groups[active].back()[2]);
        if(std::abs(f) < 0.0001f) {
            if(std::abs(v[0].y - v[1].y) > 0.0001f || std::abs(v[1].y - v[2].y) > 0.0001f) {
                v[0].x = (std::abs(v[0].x) < 0.0001f) ? 0.001f : v[0].x * 1.001f;
            } else {
                v[0].y = (std::abs(v[0].y) < 0.0001f) ? 0.001f : v[0].y * 1.001f;
            }
            f = det(groups[active].back()[0], groups[active].back()[1], groups[active].back()[2]);
            if(f > 0.0f) {
                std::swap(groups[active].back()[1], groups[active].back()[2]);
            }
        } else if(f > 0.0f) {
            std::swap(groups[active].back()[1], groups[active].back()[2]);
        }
    }
    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 Point& a, const Point& b, const std::vector<Point>& hull) const {
    for(const Point& p : hull) {
        float det = (a.x - p.x) * (b.y - p.y) - (b.x - p.x) * (a.y - p.y);
        if(det < -0.00001f) {
            return false;
        }
    }
    return true;
}

bool Game::isUpperTangent(const Point& a, const Point& b, const std::vector<Point>& hull) const {
    for(const Point& p : hull) {
        float det = (a.x - p.x) * (b.y - p.y) - (b.x - p.x) * (a.y - p.y);
        if(det > 0.00001f) {
            return false;
        }
    }
    return true;
}

void Game::findLowerTangent(const std::vector<Point>& hullA, const std::vector<Point>& hullB, int& a, int& b) const {
    a = findMaxX(hullA);
    b = findMinX(hullB);

    while(!isLowerTangent(hullA[a], hullB[b], hullA) || !isLowerTangent(hullA[a], hullB[b], hullB)) {
        while(!isLowerTangent(hullA[a], hullB[b], hullA)) {
            a = (a + 1) % hullA.size();
        }
        while(!isLowerTangent(hullA[a], hullB[b], hullB)) {
            b = (b == 0) ? hullB.size() - 1 : b - 1;
        }
    }
}

void Game::findUpperTangent(const std::vector<Point>& hullA, const std::vector<Point>& hullB, int& a, int& b) const {
    a = findMaxX(hullA);
    b = findMinX(hullB);
    while(!isUpperTangent(hullA[a], hullB[b], hullA) || !isUpperTangent(hullA[a], hullB[b], hullB)) {
        while(!isUpperTangent(hullA[a], hullB[b], hullA)) {
            a = (a == 0) ? hullA.size() - 1 : a - 1;
        }
        while(!isUpperTangent(hullA[a], hullB[b], hullB)) {
            b = (b + 1) % hullB.size();
        }
    }
}

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) {
        merge();
    }
    if(keys.getDownTime(keyNext) >= 40) {
        merge();
    }
}

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

    static unsigned int color[] = {
        0xFF0000, 0x00FF00, 0x0000FF
    };
    for(int k = 0; k < 2; k++) {
        for(const std::vector<Point> group : groups[k]) {
            for(int i = 0; i < static_cast<int> (group.size()); i++) {
                int next = (i + 1) % group.size();
                renderer.drawLine(
                        group[i].x,
                        group[i].y,
                        group[next].x,
                        group[next].y,
                        0xFFFFFF);
            }
            for(int i = 0; i < static_cast<int> (group.size()); i++) {
                renderer.drawPoint(group[i].x, group[i].y, color[i % 3]);
            }
        }
    }
}

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);
}