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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
|
#pragma once
#include "geometry/robust_orientation.hpp"
#include "base/assert.hpp"
#include "base/base.hpp"
#include "base/math.hpp"
#include "base/stl_add.hpp"
#include "std/iterator.hpp"
template <typename IsVisibleF>
bool FindSingleStripForIndex(size_t i, size_t n, IsVisibleF isVisible)
{
// Searching for a strip only in a single direction, because the opposite direction
// is traversed from the last vertex of the possible strip.
size_t a = my::PrevModN(i, n);
size_t b = my::NextModN(i, n);
for (size_t j = 2; j < n; ++j)
{
ASSERT_NOT_EQUAL ( a, b, () );
if (!isVisible(a, b))
return false;
if (j & 1)
a = my::PrevModN(a, n);
else
b = my::NextModN(b, n);
}
ASSERT_EQUAL ( a, b, () );
return true;
}
// If polygon with n vertices is a single strip, return the start index of the strip or n otherwise.
template <typename IsVisibleF>
size_t FindSingleStrip(size_t n, IsVisibleF isVisible)
{
for (size_t i = 0; i < n; ++i)
{
if (FindSingleStripForIndex(i, n, isVisible))
return i;
}
return n;
}
#ifdef DEBUG
template <typename IterT> bool TestPolygonPreconditions(IterT beg, IterT end)
{
ASSERT_GREATER ( distance(beg, end), 2, () );
ASSERT ( !AlmostEqualULPs(*beg, *(--end)), () );
return true;
}
#endif
/// Is polygon [beg, end) has CCW orientation.
template <typename IterT> bool IsPolygonCCW(IterT beg, IterT end)
{
ASSERT ( TestPolygonPreconditions(beg, end), () );
// find the most down (left) point
double minY = numeric_limits<double>::max();
IterT iRes;
for (IterT i = beg; i != end; ++i)
{
if ((*i).y < minY || ((*i).y == minY && (*i).x < (*iRes).x))
{
iRes = i;
minY = (*i).y;
}
}
double cp = m2::robust::OrientedS(*PrevIterInCycle(iRes, beg, end), *iRes,
*NextIterInCycle(iRes, beg, end));
if (cp != 0.0)
return (cp > 0.0);
// find the most up (left) point
double maxY = numeric_limits<double>::min();
for (IterT i = beg; i != end; ++i)
{
if ((*i).y > maxY || ((*i).y == maxY && (*i).x < (*iRes).x))
{
iRes = i;
maxY = (*i).y;
}
}
IterT iPrev = PrevIterInCycle(iRes, beg, end);
IterT iNext = NextIterInCycle(iRes, beg, end);
cp = m2::robust::OrientedS(*iPrev, *iRes, *iNext);
ASSERT_NOT_EQUAL(cp, 0.0, (*iPrev, *iRes, *iNext));
return (cp > 0.0);
}
/// Is diagonal (i0, i1) visible in polygon [beg, end).
/// @precondition Orientation CCW!!
template <typename IterT>
bool IsDiagonalVisible(IterT beg, IterT end, IterT i0, IterT i1)
{
ASSERT ( IsPolygonCCW(beg, end), () );
ASSERT ( TestPolygonPreconditions(beg, end), () );
ASSERT ( i0 != i1, () );
IterT const prev = PrevIterInCycle(i0, beg, end);
IterT const next = NextIterInCycle(i0, beg, end);
if (prev == i1 || next == i1)
return true;
if (!m2::robust::IsSegmentInCone(*i0, *i1, *prev, *next))
return false;
for (IterT j0 = beg, j1 = PrevIterInCycle(beg, beg, end); j0 != end; j1 = j0++)
if (j0 != i0 && j0 != i1 && j1 != i0 && j1 != i1 && m2::robust::SegmentsIntersect(*i0, *i1, *j0, *j1))
return false;
return true;
}
template <typename IterT> class IsDiagonalVisibleFunctor
{
IterT m_Beg, m_End;
public:
IsDiagonalVisibleFunctor(IterT beg, IterT end) : m_Beg(beg), m_End(end) {}
bool operator () (size_t a, size_t b) const
{
return IsDiagonalVisible(m_Beg, m_End, m_Beg + a, m_Beg + b);
}
};
namespace detail
{
template <typename F> class StripEmitter
{
F & m_f;
int m_order;
public:
StripEmitter(F & f) : m_f(f), m_order(0) {}
bool operator () (size_t a, size_t b)
{
if (m_order == 0)
{
m_f(b);
m_f(a);
m_order = 1;
}
else
{
m_f(m_order == 1 ? b : a);
m_order = -m_order;
}
return true;
}
};
}
/// Make single strip for the range of points [beg, end), started with index = i.
template <typename F>
void MakeSingleStripFromIndex(size_t i, size_t n, F f)
{
ASSERT_LESS ( i, n, () );
f(i);
FindSingleStripForIndex(i, n, detail::StripEmitter<F>(f));
}
template <class TIter> double GetPolygonArea(TIter beg, TIter end)
{
double area = 0.0;
TIter curr = beg;
while (curr != end)
{
TIter next = NextIterInCycle(curr, beg, end);
area += ((*curr).x * (*next).y - (*curr).y * (*next).x);
++curr;
}
return 0.5 * fabs(area);
}
|
