quickhull/Quickhull.h

#ifndef QUICKHULL_H
#define QUICKHULL_H

#include <list>
#include <limits.h>
#include <chrono>
#include <iostream>

#include "Display.h"
#include "Triangle.h"
#include "Utility.h"  // For IsPointInRectangle

class Quickhull
{
public:
    static void get_hull(std::list<Point> &input, std::list<Point> &output, bool akl)
    {
        // Get leftmost and rightmost point
        Point leftmost(INFINITY, 0.0), rightmost(-INFINITY, 0.0);

        if (akl)
        {
            // Also get highest and lowest point
            Point lowest(0.0, -INFINITY), highest(0.0, INFINITY);

            for (const Point &point : input)
            {
                if (point.x() < leftmost.x()) {
                    leftmost = point;
                } else if (point.x() > rightmost.x()) {
                    rightmost = point;
                }

                if (point.y() < highest.y()) {
                    highest = point;
                } else if (point.y() > lowest.y()) {
                    lowest = point;
                }
            }

            Triangle t1(highest, rightmost, lowest);
            Triangle t2(lowest, leftmost, highest);

            // Remove all points in this rectangle
            input.remove_if([highest, leftmost, lowest, rightmost](const Point &point)
            {
                return IsPointInRectangle(point, highest, leftmost, lowest, rightmost);
            });

            output.emplace_back(leftmost);
            output.emplace_back(rightmost);
            output.emplace_back(highest);
            output.emplace_back(lowest);
        } else {
            for (const Point &point : input)
            {
                if (point.x() < leftmost.x()) {
                    leftmost = point;
                } else if (point.x() > rightmost.x()) {
                    rightmost = point;
                }
            }
            // Add them to the output
            output.emplace_back(leftmost);
            output.emplace_back(rightmost);

            // Remove them from the input (as well as duplicates)
            input.remove(leftmost);
            input.remove(rightmost);
        }

        // Create a line from leftmost to rightmost
        Line line = Line(leftmost, rightmost);

        // Sort points between left and right of that line
        std::list<Point> points_left, points_right;

        for (const Point &point : input)
        {
            if (line.is_point_right(point))
            {
                points_right.emplace_back(point);
            }
            else
            {
                points_left.emplace_back(point);
            }
        }

        // Call get_hull_with_line with the left points, as well as with the right points, and the line
        get_hull_with_line(points_left, output, line);
        get_hull_with_line(points_right, output, line);
    }
    
    static void show (std::list<Point> &points, std::list<Point>& hull)
    {
        // showing points in window after calculation
        // create the window
        sf::RenderWindow window(sf::VideoMode(WIDTH, HEIGHT), "ALGO Prog2: Quickhull - performance");

        sf::CircleShape normal_p(2);
        normal_p.setFillColor(sf::Color(250, 250, 250));

        sf::CircleShape hull_p(2);
        hull_p.setFillColor(sf::Color(250, 100, 50));

        // run the program as long as the window is open
        while (window.isOpen())
        {
            // check all the window's events that were triggered since the last iteration of the loop
            sf::Event event;
            while (window.pollEvent(event))
            {
                // "close requested" event: we close the window
                if (event.type == sf::Event::Closed)
                    window.close();
            }

            // clear the window with black color
            window.clear(sf::Color::Black);

            // Draw all points
            for (const Point& point : points)
            {
                normal_p.setPosition(point.x(), point.y());
                window.draw(normal_p);
            }

            // Draw hull points
            for (const Point& point : hull)
            {
                hull_p.setPosition(point.x(), point.y());
                window.draw(hull_p);
            }

            // end the current frame
            window.display();
        }
    }

private:
    static void get_hull_with_line(std::list<Point> &input, std::list<Point> &output, const Line &line)
    {
        // If the input vector is empty, we're done
        if (input.empty()) return;

        // Find the point which is furthest away from the line, add it to the output
        Point furthest_point;
        float furthest_distance = -1.0;

        for (const Point &point : input)
        {
            float this_distance = line.distance_squared_to(point);
            if (this_distance > furthest_distance)
            {
                furthest_distance = this_distance;
                furthest_point = point;
            }
        }

        // This seems unnecessarily complicated, but it actually yielded the best results,
        //  especially when the rectangle edge case is taken into account.
        for (const Point &point : input)
        {
            float this_distance = line.distance_squared_to(point);
            if (this_distance == furthest_distance)
            {
                output.emplace_back(point);
            }
        }
        // Remove the previously checked points from the input -- we can't do that in
        //  the previous loop because we can't delete from the list we're iterating over
        input.remove_if([furthest_distance, line](Point point)
        {
            return furthest_distance == line.distance_squared_to(point);
        });

        output.emplace_back(furthest_point);

        // Build a triangle with these 3 points

        // We need to differentiate based on which side the furthest point is on
        //  in order to keep the meaning of left/right consistent.
        
        Line new_line1, new_line2;

        if (line.is_point_right(furthest_point))
        {
            new_line1 = Line(line.to(), furthest_point);
            new_line2 = Line(furthest_point, line.from());
        }
        else
        {
            new_line1 = Line(line.from(), furthest_point);
            new_line2 = Line(furthest_point, line.to());
        }

        // We don't need to remove points inside the triangle created by those lines.
        //  That happens implicitly since they are not handled further due to the
        //  following step, which assigns each line its corresponding points to handle:

        // Get points right of new_line1 and 2
        std::list<Point> left_of_line1, left_of_line2;

        for (const Point& point : input)
        {
            if (!new_line1.is_point_right(point))
            {
                left_of_line1.emplace_back(point);
            }
            // TODO: Are there any possible edge cases where this 'else if' won't work,
            //  and we need an 'if' instead?
            else if (!new_line2.is_point_right(point))
            {
                left_of_line2.emplace_back(point);
            }
        }

        // Recursively call get_hull_with_line for each side of the triangle
        get_hull_with_line(left_of_line1, output, new_line1);
        get_hull_with_line(left_of_line2, output, new_line2);
    }
};
#endif // QUICKHULL_H