mobb/polygon.cpp at master · jojva/mobb · 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
#include <algorithm>
#include <fstream>

#include "polygon.h"

Point::Point()
    : Point(0.0, 0.0)
{
}

Point::Point(float x, float y)
    : mX(x)
    , mY(y)
{
}

bool Point::IsOnTheLeftOf(const Point& p) const
{
    return mX < p.mX;
}

bool Point::IsOnTheLeftOf(const Point& p, const Point& q) const
{
    // Cross-product
    return ((mY - p.mY) * (q.mX - mX) - (mX - p.mX) * (q.mY - mY)) < 0;
}

std::string Point::ToString()
{
    std::ostringstream oss;
    oss << "[" << mX << " , " << mY << "]";
    return oss.str();
}

void Polygon::readInput(char* filename)
{
    std::ifstream input;
    input.open(filename);
    mPoints.clear();
    while(!input.eof())
    {
        float x, y;
        input >> x >> y;
        mPoints.push_back(Point(x, y));
    }
    input.close();
}

Polygon Polygon::ConvexHull() const
{
    // Gift-wrapping algorithm
    if(mPoints.size() < 3)
    {
        return Polygon();
    }
    Point leftmostPoint = mPoints.front();
    for(auto point : mPoints)
    {
        if(point.IsOnTheLeftOf(leftmostPoint))
        {
            leftmostPoint = point;
        }
    }
    Polygon convexHull;
    Point currentHullPoint = leftmostPoint;
    do
    {
        Point nextHullPoint;
        convexHull.mPoints.push_back(currentHullPoint);
        auto NextHullPointIt = std::find(mPoints.begin(), mPoints.end(), currentHullPoint);
        NextHullPointIt++;
        if(NextHullPointIt != mPoints.end())
        {
            nextHullPoint = *(NextHullPointIt);
        }
        else
        {
            nextHullPoint = mPoints.front();
        }
        for(auto candidateHullPoint : mPoints)
        {
            if(candidateHullPoint.IsOnTheLeftOf(currentHullPoint, nextHullPoint))
            {
                nextHullPoint = candidateHullPoint;
            }
        }
        currentHullPoint = nextHullPoint;
    } while(currentHullPoint != leftmostPoint);
    return convexHull;
}

std::string Polygon::ToString() const
{
    std::ostringstream oss;
    for(auto point : mPoints)
    {
        oss << point.ToString() << std::endl;
    }
    return oss.str();
}