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 ¤t_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 ¤t_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 ¤t_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();
}Last updated