-
Notifications
You must be signed in to change notification settings - Fork 9
/
PolyUtils.h
126 lines (109 loc) · 2.75 KB
/
PolyUtils.h
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
#pragma once
#include <vector>
/**
* All of necessary data structures are defined here
*/
namespace PolyClip
{
struct Point2d
{
float x_, y_;
Point2d():x_(0.0),y_(0.0){}
Point2d(float x,float y):x_(x),y_(y){}
};
struct Vertex
{
float x_, y_;
Vertex * next_;
Vertex * prev_;
bool intersect_;
bool entryExit_;
Vertex * neighbour_;
float alpha_;
bool processd;
Vertex()
:x_(0.0),y_(0.0), alpha_(0.0),next_(nullptr), prev_(nullptr),neighbour_(nullptr), intersect_(false), entryExit_(false),processd(false)
{}
Vertex(const Point2d& p)
:x_(p.x_),y_(p.y_), alpha_(0.0), next_(nullptr), prev_(nullptr), neighbour_(nullptr), intersect_(false), entryExit_(false), processd(false)
{}
Vertex(float x, float y)
:x_(x), y_(y), alpha_(0.0), next_(nullptr), prev_(nullptr), neighbour_(nullptr), intersect_(false), entryExit_(false), processd(false)
{}
};
// This object is used for sort insection vertices so that we can insert these at correct order
struct VertexPtrDistance
{
Vertex * ptr;
float distance;
VertexPtrDistance(Vertex* vPtr, float dis):ptr(vPtr),distance(dis){}
};
struct SortVertexPtrDistance
{
bool operator()(const VertexPtrDistance& v1, const VertexPtrDistance& v2)
{
return v1.distance < v2.distance;
}
};
class PolygonVertexIterator
{
public:
PolygonVertexIterator(Vertex * cv, int visitedCount) :currentVertex_(cv), visitedCount_(visitedCount) {};
PolygonVertexIterator operator++()
{
visitedCount_++;
currentVertex_ = currentVertex_->next_;
return *this;
}
PolygonVertexIterator operator--()
{
visitedCount_--;
currentVertex_ = currentVertex_->prev_;
return *this;
}
Vertex& operator*()
{
return *currentVertex_;
}
bool operator!=(const PolygonVertexIterator& p)
{
return abs(visitedCount_) != abs(p.visitedCount_);
}
Vertex* eval() { return currentVertex_; }
PolygonVertexIterator next()
{
PolygonVertexIterator nextIter = *this;
return ++nextIter;
}
private:
Vertex * currentVertex_;
int visitedCount_;
};
class Utils
{
public:
// Shoelace formula.
// The area formula is valid for any non-self-intersecting (simple) polygon, which can be convex or concave.
// See https://en.wikipedia.org/wiki/Shoelace_formula
// Input: polygon vertices (ordered), it should equal to the number of edges
// Output: the area.
static float CalculatePolygonArea(const std::vector<Point2d>& polygon)
{
float a = 0.0, b = 0.0;
for (int i=0;i<polygon.size();++i)
{
if (i == polygon.size() - 1)
{
a += polygon[i].x_*polygon[0].y_;
b += polygon[0].x_*polygon[i].y_;
}
else
{
a += polygon[i].x_*polygon[i + 1].y_;
b += polygon[i + 1].x_*polygon[i].y_;
}
}
return abs((a - b) / 2);
}
};
}