Convex Hull

Objective: Given a set of finite points, calculate the convex hole.

https://www.wikiwand.com/en/Convex_hull

Approach

• I took this problem head on without any research prior (bad). I had the idea in my head, and wanted to see if I could have worked out its implementation. I won't go into too much detail on how it worked (the code is heavily commentated on this process), but the central idea is to start will the lowest point, and start rotating a linear line about it until it find the next point of intersection. The process continues, jumping from point to point, until a full rotation is complete.

Results

• The algorithm had seemed to work in general. The points are properly identified, but there are cases were some points are overlooked because I was working explicitly with integers. So when this does happen, the results become somewhat scrabbled.

After Thoughts

• Great learning experience overall. I've learned more about the complications with integer programming, and interfacing with simple graph modules. I do however, regret the fact of not doing any research. There are TONS of information, and research about this topic like Graham's scan's algorithm incredibly more efficient and simpler.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <limits>
#include <math.h>
#include <array>
#include <random>
#include <functional>
#include <unordered_set>
#include <iomanip>
#include <time.h>

using namespace std;
inline void pause() { cin.ignore(numeric_limits<streamsize>::max(), '\n'); }

#define PI 3.14159

struct Point {
    Point() {};
    Point(unsigned short x_, unsigned short y_) 
    {
        x = x_; y = y_;
    }
    unsigned short x, y;

    void print()
    {
        cout << "(" << x << "," << y << ")";
    }

    bool operator==(const Point &other) const
    {
        return (x == other.x
            && y == other.y);
    }

    bool operator<(const Point &other) const
    {
        return (x < other.x);
    }
};

bool lowest_x(const Point &a, const Point &b)
{
    return a.y < b.y;
}

namespace std {
    template <>
    struct hash<Point>
    {
        std::size_t operator()(const Point& k) const
        {
            return (hash<unsigned short>()(k.x) ^ 
                (hash<unsigned short>()(k.y) << 1));
        }
    };
}

class Plane {
public:
    Plane() {};
    Plane(unsigned int x_width, unsigned int y_width) 
    {
        x_dim = x_width; 
        y_dim = y_width;
        grid = vector<vector<string>>(x_width, 
               vector<string>(y_width));

        // format bottom row
        for (int i = 0; i < x_width; i++) {
            grid[x_width - 1][i] = to_string(i);
        }

        // format left column
        for (int i = 0; i < y_width; i++) {
            grid[i][0] = to_string(y_width - i - 1);
        }

        // make everything else dots
        for (int row = 0; row < x_width - 1; row++) {
            for (int col = 1; col < y_width; col++) {
                grid[row][col] = ".";
            }
        }
        //print(); pause();
    }

    void add_random_points(const unsigned amount)
    {
        srand(time(nullptr));

        unsigned short x, y;
        for (int i = 0; i < amount; i++) {
            x = genRandX();
            y = genRandY();
            pts.emplace_back(x, y);
        }

        for (Point &p : pts) {
            plot(p, 0);
        }

        // add copy of points for fast processing
        for (Point &p : pts) {
            pts_cpy.insert(p);
        }

    }

    void plot(Point &p, bool clear)
    {
        if (clear) {
            grid[y_dim - p.y - 1][p.x] = ".";
        }
        else grid[y_dim - p.y - 1][p.x] = "*";
    }

    void print()
    {
        for (vector<string> s : grid) {
            for (string s2 : s) {
                cout << setw(2) << s2 << " ";
            }
            cout << endl;
        }
        cout << "\n\n";
    }

    vector<Point> findConvexHole()
    {
        // 1. Start with lowest X
        sort(pts.begin(), pts.end(), lowest_x);
        marked_points.insert(pts[0]);
        print_plotted_points();

        // 2. Find the next valid point
        // slope begins horizontally on bottom point ( = 0 )
        // first point begins with the bottom point

        Point cur_point = pts[0];
        convex_set.push_back(pts[0]);

        // once the current slope exceeds pi, then we know we've done a 
        // full rotation, and the convex hole is complete
        while (current_slope <= PI) {
            graphLine(current_slope, cur_point, x_dim, 1); 
            Point p = get_next_convex_point(current_slope, cur_point);

            // if a point is not found, increment the degree
            if (p.x == USHRT_MAX) current_slope += degree_precision;
            else convex_set.push_back(p);

            // current point will always be the most recent point 
            // added to the set.
            cur_point = convex_set[convex_set.size() - 1];
        }

        print_points(convex_set);
        return convex_set;
    }

private:
    double current_slope = 0;
    unsigned short x_dim, y_dim;
    vector<Point> pts;
    unordered_set<Point> pts_cpy;
    vector<Point> convex_set;

    vector<vector<string>> grid;

    // want to preserve order to suggest linkage of points
    unordered_set<Point> marked_points;
    double degree_precision = 0.01;

    Point get_next_convex_point(double prev_slope, Point &current_p) {
        /*
         we want to rotate about a point starting from the
         previous slope, and find the first point that contacts
         the line, that is also not in the set of marked points
         define line by calculating points along it
        */

        // look for points among the discrete x cordinates
        Point check_point = iterate_through_line(prev_slope, current_p, x_dim, 1);
        if (check_point.x != USHRT_MAX) return check_point;

        // look for points among the discrete y cordinates
        check_point = iterate_through_line(prev_slope, current_p, y_dim, 0);
        if (check_point.x != USHRT_MAX) return check_point;

        // otherwise no points have been located among the entire line
        return Point(USHRT_MAX, USHRT_MAX);
    }

    bool rotate_90 = false;
    Point iterate_through_line(double prev_slope, Point &current_p, unsigned short dimension, bool isXdim)
    {
        int f_x;
        Point check_point;
        // only focused on the first quadrant to simplify things

        // if we reach pi/2 then we've complete a 90 degree rotation, a complete vertical line is
        // impossible so we will instead iterate through all the points in the line, note
        // that our degree precision has to be precise enough to detect this

        if (prev_slope >= PI/2 && !rotate_90) {
            for (int y = 0; y < y_dim; y++) {
                check_point.x = current_p.x;
                check_point.y = y;

                if (pts_cpy.find(check_point) != pts_cpy.end() 
                    && marked_points.find(check_point) == marked_points.end()) {
                    marked_points.insert(check_point);
                    rotate_90 = true;
                    return check_point;
                }
            }
            // only do once
            rotate_90 = true;
        }
        else {
            for (double x = 0; x < dimension - 1; x++) {
                // generate point, slope intercept form y - y_1 = m(x - x1)
                if (isXdim) {
                    // solving for y given x increments
                    f_x = (tanf(prev_slope) * (x - current_p.x)) + current_p.y;
                    check_point.x = x;
                    check_point.y = f_x;
                }
                else {
                    // solving for x given y increments; switch x = f_x, and f_x = x;
                    f_x = current_p.x + ((x * current_p.y) / (tanf(prev_slope)));
                    check_point.x = f_x;
                    check_point.y = x;
                }
                // if this point exists in all the set of points and is unmarked
                if (pts_cpy.find(check_point) != pts_cpy.end() &&
                    marked_points.find(check_point) == marked_points.end()) {
                    // add to the set of marked points
                    marked_points.insert(check_point);
                    // return the next valid point
                    return check_point;
                }
                // otherwise, check the next point in the line
            }
        }


        // no point was found along the line
        return Point(USHRT_MAX, USHRT_MAX);
    }

    void graphLine(double prev_slope, Point &current_p, unsigned short dimension, bool isXdim) 
    {
        int f_x;
        Point check_point;
        vector<Point> plottedPoints;
        for (double x = 0; x < dimension - 1; x++) {
            if (isXdim) {
                f_x = (tanf(prev_slope) * (x - current_p.x)) + current_p.y;
                if (x > 0 && f_x > 0 && f_x < y_dim && x < x_dim) {
                    check_point.x = x;
                    check_point.y = f_x;
                    plot(check_point, 0);
                    plottedPoints.push_back(check_point);
                }
            }
            else {
                f_x = current_p.x + ((x * current_p.y) / (tanf(prev_slope)));
                if (f_x > 0 && x > 0 && f_x < y_dim && x < x_dim) {
                    check_point.x = f_x;
                    check_point.y = x;
                    plot(check_point, 0);
                    plottedPoints.push_back(check_point);
                }
            }
        }
        //print(); //pause();

        // clear line 
        for (Point &p : plottedPoints) {
            plot(p, 1);
        }
        // some points may have been cleared with overlap
        for (Point &p : pts) {
            plot(p, 0);
        }
    }

    unsigned short genRandX() 
    {
        return rand() % (x_dim - 2);
    }

    unsigned short genRandY()
    {
        return rand() % (y_dim - 1) + 1;
    }

    void print_plotted_points() 
    {
        for (Point &p : pts) {
            p.print();
            cout << ", ";
        }
        cout << endl;
    }

    void print_points(vector<Point> &pts)
    {
        for (Point &p : pts) {
            p.print();
            cout << ", ";
        }
        cout << endl;
    }
};

int main()
{
    Plane p(30, 30);
    p.add_random_points(20);

    p.print();
    vector<Point> convex_set = p.findConvexHole();

    pause();

}