Quadtrees

main.cpp

#include <cmath>
#include <vector>

#include "windows.h"

#include "lodepng.h"
#include "SDL.h"

typedef std::vector<unsigned char> Image;

unsigned imgW, imgH;

struct QuadTree {
	std::vector<QuadTree> sub;
	int x, y, sizeX, sizeY;
	int col[3];
	double diff = 0;
	QuadTree(int _x, int _y, int _sizeX, int _sizeY, Image &image) :
		x(_x),
		y(_y),
		sizeX(_sizeX),
		sizeY(_sizeY)
	{
		col[0] = 0; col[1] = 0; col[2] = 0;
		for (int i = x; i < x + sizeX; ++i){
			for (int j = y; j < y + sizeY; ++j){
				int xy = (j * imgW + i) * 4;
				col[0] += image[xy];
				col[1] += image[xy + 1];
				col[2] += image[xy + 2];
			}
		}
		col[0] /= (sizeX*sizeY);
		col[1] /= (sizeX*sizeY);
		col[2] /= (sizeX*sizeY);

		for (int i = x; i < x + sizeX; ++i){
			for (int j = y; j < y + sizeY; ++j){
				int xy = (j * imgW + i) * 4;
				diff += pow((int)image[xy] - col[0], 2);
				diff += pow((int)image[xy + 1] - col[1], 2);
				diff += pow((int)image[xy + 2] - col[2], 2);
			}
		}
		diff /= sizeX;
	}
};

void divide(QuadTree &tree, Image &image){
	int x = tree.x;
	int y = tree.y;
	int sizeX = tree.sizeX;
	int sizeY = tree.sizeY;
	tree.sub.emplace_back(
		x, y,
		sizeX / 2,
		sizeY / 2,
		image);
	tree.sub.emplace_back(
		x + sizeX / 2, y,
		sizeX - sizeX / 2,
		sizeY / 2,
		image);
	tree.sub.emplace_back(
		x, y + sizeY / 2,
		sizeX / 2,
		sizeY - sizeY / 2,
		image);
	tree.sub.emplace_back(
		x + sizeX / 2, y + sizeY / 2,
		sizeX - sizeX / 2,
		sizeY - sizeY / 2,
		image);
}

QuadTree* findWorst(QuadTree &tree){
	if (tree.sub.empty())
		return &tree;

	double worstValue = 0;
	QuadTree *worst = nullptr;

	for (int i = 0; i < 4; ++i){
		QuadTree *temp = findWorst(tree.sub[i]);
		if (temp == nullptr) continue;
		if (temp->sizeX < 2 || temp->sizeY < 2) continue;
		double tempValue = temp->diff;
		if (tempValue > worstValue){
			worstValue = tempValue;
			worst = temp;
		}
	}
	return worst;
}

void draw(SDL_Renderer *ren, QuadTree &tree){
	SDL_Rect rect = { tree.x, tree.y,
		tree.sizeX - 1, tree.sizeY - 1 };		//draws black borders
		//tree.sizeX, tree.sizeY };				//no borders
	if (tree.sub.empty()){
		SDL_SetRenderDrawColor(ren, tree.col[0], tree.col[1], tree.col[2], 255);
		SDL_RenderFillRect(ren, &rect);
	} else {
		SDL_SetRenderDrawColor(ren, 0, 0, 0, 255);
		SDL_RenderFillRect(ren, &rect);
		for (auto&& sub : tree.sub)
			draw(ren, sub);
	}
}


int _stdcall WinMain(HINSTANCE, HINSTANCE, char*, int){
	Image image;
	lodepng::decode(image, imgW, imgH, "image.png");

	SDL_Window *window;
	SDL_Renderer *ren;
	SDL_CreateWindowAndRenderer(imgW, imgH, SDL_WINDOW_SHOWN, &window, &ren);

	QuadTree tree(0, 0, imgW, imgH, image);

	bool stop = false;
	bool done = false;
	int iteration = 0;

	LARGE_INTEGER frequency;        // ticks per second
	LARGE_INTEGER t1, t2, t3;           // ticks
	double calcTime, drawTime;
	QueryPerformanceFrequency(&frequency);

	while(!done){
		SDL_Event event;
		while(SDL_PollEvent(&event)){
			if (event.type == SDL_QUIT)
				done = true;
		}

		QueryPerformanceCounter(&t1);

		if (!stop){
			QuadTree* ptr = findWorst(tree);
			if (ptr == nullptr) 
				stop = true;
			else {
				divide(*ptr, image);
				QueryPerformanceCounter(&t2);
				draw(ren, *ptr);
			}
			iteration++;
			if (iteration > 50000) stop = true;
		}

		SDL_RenderPresent(ren);

		QueryPerformanceCounter(&t3);

		if (iteration % 20 == 0 && !stop){
			calcTime = (t2.QuadPart - t1.QuadPart) * 1000.0 / frequency.QuadPart;
			drawTime = (t3.QuadPart - t2.QuadPart) * 1000.0 / frequency.QuadPart;

			char str[80];
			sprintf(str, "%d cycles, %f ms for algorithm, %f ms for drawing", iteration, calcTime, drawTime);
			SDL_SetWindowTitle(window, str);
		}

		if(stop)
			SDL_Delay(1);
	}

	SDL_DestroyWindow(window);
	SDL_DestroyRenderer(ren);

	return 0;
}