src/mapbox/earcut.hpp

filter: Statementstmt 53.2% 206 / 387 Branchbran 34.8% 108 / 310 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 45.0% 314 / 697 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« xsi/WKBWriter.xsi ↑ Summary xsi/MultiPoint.xsi »
1 #pragma once
2  
3 #include <algorithm>
4 #include <cassert>
5 #include <cmath>
6 #include <memory>
7 #include <vector>
8  
9 namespace mapbox {
10  
11 namespace util {
12  
13 template <std::size_t I, typename T> struct nth {
14 inline static typename std::tuple_element<I, T>::type
15 get(const T& t) { return std::get<I>(t); };
16 };
17  
18 }
19  
20 namespace detail {
21  
22 template <typename N = uint32_t>
23 class Earcut {
24 public:
25 std::vector<N> indices;
26 std::size_t vertices = 0;
27  
28 template <typename Polygon>
29 void operator()(const Polygon& points);
30  
31 private:
32 struct Node {
33 10 Node(N index, double x_, double y_) : i(index), x(x_), y(y_) {}
34 Node(const Node&) = delete;
35 Node& operator=(const Node&) = delete;
36 Node(Node&&) = delete;
37 Node& operator=(Node&&) = delete;
38  
39 const N i;
40 const double x;
41 const double y;
42  
43 // previous and next vertice nodes in a polygon ring
44 Node* prev = nullptr;
45 Node* next = nullptr;
46  
47 // z-order curve value
48 int32_t z = 0;
49  
50 // previous and next nodes in z-order
51 Node* prevZ = nullptr;
52 Node* nextZ = nullptr;
53  
54 // indicates whether this is a steiner point
55 bool steiner = false;
56 };
57  
58 template <typename Ring> Node* linkedList(const Ring& points, const bool clockwise);
59 Node* filterPoints(Node* start, Node* end = nullptr);
60 void earcutLinked(Node* ear, int pass = 0);
61 bool isEar(Node* ear);
62 bool isEarHashed(Node* ear);
63 Node* cureLocalIntersections(Node* start);
64 void splitEarcut(Node* start);
65 template <typename Polygon> Node* eliminateHoles(const Polygon& points, Node* outerNode);
66 void eliminateHole(Node* hole, Node* outerNode);
67 Node* findHoleBridge(Node* hole, Node* outerNode);
68 void indexCurve(Node* start);
69 Node* sortLinked(Node* list);
70 int32_t zOrder(const double x_, const double y_);
71 Node* getLeftmost(Node* start);
72 bool pointInTriangle(double ax, double ay, double bx, double by, double cx, double cy, double px, double py) const;
73 bool isValidDiagonal(Node* a, Node* b);
74 double area(const Node* p, const Node* q, const Node* r) const;
75 bool equals(const Node* p1, const Node* p2);
76 bool intersects(const Node* p1, const Node* q1, const Node* p2, const Node* q2);
77 bool intersectsPolygon(const Node* a, const Node* b);
78 bool locallyInside(const Node* a, const Node* b);
79 bool middleInside(const Node* a, const Node* b);
80 Node* splitPolygon(Node* a, Node* b);
81 template <typename Point> Node* insertNode(std::size_t i, const Point& p, Node* last);
82 void removeNode(Node* p);
83  
84 bool hashing;
85 double minX, maxX;
86 double minY, maxY;
87 double inv_size = 0;
88  
89 template <typename T, typename Alloc = std::allocator<T>>
90 class ObjectPool {
91 public:
92 1 ObjectPool() { }
93 ObjectPool(std::size_t blockSize_) {
94 reset(blockSize_);
95 }
96 1 ~ObjectPool() {
97 1 clear();
98 1 }
99 template <typename... Args>
100 10 T* construct(Args&&... args) {
101 10 ▶ if (currentIndex >= blockSize) {
Branch: 2 branches
BranchTrueFalseTotal
if (currentIndex >= blockSize) { 0 2 2
if (currentIndex >= blockSize) { 1 7 8
102 0 currentBlock = alloc.allocate(blockSize);
103 0 allocations.emplace_back(currentBlock);
104 0 currentIndex = 0;
105 }
106 10 T* object = &currentBlock[currentIndex++];
107 10 alloc.construct(object, std::forward<Args>(args)...);
108 10 return object;
109 }
110 3 void reset(std::size_t newBlockSize) {
111 4 ▶ for (auto allocation : allocations) alloc.deallocate(allocation, blockSize);
Branch: 1 branch
BranchTrueFalseTotal
for (auto allocation : allocations) alloc.deallocate(allocation, blockSize); 1 3 4
112 3 allocations.clear();
113 3 blockSize = std::max<std::size_t>(1, newBlockSize);
114 3 currentBlock = nullptr;
115 3 currentIndex = blockSize;
116 3 }
117 2 void clear() { reset(blockSize); }
118 private:
119 T* currentBlock = nullptr;
120 std::size_t currentIndex = 1;
121 std::size_t blockSize = 1;
122 std::vector<T*> allocations;
123 Alloc alloc;
124 };
125 ObjectPool<Node> nodes;
126 };
127  
128 template <typename N> template <typename Polygon>
129 1 void Earcut<N>::operator()(const Polygon& points) {
130 // reset
131 1 indices.clear();
132 1 vertices = 0;
133  
134 1 ▶ if (points.empty()) return;
Branch: 1 branch
BranchTrueFalseTotal
if (points.empty()) return; 0 1 1
135  
136 double x;
137 double y;
138 1 int threshold = 80;
139 1 std::size_t len = 0;
140  
141 3 ▶ for (size_t i = 0; threshold >= 0 && i < points.size(); i++) {
Branch: 3 branches
BranchTrueFalseTotal
for (size_t i = 0; threshold >= 0 && i < points.size(); i++) { 3 0 3
for (size_t i = 0; threshold >= 0 && i < points.size(); i++) { 2 1 3
for (size_t i = 0; threshold >= 0 && i < points.size(); i++) { 2 1 3
142 2 threshold -= static_cast<int>(points[i].size());
143 2 len += points[i].size();
144 }
145  
146 //estimate size of nodes and indices
147 1 ▶ nodes.reset(len * 3 / 2);
Branch: 1 branch
BranchTrueFalseTotal
nodes.reset(len * 3 / 2); 1 0 1
148 1 ▶ indices.reserve(len + points[0].size());
Branch: 1 branch
BranchTrueFalseTotal
indices.reserve(len + points[0].size()); 1 0 1
149  
150 1 ▶ Node* outerNode = linkedList(points[0], true);
Branch: 1 branch
BranchTrueFalseTotal
Node* outerNode = linkedList(points[0], true); 1 0 1
151 1 ▶ if (!outerNode) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!outerNode) return; 0 1 1
152  
153 1 ▶ if (points.size() > 1) outerNode = eliminateHoles(points, outerNode);
Branch: 2 branches
BranchTrueFalseTotal
if (points.size() > 1) outerNode = eliminateHoles(points, outerNode); 1 0 1
if (points.size() > 1) outerNode = eliminateHoles(points, outerNode); 1 0 1
154  
155 // if the shape is not too simple, we'll use z-order curve hash later; calculate polygon bbox
156 1 hashing = threshold < 0;
157 1 ▶ if (hashing) {
Branch: 1 branch
BranchTrueFalseTotal
if (hashing) { 0 1 1
158 0 Node* p = outerNode->next;
159 0 minX = maxX = p->x;
160 0 minY = maxY = p->y;
161 do {
162 0 x = p->x;
163 0 y = p->y;
164 0 minX = std::min<double>(minX, x);
165 0 minY = std::min<double>(minY, y);
166 0 maxX = std::max<double>(maxX, x);
167 0 maxY = std::max<double>(maxY, y);
168 0 p = p->next;
169 0 ▶ } while (p != outerNode);
Branch: 1 branch
BranchTrueFalseTotal
} while (p != outerNode); 0 0 0
170  
171 // minX, minY and size are later used to transform coords into integers for z-order calculation
172 0 inv_size = std::max<double>(maxX - minX, maxY - minY);
173 0 ▶ inv_size = inv_size != .0 ? (1. / inv_size) : .0;
Branch: 1 branch
BranchTrueFalseTotal
inv_size = inv_size != .0 ? (1. / inv_size) : .0; 0 0 0
174 }
175  
176 1 ▶ earcutLinked(outerNode);
Branch: 1 branch
BranchTrueFalseTotal
earcutLinked(outerNode); 1 0 1
177  
178 1 ▶ nodes.clear();
Branch: 1 branch
BranchTrueFalseTotal
nodes.clear(); 1 0 1
179 }
180  
181 // create a circular doubly linked list from polygon points in the specified winding order
182 template <typename N> template <typename Ring>
183 typename Earcut<N>::Node*
184 2 Earcut<N>::linkedList(const Ring& points, const bool clockwise) {
185 using Point = typename Ring::value_type;
186 2 double sum = 0;
187 2 const std::size_t len = points.size();
188 std::size_t i, j;
189 2 Node* last = nullptr;
190  
191 // calculate original winding order of a polygon ring
192 10 ▶ for (i = 0, j = len > 0 ? len - 1 : 0; i < len; j = i++) {
Branch: 2 branches
BranchTrueFalseTotal
for (i = 0, j = len > 0 ? len - 1 : 0; i < len; j = i++) { 2 0 2
for (i = 0, j = len > 0 ? len - 1 : 0; i < len; j = i++) { 8 2 10
193 8 const auto& p1 = points[i];
194 8 const auto& p2 = points[j];
195 8 const double p20 = util::nth<0, Point>::get(p2);
196 8 const double p10 = util::nth<0, Point>::get(p1);
197 8 const double p11 = util::nth<1, Point>::get(p1);
198 8 const double p21 = util::nth<1, Point>::get(p2);
199 8 sum += (p20 - p10) * (p11 + p21);
200 }
201  
202 // link points into circular doubly-linked list in the specified winding order
203 2 ▶ if (clockwise == (sum > 0)) {
Branch: 1 branch
BranchTrueFalseTotal
if (clockwise == (sum > 0)) { 1 1 2
204 5 ▶ for (i = 0; i < len; i++) last = insertNode(vertices + i, points[i], last);
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < len; i++) last = insertNode(vertices + i, points[i], last); 4 1 5
205 } else {
206 5 ▶ for (i = len; i-- > 0;) last = insertNode(vertices + i, points[i], last);
Branch: 1 branch
BranchTrueFalseTotal
for (i = len; i-- > 0;) last = insertNode(vertices + i, points[i], last); 4 1 5
207 }
208  
209 2 ▶ if (last && equals(last, last->next)) {
Branch: 3 branches
BranchTrueFalseTotal
if (last && equals(last, last->next)) { 2 0 2
if (last && equals(last, last->next)) { 0 2 2
if (last && equals(last, last->next)) { 0 2 2
210 0 removeNode(last);
211 0 last = last->next;
212 }
213  
214 2 vertices += len;
215  
216 2 return last;
217 }
218  
219 // eliminate colinear or duplicate points
220 template <typename N>
221 typename Earcut<N>::Node*
222 2 Earcut<N>::filterPoints(Node* start, Node* end) {
223 2 ▶ if (!end) end = start;
Branch: 1 branch
BranchTrueFalseTotal
if (!end) end = start; 0 2 2
224  
225 2 Node* p = start;
226 bool again;
227 do {
228 2 again = false;
229  
230 2 ▶ if (!p->steiner && (equals(p, p->next) || area(p->prev, p, p->next) == 0)) {
Branch: 4 branches
BranchTrueFalseTotal
if (!p->steiner && (equals(p, p->next) || area(p->prev, p, p->next) == 0)) { 2 0 2
if (!p->steiner && (equals(p, p->next) || area(p->prev, p, p->next) == 0)) { 2 0 2
if (!p->steiner && (equals(p, p->next) || area(p->prev, p, p->next) == 0)) { 0 2 2
if (!p->steiner && (equals(p, p->next) || area(p->prev, p, p->next) == 0)) { 0 2 2
231 0 removeNode(p);
232 0 p = end = p->prev;
233  
234 0 ▶ if (p == p->next) break;
Branch: 1 branch
BranchTrueFalseTotal
if (p == p->next) break; 0 0 0
235 0 again = true;
236  
237 } else {
238 2 p = p->next;
239 }
240 2 ▶ } while (again || p != end);
Branch: 2 branches
BranchTrueFalseTotal
} while (again || p != end); 0 2 2
} while (again || p != end); 0 2 2
241  
242 2 return end;
243 }
244  
245 // main ear slicing loop which triangulates a polygon (given as a linked list)
246 template <typename N>
247 1 void Earcut<N>::earcutLinked(Node* ear, int pass) {
248 1 ▶ if (!ear) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!ear) return; 0 1 1
249  
250 // interlink polygon nodes in z-order
251 1 ▶ if (!pass && hashing) indexCurve(ear);
Branch: 2 branches
BranchTrueFalseTotal
if (!pass && hashing) indexCurve(ear); 1 0 1
if (!pass && hashing) indexCurve(ear); 0 1 1
252  
253 1 Node* stop = ear;
254 Node* prev;
255 Node* next;
256  
257 1 int iterations = 0;
258  
259 // iterate through ears, slicing them one by one
260 20 ▶ while (ear->prev != ear->next) {
Branch: 1 branch
BranchTrueFalseTotal
while (ear->prev != ear->next) { 19 1 20
261 19 iterations++;
262 19 prev = ear->prev;
263 19 next = ear->next;
264  
265 19 ▶ if (hashing ? isEarHashed(ear) : isEar(ear)) {
Branch: 2 branches
BranchTrueFalseTotal
if (hashing ? isEarHashed(ear) : isEar(ear)) { 0 19 19
if (hashing ? isEarHashed(ear) : isEar(ear)) { 8 11 19
266 // cut off the triangle
267 8 indices.emplace_back(prev->i);
268 8 indices.emplace_back(ear->i);
269 8 indices.emplace_back(next->i);
270  
271 8 removeNode(ear);
272  
273 // skipping the next vertice leads to less sliver triangles
274 8 ear = next->next;
275 8 stop = next->next;
276  
277 8 continue;
278 }
279  
280 11 ear = next;
281  
282 // if we looped through the whole remaining polygon and can't find any more ears
283 11 ▶ if (ear == stop) {
Branch: 1 branch
BranchTrueFalseTotal
if (ear == stop) { 0 11 11
284 // try filtering points and slicing again
285 0 ▶ if (!pass) earcutLinked(filterPoints(ear), 1);
Branch: 1 branch
BranchTrueFalseTotal
if (!pass) earcutLinked(filterPoints(ear), 1); 0 0 0
286  
287 // if this didn't work, try curing all small self-intersections locally
288 0 ▶ else if (pass == 1) {
Branch: 1 branch
BranchTrueFalseTotal
else if (pass == 1) { 0 0 0
289 0 ear = cureLocalIntersections(ear);
290 0 earcutLinked(ear, 2);
291  
292 // as a last resort, try splitting the remaining polygon into two
293 0 ▶ } else if (pass == 2) splitEarcut(ear);
Branch: 1 branch
BranchTrueFalseTotal
} else if (pass == 2) splitEarcut(ear); 0 0 0
294  
295 0 break;
296 }
297 }
298 }
299  
300 // check whether a polygon node forms a valid ear with adjacent nodes
301 template <typename N>
302 19 bool Earcut<N>::isEar(Node* ear) {
303 19 const Node* a = ear->prev;
304 19 const Node* b = ear;
305 19 const Node* c = ear->next;
306  
307 19 ▶ if (area(a, b, c) >= 0) return false; // reflex, can't be an ear
Branch: 1 branch
BranchTrueFalseTotal
if (area(a, b, c) >= 0) return false; // reflex, can't be an ear 6 13 19
308  
309 // now make sure we don't have other points inside the potential ear
310 13 Node* p = ear->next->next;
311  
312 46 ▶ while (p != ear->prev) {
Branch: 1 branch
BranchTrueFalseTotal
while (p != ear->prev) { 38 8 46
313 47 ▶ if (pointInTriangle(a->x, a->y, b->x, b->y, c->x, c->y, p->x, p->y) &&
Branch: 1 branch
BranchTrueFalseTotal
if (pointInTriangle(a->x, a->y, b->x, b->y, c->x, c->y, p->x, p->y) && 5 33 38
314 14 area(p->prev, p, p->next) >= 0) return false;
315 33 p = p->next;
316 }
317  
318 8 return true;
319 }
320  
321 template <typename N>
322 0 bool Earcut<N>::isEarHashed(Node* ear) {
323 0 const Node* a = ear->prev;
324 0 const Node* b = ear;
325 0 const Node* c = ear->next;
326  
327 0 ▶ if (area(a, b, c) >= 0) return false; // reflex, can't be an ear
Branch: 1 branch
BranchTrueFalseTotal
if (area(a, b, c) >= 0) return false; // reflex, can't be an ear 0 0 0
328  
329 // triangle bbox; min & max are calculated like this for speed
330 0 const double minTX = std::min<double>(a->x, std::min<double>(b->x, c->x));
331 0 const double minTY = std::min<double>(a->y, std::min<double>(b->y, c->y));
332 0 const double maxTX = std::max<double>(a->x, std::max<double>(b->x, c->x));
333 0 const double maxTY = std::max<double>(a->y, std::max<double>(b->y, c->y));
334  
335 // z-order range for the current triangle bbox;
336 0 const int32_t minZ = zOrder(minTX, minTY);
337 0 const int32_t maxZ = zOrder(maxTX, maxTY);
338  
339 // first look for points inside the triangle in increasing z-order
340 0 Node* p = ear->nextZ;
341  
342 0 ▶ while (p && p->z <= maxZ) {
Branch: 2 branches
BranchTrueFalseTotal
while (p && p->z <= maxZ) { 0 0 0
while (p && p->z <= maxZ) { 0 0 0
343 0 if (p != ear->prev && p != ear->next &&
344 0 ▶ pointInTriangle(a->x, a->y, b->x, b->y, c->x, c->y, p->x, p->y) &&
Branch: 3 branches
BranchTrueFalseTotal
pointInTriangle(a->x, a->y, b->x, b->y, c->x, c->y, p->x, p->y) && 0 0 0
pointInTriangle(a->x, a->y, b->x, b->y, c->x, c->y, p->x, p->y) && 0 0 0
pointInTriangle(a->x, a->y, b->x, b->y, c->x, c->y, p->x, p->y) && 0 0 0
345 0 area(p->prev, p, p->next) >= 0) return false;
346 0 p = p->nextZ;
347 }
348  
349 // then look for points in decreasing z-order
350 0 p = ear->prevZ;
351  
352 0 ▶ while (p && p->z >= minZ) {
Branch: 2 branches
BranchTrueFalseTotal
while (p && p->z >= minZ) { 0 0 0
while (p && p->z >= minZ) { 0 0 0
353 0 if (p != ear->prev && p != ear->next &&
354 0 ▶ pointInTriangle(a->x, a->y, b->x, b->y, c->x, c->y, p->x, p->y) &&
Branch: 3 branches
BranchTrueFalseTotal
pointInTriangle(a->x, a->y, b->x, b->y, c->x, c->y, p->x, p->y) && 0 0 0
pointInTriangle(a->x, a->y, b->x, b->y, c->x, c->y, p->x, p->y) && 0 0 0
pointInTriangle(a->x, a->y, b->x, b->y, c->x, c->y, p->x, p->y) && 0 0 0
355 0 area(p->prev, p, p->next) >= 0) return false;
356 0 p = p->prevZ;
357 }
358  
359 0 return true;
360 }
361  
362 // go through all polygon nodes and cure small local self-intersections
363 template <typename N>
364 typename Earcut<N>::Node*
365 0 Earcut<N>::cureLocalIntersections(Node* start) {
366 0 Node* p = start;
367 do {
368 0 Node* a = p->prev;
369 0 Node* b = p->next->next;
370  
371 // a self-intersection where edge (v[i-1],v[i]) intersects (v[i+1],v[i+2])
372 0 ▶ if (!equals(a, b) && intersects(a, p, p->next, b) && locallyInside(a, b) && locallyInside(b, a)) {
Branch: 5 branches
BranchTrueFalseTotal
if (!equals(a, b) && intersects(a, p, p->next, b) && locallyInside(a, b) && locallyInside(b, a)) { 0 0 0
if (!equals(a, b) && intersects(a, p, p->next, b) && locallyInside(a, b) && locallyInside(b, a)) { 0 0 0
if (!equals(a, b) && intersects(a, p, p->next, b) && locallyInside(a, b) && locallyInside(b, a)) { 0 0 0
if (!equals(a, b) && intersects(a, p, p->next, b) && locallyInside(a, b) && locallyInside(b, a)) { 0 0 0
if (!equals(a, b) && intersects(a, p, p->next, b) && locallyInside(a, b) && locallyInside(b, a)) { 0 0 0
373 0 indices.emplace_back(a->i);
374 0 indices.emplace_back(p->i);
375 0 indices.emplace_back(b->i);
376  
377 // remove two nodes involved
378 0 removeNode(p);
379 0 removeNode(p->next);
380  
381 0 p = start = b;
382 }
383 0 p = p->next;
384 0 ▶ } while (p != start);
Branch: 1 branch
BranchTrueFalseTotal
} while (p != start); 0 0 0
385  
386 0 return p;
387 }
388  
389 // try splitting polygon into two and triangulate them independently
390 template <typename N>
391 0 void Earcut<N>::splitEarcut(Node* start) {
392 // look for a valid diagonal that divides the polygon into two
393 0 Node* a = start;
394 do {
395 0 Node* b = a->next->next;
396 0 ▶ while (b != a->prev) {
Branch: 1 branch
BranchTrueFalseTotal
while (b != a->prev) { 0 0 0
397 0 ▶ if (a->i != b->i && isValidDiagonal(a, b)) {
Branch: 3 branches
BranchTrueFalseTotal
if (a->i != b->i && isValidDiagonal(a, b)) { 0 0 0
if (a->i != b->i && isValidDiagonal(a, b)) { 0 0 0
if (a->i != b->i && isValidDiagonal(a, b)) { 0 0 0
398 // split the polygon in two by the diagonal
399 0 Node* c = splitPolygon(a, b);
400  
401 // filter colinear points around the cuts
402 0 a = filterPoints(a, a->next);
403 0 c = filterPoints(c, c->next);
404  
405 // run earcut on each half
406 0 earcutLinked(a);
407 0 earcutLinked(c);
408 0 return;
409 }
410 0 b = b->next;
411 }
412 0 a = a->next;
413 0 ▶ } while (a != start);
Branch: 1 branch
BranchTrueFalseTotal
} while (a != start); 0 0 0
414 }
415  
416 // link every hole into the outer loop, producing a single-ring polygon without holes
417 template <typename N> template <typename Polygon>
418 typename Earcut<N>::Node*
419 1 Earcut<N>::eliminateHoles(const Polygon& points, Node* outerNode) {
420 1 const size_t len = points.size();
421  
422 1 std::vector<Node*> queue;
423 2 ▶ for (size_t i = 1; i < len; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (size_t i = 1; i < len; i++) { 1 1 2
424 1 ▶ Node* list = linkedList(points[i], false);
Branch: 1 branch
BranchTrueFalseTotal
Node* list = linkedList(points[i], false); 1 0 1
425 1 ▶ if (list) {
Branch: 1 branch
BranchTrueFalseTotal
if (list) { 1 0 1
426 1 ▶ if (list == list->next) list->steiner = true;
Branch: 1 branch
BranchTrueFalseTotal
if (list == list->next) list->steiner = true; 0 1 1
427 1 ▶ queue.push_back(getLeftmost(list));
Branch: 1 branch
BranchTrueFalseTotal
queue.push_back(getLeftmost(list)); 1 0 1
428 }
429 }
430 1 ▶ std::sort(queue.begin(), queue.end(), [](const Node* a, const Node* b) {
Branch: 1 branch
BranchTrueFalseTotal
std::sort(queue.begin(), queue.end(), [](const Node* a, const Node* b) { 1 0 1
431 0 return a->x < b->x;
432 });
433  
434 // process holes from left to right
435 2 ▶ for (size_t i = 0; i < queue.size(); i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (size_t i = 0; i < queue.size(); i++) { 1 1 2
436 1 ▶ eliminateHole(queue[i], outerNode);
Branch: 1 branch
BranchTrueFalseTotal
eliminateHole(queue[i], outerNode); 1 0 1
437 1 ▶ outerNode = filterPoints(outerNode, outerNode->next);
Branch: 1 branch
BranchTrueFalseTotal
outerNode = filterPoints(outerNode, outerNode->next); 1 0 1
438 }
439  
440 1 return outerNode;
441 1 }
442  
443 // find a bridge between vertices that connects hole with an outer ring and and link it
444 template <typename N>
445 1 void Earcut<N>::eliminateHole(Node* hole, Node* outerNode) {
446 1 outerNode = findHoleBridge(hole, outerNode);
447 1 ▶ if (outerNode) {
Branch: 1 branch
BranchTrueFalseTotal
if (outerNode) { 1 0 1
448 1 Node* b = splitPolygon(outerNode, hole);
449 1 filterPoints(b, b->next);
450 }
451 1 }
452  
453 // David Eberly's algorithm for finding a bridge between hole and outer polygon
454 template <typename N>
455 typename Earcut<N>::Node*
456 1 Earcut<N>::findHoleBridge(Node* hole, Node* outerNode) {
457 1 Node* p = outerNode;
458 1 double hx = hole->x;
459 1 double hy = hole->y;
460 1 double qx = -std::numeric_limits<double>::infinity();
461 1 Node* m = nullptr;
462  
463 // find a segment intersected by a ray from the hole's leftmost Vertex to the left;
464 // segment's endpoint with lesser x will be potential connection Vertex
465 do {
466 4 ▶ if (hy <= p->y && hy >= p->next->y && p->next->y != p->y) {
Branch: 3 branches
BranchTrueFalseTotal
if (hy <= p->y && hy >= p->next->y && p->next->y != p->y) { 2 2 4
if (hy <= p->y && hy >= p->next->y && p->next->y != p->y) { 1 1 2
if (hy <= p->y && hy >= p->next->y && p->next->y != p->y) { 1 0 1
467 1 double x = p->x + (hy - p->y) * (p->next->x - p->x) / (p->next->y - p->y);
468 1 ▶ if (x <= hx && x > qx) {
Branch: 2 branches
BranchTrueFalseTotal
if (x <= hx && x > qx) { 1 0 1
if (x <= hx && x > qx) { 1 0 1
469 1 qx = x;
470 1 ▶ if (x == hx) {
Branch: 1 branch
BranchTrueFalseTotal
if (x == hx) { 0 1 1
471 0 ▶ if (hy == p->y) return p;
Branch: 1 branch
BranchTrueFalseTotal
if (hy == p->y) return p; 0 0 0
472 0 ▶ if (hy == p->next->y) return p->next;
Branch: 1 branch
BranchTrueFalseTotal
if (hy == p->next->y) return p->next; 0 0 0
473 }
474 1 ▶ m = p->x < p->next->x ? p : p->next;
Branch: 1 branch
BranchTrueFalseTotal
m = p->x < p->next->x ? p : p->next; 0 1 1
475 }
476 }
477 4 p = p->next;
478 4 ▶ } while (p != outerNode);
Branch: 1 branch
BranchTrueFalseTotal
} while (p != outerNode); 3 1 4
479  
480 1 ▶ if (!m) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!m) return 0; 0 1 1
481  
482 1 ▶ if (hx == qx) return m->prev;
Branch: 1 branch
BranchTrueFalseTotal
if (hx == qx) return m->prev; 0 1 1
483  
484 // look for points inside the triangle of hole Vertex, segment intersection and endpoint;
485 // if there are no points found, we have a valid connection;
486 // otherwise choose the Vertex of the minimum angle with the ray as connection Vertex
487  
488 1 const Node* stop = m;
489 1 double tanMin = std::numeric_limits<double>::infinity();
490 1 double tanCur = 0;
491  
492 1 p = m->next;
493 1 double mx = m->x;
494 1 double my = m->y;
495  
496 4 ▶ while (p != stop) {
Branch: 1 branch
BranchTrueFalseTotal
while (p != stop) { 3 1 4
497 4 ▶ if (hx >= p->x && p->x >= mx && hx != p->x &&
Branch: 3 branches
BranchTrueFalseTotal
if (hx >= p->x && p->x >= mx && hx != p->x && 1 2 3
if (hx >= p->x && p->x >= mx && hx != p->x && 1 0 1
if (hx >= p->x && p->x >= mx && hx != p->x && 0 3 3
498 1 ▶ pointInTriangle(hy < my ? hx : qx, hy, mx, my, hy < my ? qx : hx, hy, p->x, p->y)) {
Branch: 2 branches
BranchTrueFalseTotal
pointInTriangle(hy < my ? hx : qx, hy, mx, my, hy < my ? qx : hx, hy, p->x, p->y)) { 0 1 1
pointInTriangle(hy < my ? hx : qx, hy, mx, my, hy < my ? qx : hx, hy, p->x, p->y)) { 0 1 1
499  
500 0 tanCur = std::abs(hy - p->y) / (hx - p->x); // tangential
501  
502 0 ▶ if ((tanCur < tanMin || (tanCur == tanMin && p->x > m->x)) && locallyInside(p, hole)) {
Branch: 5 branches
BranchTrueFalseTotal
if ((tanCur < tanMin || (tanCur == tanMin && p->x > m->x)) && locallyInside(p, hole)) { 0 0 0
if ((tanCur < tanMin || (tanCur == tanMin && p->x > m->x)) && locallyInside(p, hole)) { 0 0 0
if ((tanCur < tanMin || (tanCur == tanMin && p->x > m->x)) && locallyInside(p, hole)) { 0 0 0
if ((tanCur < tanMin || (tanCur == tanMin && p->x > m->x)) && locallyInside(p, hole)) { 0 0 0
if ((tanCur < tanMin || (tanCur == tanMin && p->x > m->x)) && locallyInside(p, hole)) { 0 0 0
503 0 m = p;
504 0 tanMin = tanCur;
505 }
506 }
507  
508 3 p = p->next;
509 }
510  
511 1 return m;
512 }
513  
514 // interlink polygon nodes in z-order
515 template <typename N>
516 0 void Earcut<N>::indexCurve(Node* start) {
517 0 ▶ assert(start);
Branch: 1 branch
BranchTrueFalseTotal
assert(start); 0 0 0
518 0 Node* p = start;
519  
520 do {
521 0 ▶ p->z = p->z ? p->z : zOrder(p->x, p->y);
Branch: 1 branch
BranchTrueFalseTotal
p->z = p->z ? p->z : zOrder(p->x, p->y); 0 0 0
522 0 p->prevZ = p->prev;
523 0 p->nextZ = p->next;
524 0 p = p->next;
525 0 ▶ } while (p != start);
Branch: 1 branch
BranchTrueFalseTotal
} while (p != start); 0 0 0
526  
527 0 p->prevZ->nextZ = nullptr;
528 0 p->prevZ = nullptr;
529  
530 0 sortLinked(p);
531 0 }
532  
533 // Simon Tatham's linked list merge sort algorithm
534 // http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html
535 template <typename N>
536 typename Earcut<N>::Node*
537 0 Earcut<N>::sortLinked(Node* list) {
538 0 ▶ assert(list);
Branch: 1 branch
BranchTrueFalseTotal
assert(list); 0 0 0
539 Node* p;
540 Node* q;
541 Node* e;
542 Node* tail;
543 int i, numMerges, pSize, qSize;
544 0 int inSize = 1;
545  
546 for (;;) {
547 0 p = list;
548 0 list = nullptr;
549 0 tail = nullptr;
550 0 numMerges = 0;
551  
552 0 ▶ while (p) {
Branch: 1 branch
BranchTrueFalseTotal
while (p) { 0 0 0
553 0 numMerges++;
554 0 q = p;
555 0 pSize = 0;
556 0 ▶ for (i = 0; i < inSize; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < inSize; i++) { 0 0 0
557 0 pSize++;
558 0 q = q->nextZ;
559 0 ▶ if (!q) break;
Branch: 1 branch
BranchTrueFalseTotal
if (!q) break; 0 0 0
560 }
561  
562 0 qSize = inSize;
563  
564 0 ▶ while (pSize > 0 || (qSize > 0 && q)) {
Branch: 3 branches
BranchTrueFalseTotal
while (pSize > 0 || (qSize > 0 && q)) { 0 0 0
while (pSize > 0 || (qSize > 0 && q)) { 0 0 0
while (pSize > 0 || (qSize > 0 && q)) { 0 0 0
565  
566 0 ▶ if (pSize == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (pSize == 0) { 0 0 0
567 0 e = q;
568 0 q = q->nextZ;
569 0 qSize--;
570 0 ▶ } else if (qSize == 0 || !q) {
Branch: 2 branches
BranchTrueFalseTotal
} else if (qSize == 0 || !q) { 0 0 0
} else if (qSize == 0 || !q) { 0 0 0
571 0 e = p;
572 0 p = p->nextZ;
573 0 pSize--;
574 0 ▶ } else if (p->z <= q->z) {
Branch: 1 branch
BranchTrueFalseTotal
} else if (p->z <= q->z) { 0 0 0
575 0 e = p;
576 0 p = p->nextZ;
577 0 pSize--;
578 } else {
579 0 e = q;
580 0 q = q->nextZ;
581 0 qSize--;
582 }
583  
584 0 ▶ if (tail) tail->nextZ = e;
Branch: 1 branch
BranchTrueFalseTotal
if (tail) tail->nextZ = e; 0 0 0
585 0 else list = e;
586  
587 0 e->prevZ = tail;
588 0 tail = e;
589 }
590  
591 0 p = q;
592 }
593  
594 0 tail->nextZ = nullptr;
595  
596 0 ▶ if (numMerges <= 1) return list;
Branch: 1 branch
BranchTrueFalseTotal
if (numMerges <= 1) return list; 0 0 0
597  
598 0 inSize *= 2;
599 }
600 }
601  
602 // z-order of a Vertex given coords and size of the data bounding box
603 template <typename N>
604 0 int32_t Earcut<N>::zOrder(const double x_, const double y_) {
605 // coords are transformed into non-negative 15-bit integer range
606 0 int32_t x = static_cast<int32_t>(32767.0 * (x_ - minX) * inv_size);
607 0 int32_t y = static_cast<int32_t>(32767.0 * (y_ - minY) * inv_size);
608  
609 0 x = (x | (x << 8)) & 0x00FF00FF;
610 0 x = (x | (x << 4)) & 0x0F0F0F0F;
611 0 x = (x | (x << 2)) & 0x33333333;
612 0 x = (x | (x << 1)) & 0x55555555;
613  
614 0 y = (y | (y << 8)) & 0x00FF00FF;
615 0 y = (y | (y << 4)) & 0x0F0F0F0F;
616 0 y = (y | (y << 2)) & 0x33333333;
617 0 y = (y | (y << 1)) & 0x55555555;
618  
619 0 return x | (y << 1);
620 }
621  
622 // find the leftmost node of a polygon ring
623 template <typename N>
624 typename Earcut<N>::Node*
625 1 Earcut<N>::getLeftmost(Node* start) {
626 1 Node* p = start;
627 1 Node* leftmost = start;
628 do {
629 4 ▶ if (p->x < leftmost->x) leftmost = p;
Branch: 1 branch
BranchTrueFalseTotal
if (p->x < leftmost->x) leftmost = p; 1 3 4
630 4 p = p->next;
631 4 ▶ } while (p != start);
Branch: 1 branch
BranchTrueFalseTotal
} while (p != start); 3 1 4
632  
633 1 return leftmost;
634 }
635  
636 // check if a point lies within a convex triangle
637 template <typename N>
638 39 bool Earcut<N>::pointInTriangle(double ax, double ay, double bx, double by, double cx, double cy, double px, double py) const {
639 58 return (cx - px) * (ay - py) - (ax - px) * (cy - py) >= 0 &&
640 50 ▶ (ax - px) * (by - py) - (bx - px) * (ay - py) >= 0 &&
Branch: 2 branches
BranchTrueFalseTotal
(ax - px) * (by - py) - (bx - px) * (ay - py) >= 0 && 19 20 39
(ax - px) * (by - py) - (bx - px) * (ay - py) >= 0 && 11 8 19
641 50 ▶ (bx - px) * (cy - py) - (cx - px) * (by - py) >= 0;
Branch: 1 branch
BranchTrueFalseTotal
(bx - px) * (cy - py) - (cx - px) * (by - py) >= 0; 9 2 11
642 }
643  
644 // check if a diagonal between two polygon nodes is valid (lies in polygon interior)
645 template <typename N>
646 0 bool Earcut<N>::isValidDiagonal(Node* a, Node* b) {
647 0 ▶ return a->next->i != b->i && a->prev->i != b->i && !intersectsPolygon(a, b) &&
Branch: 1 branch
BranchTrueFalseTotal
return a->next->i != b->i && a->prev->i != b->i && !intersectsPolygon(a, b) && 0 0 0
648 0 ▶ locallyInside(a, b) && locallyInside(b, a) && middleInside(a, b);
Branch: 3 branches
BranchTrueFalseTotal
locallyInside(a, b) && locallyInside(b, a) && middleInside(a, b); 0 0 0
locallyInside(a, b) && locallyInside(b, a) && middleInside(a, b); 0 0 0
locallyInside(a, b) && locallyInside(b, a) && middleInside(a, b); 0 0 0
649 }
650  
651 // signed area of a triangle
652 template <typename N>
653 30 double Earcut<N>::area(const Node* p, const Node* q, const Node* r) const {
654 30 return (q->y - p->y) * (r->x - q->x) - (q->x - p->x) * (r->y - q->y);
655 }
656  
657 // check if two points are equal
658 template <typename N>
659 4 bool Earcut<N>::equals(const Node* p1, const Node* p2) {
660 4 ▶ return p1->x == p2->x && p1->y == p2->y;
Branch: 2 branches
BranchTrueFalseTotal
return p1->x == p2->x && p1->y == p2->y; 2 2 4
return p1->x == p2->x && p1->y == p2->y; 0 2 2
661 }
662  
663 // check if two segments intersect
664 template <typename N>
665 0 bool Earcut<N>::intersects(const Node* p1, const Node* q1, const Node* p2, const Node* q2) {
666 0 ▶ if ((equals(p1, q1) && equals(p2, q2)) ||
Branch: 2 branches
BranchTrueFalseTotal
if ((equals(p1, q1) && equals(p2, q2)) || 0 0 0
if ((equals(p1, q1) && equals(p2, q2)) || 0 0 0
667 0 ▶ (equals(p1, q2) && equals(p2, q1))) return true;
Branch: 1 branch
BranchTrueFalseTotal
(equals(p1, q2) && equals(p2, q1))) return true; 0 0 0
668 0 ▶ return (area(p1, q1, p2) > 0) != (area(p1, q1, q2) > 0) &&
Branch: 1 branch
BranchTrueFalseTotal
return (area(p1, q1, p2) > 0) != (area(p1, q1, q2) > 0) && 0 0 0
669 0 ▶ (area(p2, q2, p1) > 0) != (area(p2, q2, q1) > 0);
Branch: 1 branch
BranchTrueFalseTotal
(area(p2, q2, p1) > 0) != (area(p2, q2, q1) > 0); 0 0 0
670 }
671  
672 // check if a polygon diagonal intersects any polygon segments
673 template <typename N>
674 0 bool Earcut<N>::intersectsPolygon(const Node* a, const Node* b) {
675 0 const Node* p = a;
676 do {
677 0 ▶ if (p->i != a->i && p->next->i != a->i && p->i != b->i && p->next->i != b->i &&
Branch: 4 branches
BranchTrueFalseTotal
if (p->i != a->i && p->next->i != a->i && p->i != b->i && p->next->i != b->i && 0 0 0
if (p->i != a->i && p->next->i != a->i && p->i != b->i && p->next->i != b->i && 0 0 0
if (p->i != a->i && p->next->i != a->i && p->i != b->i && p->next->i != b->i && 0 0 0
if (p->i != a->i && p->next->i != a->i && p->i != b->i && p->next->i != b->i && 0 0 0
678 0 intersects(p, p->next, a, b)) return true;
679 0 p = p->next;
680 0 ▶ } while (p != a);
Branch: 1 branch
BranchTrueFalseTotal
} while (p != a); 0 0 0
681  
682 0 return false;
683 }
684  
685 // check if a polygon diagonal is locally inside the polygon
686 template <typename N>
687 0 bool Earcut<N>::locallyInside(const Node* a, const Node* b) {
688 0 ▶ return area(a->prev, a, a->next) < 0 ?
Branch: 1 branch
BranchTrueFalseTotal
return area(a->prev, a, a->next) < 0 ? 0 0 0
689 0 ▶ area(a, b, a->next) >= 0 && area(a, a->prev, b) >= 0 :
Branch: 2 branches
BranchTrueFalseTotal
area(a, b, a->next) >= 0 && area(a, a->prev, b) >= 0 : 0 0 0
area(a, b, a->next) >= 0 && area(a, a->prev, b) >= 0 : 0 0 0
690 0 ▶ area(a, b, a->prev) < 0 || area(a, a->next, b) < 0;
Branch: 2 branches
BranchTrueFalseTotal
area(a, b, a->prev) < 0 || area(a, a->next, b) < 0; 0 0 0
area(a, b, a->prev) < 0 || area(a, a->next, b) < 0; 0 0 0
691 }
692  
693 // check if the middle Vertex of a polygon diagonal is inside the polygon
694 template <typename N>
695 0 bool Earcut<N>::middleInside(const Node* a, const Node* b) {
696 0 const Node* p = a;
697 0 bool inside = false;
698 0 double px = (a->x + b->x) / 2;
699 0 double py = (a->y + b->y) / 2;
700 do {
701 0 ▶ if (((p->y > py) != (p->next->y > py)) && p->next->y != p->y &&
Branch: 2 branches
BranchTrueFalseTotal
if (((p->y > py) != (p->next->y > py)) && p->next->y != p->y && 0 0 0
if (((p->y > py) != (p->next->y > py)) && p->next->y != p->y && 0 0 0
702 0 ▶ (px < (p->next->x - p->x) * (py - p->y) / (p->next->y - p->y) + p->x))
Branch: 1 branch
BranchTrueFalseTotal
(px < (p->next->x - p->x) * (py - p->y) / (p->next->y - p->y) + p->x)) 0 0 0
703 0 inside = !inside;
704 0 p = p->next;
705 0 ▶ } while (p != a);
Branch: 1 branch
BranchTrueFalseTotal
} while (p != a); 0 0 0
706  
707 0 return inside;
708 }
709  
710 // link two polygon vertices with a bridge; if the vertices belong to the same ring, it splits
711 // polygon into two; if one belongs to the outer ring and another to a hole, it merges it into a
712 // single ring
713 template <typename N>
714 typename Earcut<N>::Node*
715 1 Earcut<N>::splitPolygon(Node* a, Node* b) {
716 1 Node* a2 = nodes.construct(a->i, a->x, a->y);
717 1 Node* b2 = nodes.construct(b->i, b->x, b->y);
718 1 Node* an = a->next;
719 1 Node* bp = b->prev;
720  
721 1 a->next = b;
722 1 b->prev = a;
723  
724 1 a2->next = an;
725 1 an->prev = a2;
726  
727 1 b2->next = a2;
728 1 a2->prev = b2;
729  
730 1 bp->next = b2;
731 1 b2->prev = bp;
732  
733 1 return b2;
734 }
735  
736 // create a node and util::optionally link it with previous one (in a circular doubly linked list)
737 template <typename N> template <typename Point>
738 typename Earcut<N>::Node*
739 8 Earcut<N>::insertNode(std::size_t i, const Point& pt, Node* last) {
740 8 ▶ Node* p = nodes.construct(static_cast<N>(i), util::nth<0, Point>::get(pt), util::nth<1, Point>::get(pt));
Branch: 1 branch
BranchTrueFalseTotal
Node* p = nodes.construct(static_cast<N>(i), util::nth<0, Point>::get(pt), util::nth<1, Point>::get(pt)); 8 0 8
741  
742 8 ▶ if (!last) {
Branch: 1 branch
BranchTrueFalseTotal
if (!last) { 2 6 8
743 2 p->prev = p;
744 2 p->next = p;
745  
746 } else {
747 6 ▶ assert(last);
Branch: 1 branch
BranchTrueFalseTotal
assert(last); 0 6 6
748 6 p->next = last->next;
749 6 p->prev = last;
750 6 last->next->prev = p;
751 6 last->next = p;
752 }
753 8 return p;
754 }
755  
756 template <typename N>
757 8 void Earcut<N>::removeNode(Node* p) {
758 8 p->next->prev = p->prev;
759 8 p->prev->next = p->next;
760  
761 8 ▶ if (p->prevZ) p->prevZ->nextZ = p->nextZ;
Branch: 1 branch
BranchTrueFalseTotal
if (p->prevZ) p->prevZ->nextZ = p->nextZ; 0 8 8
762 8 ▶ if (p->nextZ) p->nextZ->prevZ = p->prevZ;
Branch: 1 branch
BranchTrueFalseTotal
if (p->nextZ) p->nextZ->prevZ = p->prevZ; 0 8 8
763 8 }
764 }
765  
766 template <typename N = uint32_t, typename Polygon>
767 1 std::vector<N> earcut(const Polygon& poly) {
768 1 ▶ mapbox::detail::Earcut<N> earcut;
Branch: 1 branch
BranchTrueFalseTotal
mapbox::detail::Earcut<N> earcut; 1 0 1
769 1 ▶ earcut(poly);
Branch: 1 branch
BranchTrueFalseTotal
earcut(poly); 1 0 1
770 2 return std::move(earcut.indices);
771 1 }
772 }
« xsi/WKBWriter.xsi ↑ Summary xsi/MultiPoint.xsi »