computer_graphics/convex_hull.cpp at master · ypldan/computer_graphics · 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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include "convex_hull.h"

int findSide(QPoint p1, QPoint p2, QPoint p) {
    int val = (p.y() - p1.y()) * (p2.x() - p1.x()) -
              (p2.y() - p1.y()) * (p.x() - p1.x());

    if (val > 0)
        return 1;
    if (val < 0)
        return -1;
    return 0;
}

int lineDist(QPoint p1, QPoint p2, QPoint p) {
    return abs ((p.y() - p1.y()) * (p2.x() - p1.x()) -
               (p2.y() - p1.y()) * (p.x() - p1.x()));
}

void quickHull(QVector<QPoint> a, int n, QPoint p1, QPoint p2, int side, QSet<QPoint> &hull)
{
    int ind = -1;
    int max_dist = 0;

    // finding the point with maximum distance
    // from L and also on the specified side of L.
    for (int i=0; i<n; i++)
    {
        int temp = lineDist(p1, p2, a[i]);
        if (findSide(p1, p2, a[i]) == side && temp > max_dist)
        {
            ind = i;
            max_dist = temp;
        }
    }

    // If no point is found, add the end points
    // of L to the convex hull.
    if (ind == -1)
    {
        hull.insert(p1);
        hull.insert(p2);
        return;
    }

    // Recur for the two parts divided by a[ind]
    quickHull(a, n, a[ind], p1, -findSide(a[ind], p1, p2), hull);
    quickHull(a, n, a[ind], p2, -findSide(a[ind], p2, p1), hull);
}

QVector<QPoint> getHull(QVector<QPoint> points)
{
    // a[i].y() -> y-coordinate of the ith point

    // Finding the point with minimum and
    // maximum x-coordinate
    int n = points.size();
    int min_x = 0, max_x = 0;
    int min_y = 0, max_y = 0;
    for (int i=1; i<n; i++)
    {
        if (points[i].x() < points[min_x].x() || (points[i].x() == points[min_x].x() && points[i].y() < points[min_x].y())) {
            min_x = i;
        }
        if (points[i].x() > points[max_x].x() || (points[i].x() == points[min_x].x() && points[i].y() < points[max_x].y())) {
            max_x = i;
        }
        if (points[i].y() < points[min_y].y()) {
            min_y = i;
        }
        if (points[i].y() > points[max_y].y()) {
            max_y = i;
        }
    }

    qInfo() << points[max_x] << " " << points[min_x];

    QSet<QPoint> up, down;

    // Recursively find convex hull points on
    // one side of line joining a[min_x] and
    // a[max_x]
    quickHull(points, n, points[min_x], points[max_x], 1, up);
    auto upList = up.toList();
    std::sort(upList.begin(), upList.end(), [&points, &max_y](const QPoint& a, const QPoint& b) {
        if (a.x() < b.x()) {
            return true;
        } else if (a.x() > b.x()) {
            return false;
        } else if (a.x() == b.x()) {
            if (a.x() <= points[max_y].x() && b.x() >= points[max_y].x()) {
                return true;
            } else if (a.x() >= points[max_y].x() && b.x() <= points[max_y].x()) {
                return false;
            } else if (a.x() >= points[max_y].x() && b.x() >= points[max_y].x()) {
                return a.y() > b.y();
            } else if (a.x() <= points[max_y].x() && b.x() <= points[max_y].x()) {
                return a.y() < b.y();
            }
        }
        qWarning() << "UNEXPECTED: " << a << " " << b;
        return true;
    });

    // Recursively find convex hull points on
    // other side of line joining a[min_x] and
    // a[max_x]
    quickHull(points, n, points[min_x], points[max_x], -1, down);
    auto downList = down.toList();
    std::sort(downList.begin(), downList.end(), [&points, &min_y](const QPoint& a, const QPoint& b) {
        if (a.x() > b.x()) {
            return true;
        } else if (a.x() < b.x()) {
            return false;
        } else if (a.x() == b.x()) {
            if (a.x() <= points[min_y].x() && b.x() >= points[min_y].x()) {
                return false;
            } else if (a.x() >= points[min_y].x() && b.x() <= points[min_y].x()) {
                return true;
            } else if (a.x() >= points[min_y].x() && b.x() >= points[min_y].x()) {
                return a.y() < b.y();
            } else if (a.x() <= points[min_y].x() && b.x() <= points[min_y].x()) {
                return a.y() > b.y();
            }
        }
        qWarning() << "UNEXPECTED: " << a << " " << b;
        return true;
    });
    QVector<QPoint> result;
    qInfo() << "up:";
    for (auto p: upList) {
        result.push_back(p);
        qInfo() << p;
    }
    qInfo() << "down:";
    for (auto p: downList) {
        result.push_back(p);
        qInfo() << p;
    }
//    for (auto p: result) {
//        qInfo() << p;
//    }
    return result;
}