123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394 |
- #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) {
- // try getting number
- int amount = atoi(file);
- if(amount > 0) {
- Random r;
- 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 << (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;
- }
|