Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- * @file quadtree.cpp
- * quadtree class implementation.
- * @date Spring 2008
- * @date Modified Summer 2014
- */
- #include <iostream>
- #include <cstdint>
- #include <memory>
- #include <exception>
- #include <cmath>
- #include "quadtree.h"
- #include "epng.h"
- #include "rgba_pixel.h"
- namespace cs225
- {
- /*
- * Constructors for the quadtree class:
- * Defualt constructor
- * Cropped image Constructor
- * Copy constructor
- * Move constructor
- */
- quadtree::quadtree()
- :root_{nullptr}, size_{0}
- {
- //Call the defualt node constructor
- node();
- }
- quadtree::quadtree(const epng::png& source, uint64_t resolution)
- :root_{nullptr}, size_{0}
- {
- //Build_tree will initialize and construct the tree
- build_tree(source, resolution);
- }
- quadtree::quadtree(const quadtree& other)
- :root_{nullptr}, size_{other.size_}
- {
- //Check if other is empty
- if(other.root_ != nullptr)
- root_ = std::make_unique<node>(node(*(other.root_.get())));
- }
- quadtree::quadtree(quadtree&& other)
- :root_{nullptr}, size_{0}
- {
- std::swap(root_, other.root_);
- std::swap(size_, other.size_);
- }
- /*
- * Constructors for the node structures:
- * Defualt constructor
- * Copy constructor
- */
- quadtree::node::node()
- :northwest{nullptr}, northeast{nullptr},
- southwest{nullptr}, southeast{nullptr},
- element{epng::rgba_pixel()}
- {
- //Nothing!
- }
- quadtree::node::node(const node& other)
- :northwest{nullptr}, northeast{nullptr},
- southwest{nullptr}, southeast{nullptr},
- element{epng::rgba_pixel()}
- {
- //Copy over all the nodes and elements
- element = std::move(copy_nodes(other));
- }
- quadtree& quadtree::operator=(quadtree other)
- {
- if(root_ != nullptr)
- {
- clear(*(root_.get()));
- root_.reset(nullptr);
- }
- size_ = std::move(other.size_);
- swap(other);
- return *this;
- }
- const epng::rgba_pixel& quadtree::operator()(uint64_t x, uint64_t y) const
- {
- uint64_t x_bound = size_;
- uint64_t y_bound = size_;
- epng::rgba_pixel temp = epng::rgba_pixel();
- //Check the bounds of the given coordinates
- if(!root_)
- throw std::out_of_range("Empty tree");
- else if(x > (size_-1) || y > (size_-1))
- throw std::out_of_range("Invalid coordinates");
- //Call the helper function to return the pixel
- return find_pixel(*(root_.get()), temp, x, y, x_bound, y_bound);
- }
- void quadtree::build_tree(const epng::png& source, uint64_t resolution)
- {
- uint64_t height = 0;
- uint64_t level = 0;
- uint64_t x = 0;
- uint64_t y = 0;
- uint64_t iter_x = 0;
- uint64_t iter_y = 0;
- int base = 0;
- if(root_ != nullptr)
- {
- //Delete the contents of the current tree
- clear(*(root_.get()));
- root_ = nullptr;
- }
- //Set the size of the quadtree
- size_ = resolution;
- //Compute the height of the tree to be built
- height = log2(resolution);
- //Create the root for the tree
- root_ = std::make_unique<node>(node());
- //build the tree by looping through the pixels recursively
- build_tree(source, resolution, *(root_.get()), level, height, x, y, iter_x, iter_y, base);
- }
- epng::png quadtree::decompress() const
- {
- //Check for an empty tree
- if(!root_)
- throw std::runtime_error("Empty tree");
- //Create the png image from the quadtree
- epng::png* out_png = new epng::png(size_, size_);
- epng::png temp_png = epng::png(size_, size_);
- uint64_t height = log2(size_);
- //Set each pixel to its respective pixel in the quadtree
- *out_png = get_pixels(*(root_.get()), temp_png, size_, size_, height+1);
- return *out_png;
- }
- void quadtree::rotate_clockwise()
- {
- //Call the helper function
- rotate_clockwise(*(root_.get()));
- }
- void quadtree::clear(node& subroot)
- {
- //Perform a depth-first deletion of the tree
- //Base case: At a leaf
- if(!subroot.northwest.get() && !subroot.northeast.get() && !subroot.southwest.get() && !subroot.southeast.get())
- {
- return;
- }
- //Traverse the Northwest child
- if(subroot.northwest.get() != nullptr)
- {
- clear(*(subroot.northwest.get()));
- subroot.northwest.reset(nullptr);
- }
- //Traverse the Northeast child
- if(subroot.northeast.get() != nullptr)
- {
- clear(*(subroot.northeast.get()));
- subroot.northeast.reset(nullptr);
- }
- //Traverse the Southwest child
- if(subroot.southwest.get() != nullptr)
- {
- clear(*(subroot.southwest.get()));
- subroot.southwest.reset(nullptr);
- }
- //Traverse the Southeast child
- if(subroot.southeast.get() != nullptr)
- {
- clear(*(subroot.southeast.get()));
- subroot.southeast.reset(nullptr);
- }
- return;
- }
- void quadtree::swap(quadtree& other)
- {
- //Call the copy_nodes function to copy the nodes
- root_ = std::make_unique<node>(node(*(other.root_.get())));
- }
- void quadtree::build_tree(const epng::png source, const uint64_t scope, node& subroot, uint64_t level,
- const uint64_t height, uint64_t x, uint64_t y, uint64_t iter_x, uint64_t iter_y, int& base)
- {
- if(base == pow(scope, 2))
- return;
- iter_x = x;
- iter_y = y;
- //Base case: At a leaf
- if(level == height)
- {
- base++;
- //Get the element
- subroot.element = std::move(*source(x+iter_x, y+iter_y));
- if(iter_x == 1)
- {
- iter_x = 0;
- if(iter_y == 1)
- iter_y = 0;
- else
- iter_y++;
- }
- else
- iter_x++;
- return;
- }
- //Perform a breadth-first like build of the tree
- subroot.northwest = std::make_unique<node>(node());
- subroot.northeast = std::make_unique<node>(node());
- subroot.southwest = std::make_unique<node>(node());
- subroot.southeast = std::make_unique<node>(node());
- level++;
- //recursively call the the subroots
- build_tree(source, scope, *(subroot.northwest.get()), level, height, x, y, iter_x, iter_y, base);
- build_tree(source, scope, *(subroot.northeast.get()), level, height, (x+(level/2)), y, iter_x, iter_y, base);
- build_tree(source, scope, *(subroot.southwest.get()), level, height, x, (y+(level/2)), iter_x, iter_y, base);
- build_tree(source, scope, *(subroot.southeast.get()), level, height, (x+(level/2)), (y+(level/2)), iter_x, iter_y, base);
- //Compute the average of the colors
- subroot.element.red = (subroot.northwest.get()->element.red + subroot.northeast.get()->element.red +
- subroot.southwest.get()->element.red + subroot.southeast.get()->element.red)/4;
- subroot.element.green = (subroot.northwest.get()->element.green + subroot.northeast.get()->element.green +
- subroot.southwest.get()->element.green + subroot.southeast.get()->element.green)/4;
- subroot.element.blue = (subroot.northwest.get()->element.blue + subroot.northeast.get()->element.blue +
- subroot.southwest.get()->element.blue + subroot.southeast.get()->element.blue)/4;
- subroot.element.alpha = (subroot.northwest.get()->element.alpha + subroot.northeast.get()->element.alpha +
- subroot.southwest.get()->element.alpha + subroot.southeast.get()->element.alpha)/4;
- return;
- }
- const epng::rgba_pixel& quadtree::find_pixel(node& subroot, epng::rgba_pixel& temp, const uint64_t x, const uint64_t y,
- uint64_t x_bound, uint64_t y_bound) const
- {
- //Base case: At a leaf
- if(!subroot.northwest.get() && !subroot.northeast.get() && !subroot.southwest.get() && !subroot.southeast.get())
- {
- temp = subroot.element;
- return temp;
- }
- if(x >= (x_bound/2))
- {
- if(y >= (y_bound/2))
- {
- //Pixel is in the southeast node
- temp = find_pixel(*(subroot.southeast.get()), temp, x, y, (x_bound+2), (y_bound+2));
- }
- else
- {
- //Pixel is in the northeast node
- temp = find_pixel(*(subroot.northeast.get()), temp, x, y, (x_bound+2), (y_bound/2));
- }
- }
- else
- {
- if(y >= (y_bound/2))
- {
- //Pixel is in the southwest node
- temp = find_pixel(*(subroot.southwest.get()), temp, x, y, (x_bound/2), (y_bound+2));
- }
- else
- {
- //Pixel is in the northwest node
- temp = find_pixel(*(subroot.northwest.get()), temp, x, y, (x_bound/2), (y_bound/2));
- }
- }
- return temp;
- }
- const epng::png& quadtree::get_pixels(const node& subroot, epng::png& out_png, uint64_t x, uint64_t y, uint64_t level) const
- {
- //Base case: At a leaf
- if(!subroot.northwest.get() && !subroot.northeast.get() && !subroot.southwest.get() && !subroot.southeast.get())
- {
- *out_png(x-1, y-1) = subroot.element;
- return out_png;
- }
- level--;
- //Traverse the northwest node
- if(subroot.northwest.get() != nullptr)
- get_pixels(*(subroot.northwest.get()), out_png, ceil(x/2), ceil(y/2), level);
- //Traverse the northeast node
- if(subroot.northeast.get() != nullptr)
- get_pixels(*(subroot.northeast.get()), out_png, ceil(x/2+level), ceil(y/2), level);
- //Traverse the southwest node
- if(subroot.southwest.get() != nullptr)
- get_pixels(*(subroot.southwest.get()), out_png, ceil(x/2), ceil(y/2+level),level);
- //Traverse the southeast node
- if(subroot.southeast.get() != nullptr)
- get_pixels(*(subroot.southeast.get()), out_png, ceil(x/2+level), ceil(y/2+level), level);
- return out_png;
- }
- const epng::rgba_pixel& quadtree::node::copy_nodes(const node& other)
- {
- //Base case: At a leaf
- if(!other.northwest.get() && !other.northeast.get() && !other.southwest.get() && !other.southeast.get())
- {
- return other.element;
- }
- //Traverse the northwest node
- if(other.northwest.get() != nullptr)
- {
- //Create a node at the child
- this->northwest = std::make_unique<node>(node(*(other.northwest.get())));
- }
- //Traverse the northeast node
- if(other.northeast.get() != nullptr)
- {
- //Create a node at the child
- this->northeast = std::make_unique<node>(node(*(other.northeast.get())));
- }
- //Traverse the southwest node
- if(other.southwest.get() != nullptr)
- {
- //Create a node at the child
- this->southwest = std::make_unique<node>(node(*(other.southwest.get())));
- }
- //Traverse the southeast node
- if(other.southeast.get() != nullptr)
- {
- //Create a node at the child
- this->southeast = std::make_unique<node>(node(*(other.southeast.get())));
- }
- return other.element;
- }
- void quadtree::rotate_clockwise(node& subroot)
- {
- //Base case: At a leaf
- if(!subroot.northwest.get() && !subroot.northeast.get() && !subroot.southwest.get() && !subroot.southeast.get())
- {
- return;
- }
- //Traverse the northwest node
- if(subroot.northwest != nullptr)
- {
- rotate_clockwise(*(subroot.northwest.get()));
- //Rotate the nodes
- std::swap(subroot.northwest, subroot.southeast);
- std::swap(subroot.northwest, subroot.southwest);
- std::swap(subroot.northwest, subroot.northeast);
- }
- //Traverse the northeast node
- if(subroot.northeast != nullptr)
- {
- rotate_clockwise(*(subroot.northeast.get()));
- //Rotate the nodes
- std::swap(subroot.northwest, subroot.southeast);
- std::swap(subroot.northwest, subroot.southwest);
- std::swap(subroot.northwest, subroot.northeast);
- }
- //Traverse the southwest node
- if(subroot.southwest != nullptr)
- {
- rotate_clockwise(*(subroot.southwest.get()));
- //Rotate the nodes
- std::swap(subroot.northwest, subroot.southeast);
- std::swap(subroot.northwest, subroot.southwest);
- std::swap(subroot.northwest, subroot.northeast);
- }
- //Traverse the southeast node
- if(subroot.southwest != nullptr)
- {
- rotate_clockwise(*(subroot.southeast.get()));
- //Rotate the nodes
- std::swap(subroot.northwest, subroot.southeast);
- std::swap(subroot.northwest, subroot.southwest);
- std::swap(subroot.northwest, subroot.northeast);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement