GeometricDataStructures2D/ConvexHullChansAlgorithm.cpp at main · srikarC03/GeometricDataStructures2D · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include "ConvexHullChansAlgorithm.h"
#include "Utilities.h"
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;


Number angleFactor(SimplePoint2D sp)
{
    if (sp.x == Number("0") && sp.y == Number("0"))
        return Number("2");     // the origin is always first
    return sp.x.sign() * (sp.x.square() / (sp.x.square() + sp.y.square()));
}

// from Grahamscan(Richard)
bool angularCompareFunc(SimplePoint2D p1, SimplePoint2D p2)
{

    Number a1 = angleFactor(p1);
    Number a2 = angleFactor(p2);
    SimplePoint2D origin = SimplePoint2D(Number("0"), Number("0"));\

    if (a1 != a2)
        return a1 > a2;
    else
        return distSquared(origin, p1) > distSquared(origin, p2);
}

vector<SimplePoint2D> arrangeHull(vector<SimplePoint2D> points)
{
    vector<SimplePoint2D> hull;
    int min = 0;
    for(int i=0; i<points.size(); i++){

    }
}

vector<SimplePoint2D> internalGrahamScan(vector<SimplePoint2D> pointset, int start, int end)
{
    vector<SimplePoint2D> points(&pointset[start],&pointset[end]);

    if (points.size() <= 3)
        return points;

    SimplePoint2D p0 = points[0];
    for (SimplePoint2D p : points) {
        if ((p.y < p0.y) || (p.y == p0.y && p.x < p0.x))
            p0 = p;
    }

    // This is a lambda expression. It will be used by std::sort to order the points.
    // A lambda function is needed here because the ordering is dependent on p0.
    auto comp = [p0](SimplePoint2D p1, SimplePoint2D p2) {
        return angularCompareFunc(relativeCoord(p0, p1), relativeCoord(p0, p2));
    };

    // Sort points by polar angle with p0
    sort(points.begin(), points.end(), comp);

    vector<SimplePoint2D> stack;
    for (SimplePoint2D p : points) {
        while (stack.size() > 1 && isCounterClockwiseTurn(stack[stack.size()-2], stack.back(), p) <= 0) {
            stack.pop_back();
        }
        stack.push_back(p);
    }

    return stack;

}

pair<bool,vector<SimplePoint2D>> partialHull(vector<SimplePoint2D> points, int m){
    int k = ceil(points.size() / m);
    vector<vector<SimplePoint2D>> subHulls;
    int start;
    int end;
    for(int i=0; i<k; i++){
        start = i*m;
        end = i*m + m;
        if(end > points.size()){end = points.size();}
        subHulls[i] = internalGrahamScan(points,start,end);
    }

}

Region2D ConvexHullChansAlgorithm(Point2D pointset)
{
    bool done = false;
    vector<SimplePoint2D> points;
    vector<SimplePoint2D> hull;
    pair<bool, vector<SimplePoint2D>> partial;

    for(Point2D::Iterator itr = pointset.begin(); itr != pointset.end(); itr++)
    {
        points.push_back(*itr);
    }

    if(points.size() < 3){
        return Region2D();
    }
    else if(points.size() == 3){
        return Region2D(pointsToSegments(points));
    }
    else{
        int count = 1;
        int m;
        while(!done)
        {
            m = min((int)pow(2,pow(2,count)), (int)points.size());
            partial = partialHull(points,m);
            if(partial.first){
                done = true;
            }
            count++;
        }
    }
    hull = partial.second;
    return Region2D(pointsToSegments(hull));
}