GCC Code Coverage Report

Directory: ./
File: lib/geogram/voronoi/generic_RVD_vertex.h
Date: 2026-09-07 02:25:23
Exec Total Coverage
Lines: 135 136 99.3%
Functions: 14 20 70.0%
Branches: 139 1356 10.3%
Line Branch Exec Source
1 /*
2 * Copyright (c) 2000-2022 Inria
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are met:
7 *
8 * * Redistributions of source code must retain the above copyright notice,
9 * this list of conditions and the following disclaimer.
10 * * Redistributions in binary form must reproduce the above copyright notice,
11 * this list of conditions and the following disclaimer in the documentation
12 * and/or other materials provided with the distribution.
13 * * Neither the name of the ALICE Project-Team nor the names of its
14 * contributors may be used to endorse or promote products derived from this
15 * software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
18 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
21 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
22 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
23 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
24 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
25 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
26 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
27 * POSSIBILITY OF SUCH DAMAGE.
28 *
29 * Contact: Bruno Levy
30 *
31 * https://www.inria.fr/fr/bruno-levy
32 *
33 * Inria,
34 * Domaine de Voluceau,
35 * 78150 Le Chesnay - Rocquencourt
36 * FRANCE
37 *
38 */
39
40 #ifndef GEOGRAM_VORONOI_GENERIC_RVD_VERTEX
41 #define GEOGRAM_VORONOI_GENERIC_RVD_VERTEX
42
43 #include <geogram/basic/common.h>
44 #include <geogram/mesh/mesh.h>
45 #include <geogram/delaunay/delaunay_nn.h>
46 #include <geogram/basic/assert.h>
47 #include <geogram/basic/process.h>
48 #include <geogram/basic/attributes.h>
49
50 /**
51 * \file geogram/voronoi/generic_RVD_vertex.h
52 * \brief Types and utilities for manipulating vertices in geometric
53 * and symbolic forms in restricted Voronoi diagrams.
54 * \note This file contains functions and classes used by the
55 * internal implementation of GEO::GenericVoronoiDiagram.
56 * Except some special uses, e.g. subclassing GEO::IntegrationSimplex,
57 * they are not meant to be used directly by client code.
58 */
59
60 namespace GEOGen {
61
62 using GEO::Delaunay; /**< \brief type for nD Delaunay triangulation */
63 using GEO::index_t; /**< \brief type for indices (vertex and facet id) */
64 using GEO::signed_index_t; /**< \brief type for indices (can be <0) */
65 using GEO::coord_index_t; /**< \brief type for coordinate indices */
66 using GEO::Sign; /**< \brief type for signs (POSITIVE,ZERO or NEGATIVE) */
67
68 using GEO::Mesh;
69
70 /**
71 * \brief Small_set is similar to std::set, but with fixed
72 * maximum size (and no dynamic memory allocation).
73 * \details Used by GenericVoronoiDiagram to store vertices equations
74 * (represented as plane indices triplets).
75 * \note This is an internal implementation class, not meant to be
76 * used by client code.
77 */
78 template <class T, index_t DIM>
79 class small_set {
80
81 /** \brief This class type */
82 typedef small_set<T, DIM> thisclass;
83
84 public:
85 /** \brief A random access iterator to elements */
86 typedef T* iterator;
87
88 /** \brief A random access iterator to const elements */
89 typedef const T* const_iterator;
90
91 /** \brief Reference to element */
92 typedef T& reference;
93
94 /** \brief Type of the elements */
95 typedef T value_type;
96
97 /**
98 * \brief Constructs an empty small_set.
99 */
100 36342926 small_set() :
101 36342926 size_(0) {
102 }
103
104 /**
105 * \brief Gets the number of element in this small_set.
106 */
107 index_t size() const {
108 return size_;
109 }
110
111 /**
112 * \brief Gets the maximum number of elements that can be
113 * stored in this small_set.
114 */
115 index_t capacity() const {
116 return (index_t) DIM;
117 }
118
119 /**
120 * \brief Gets an iterator to the first element.
121 */
122 iterator begin() {
123 3312752 return data_;
124 }
125
126 /**
127 * \brief Gets an iterator one position past the last element.
128 */
129 iterator end() {
130 11545912 return data_ + size_;
131 }
132
133 /**
134 * \brief Gets an iterator one position past the last element
135 * that can be stored.
136 */
137 iterator end_of_storage() {
138 return data_ + DIM;
139 }
140
141 /**
142 * \brief Gets a const iterator to the first element..
143 */
144 const_iterator begin() const {
145 58206404 return data_;
146 }
147
148 /**
149 * \brief Gets a const iterator one position past the last element.
150 */
151 const_iterator end() const {
152 119504103 return data_ + size_;
153 }
154
155 /**
156 * \brief Gets a const iterator one position past the last element
157 * that can be stored
158 */
159 const_iterator end_of_storage() const {
160 return data_ + DIM;
161 }
162
163 /**
164 * \brief Insert a new element.
165 * \param[in] x a const reference to the element to be inserted
166 * \return an iterator to the inserted element
167 * \note Throws an assertion failure if maximum capacity is reached
168 */
169 3312752 iterator insert(const T& x) {
170 3312752 return insert(x, find_i(x));
171 }
172
173 /**
174 * \brief Inserts a new element at a specified location..
175 * \param[in] x a const reference to the element to be inserted
176 * \param[in] where an iterator to the location where \p x should be
177 * inserted
178 * \return an iterator to the inserted element (\p = where)
179 * \note Throws an assertion failure if maximum capacity is reached
180 */
181 iterator insert(const T& x, iterator where) {
182
2/2
✓ Branch 0 taken 2462423 times.
✓ Branch 1 taken 850329 times.
 3312752 if(where == end()) {
183 2462423 *where = x;
184 grow();
185 2462423 return where;
186 }
187
1/2
✓ Branch 0 taken 850329 times.
✗ Branch 1 not taken.
 850329 if(*where == x) {
188 return where;
189 }
190 grow();
191 if(where == end() - 1) {
192 *where = x;
193 return where;
194 }
195
2/2
✓ Branch 0 taken 1026204 times.
✓ Branch 1 taken 850329 times.
 1876533 for(iterator i = end() - 1; i != where; i--) {
196 geo_debug_assert(i != begin());
197 1026204 *i = *(i - 1);
198 }
199 850329 *where = x;
200 #ifdef GEO_DEBUG
201 for(iterator i = begin(); i != end() - 1; ++i) {
202 geo_debug_assert(*i < *(i + 1));
203 }
204 #endif
205 850329 return where;
206 }
207
208 /**
209 * \brief Clears this small_set.
210 */
211 void clear() {
212 1982204 size_ = 0;
213 }
214
215 /**
216 * \brief Finds an element by value.
217 * \param[in] x a const reference to the value of the element
218 * \return an iterator to the element or end() if not found
219 */
220 iterator find(const T& x) {
221 iterator result = find_i(x);
222 if(*result != x) {
223 result = end();
224 }
225 return result;
226 }
227
228 /**
229 * \brief Finds an element by value.
230 * \param[in] x a const reference to the value of the element
231 * \return a const iterator to the element or end() if not found
232 */
233 const_iterator find(const T& x) const {
234 const_iterator result = find_i(x);
235 if(*result != x) {
236 result = end();
237 }
238 return result;
239 }
240
241 /**
242 * \brief Appends an element to the end of the list.
243 * \param[in] x a const reference to the value of the element
244 * \pre \p x is greater than all the stored elements
245 */
246 void push_back(const T& x) {
247 #ifdef GEO_DEBUG
248 for(iterator i = begin(); i != end(); ++i) {
249 geo_debug_assert(*i < x);
250 }
251 #endif
252 3964408 *end() = x;
253 grow();
254 }
255
256 /**
257 * \brief Displays the stored elements.
258 */
259 void print(std::ostream& out) const {
260 out << "[ ";
261 for(const_iterator it = begin(); it != end(); ++it) {
262 out << *it << " ";
263 }
264 out << "]";
265 }
266
267 /**
268 * \brief Direct access to an element.
269 * \param[in] i index of the element
270 * \return a reference to the element
271 */
272 T& operator[] (signed_index_t i) {
273 geo_debug_assert(i >= 0);
274 geo_debug_assert(begin() + i < end());
275 return begin()[i];
276 }
277
278 /**
279 * \brief Direct access to an element.
280 * \param[in] i index of the element
281 * \return a const reference to the element
282 */
283 const T& operator[] (signed_index_t i) const {
284 geo_debug_assert(i >= 0);
285 geo_debug_assert(begin() + i < end());
286 return begin()[i];
287 }
288
289 protected:
290 /**
291 * \brief Increases the size of this small_set.
292 * \details Cannot grow past the maximum size.
293 */
294 void grow() {
295 geo_debug_assert(end() != end_of_storage());
296 3312752 size_++;
297 }
298
299 // Note: maybe we should start from end() instead of begin()
300 // since negative indices are inserted first.
301
302 /**
303 * \brief Finds where an element is or where it should be inserted
304 * from its value.
305 * \param[in] x a const reference to the value of the element
306 * \return an iterator to the location where the element should be
307 * found or inserted
308 */
309 iterator find_i(const T& x) {
310 iterator result = begin();
311
4/4
✓ Branch 0 taken 5119081 times.
✓ Branch 1 taken 2462423 times.
✓ Branch 2 taken 4268752 times.
✓ Branch 3 taken 850329 times.
 7581504 while(result != end() && *result < x) {
312 4268752 result++;
313 }
314 return result;
315 }
316
317 /**
318 * \brief Finds where an element should be located from its value.
319 * \param[in] x a const reference to the value of the element
320 * \return a const iterator to the location where the element should be
321 * found.
322 */
323 const_iterator find_i(const T& x) const {
324 const_iterator result = begin();
325 while(result != end() && *result < x) {
326 result++;
327 }
328 return result;
329 }
330
331 protected:
332 T data_[DIM];
333 index_t size_;
334 };
335
336 /**
337 * \brief Displays the contents of a small_set to a std::ostream.
338 */
339 template <class T, index_t DIM>
340 inline std::ostream& operator<< (
341 std::ostream& out,
342 const small_set<T, DIM>& S) {
343 S.print(out);
344 return out;
345 }
346
347 /**
348 * \brief Computes the intersection between two small_set%s.
349 * \param[in] S1 the first set
350 * \param[in] S2 the second set
351 * \param[out] I where to store the intersection
352 */
353 template <class T, index_t DIM1, index_t DIM2, index_t DIM3>
354 1982204 inline void sets_intersect(
355 const small_set<T, DIM1>& S1,
356 const small_set<T, DIM2>& S2,
357 small_set<T, DIM3>& I
358 ) {
359 I.clear();
360 auto i1 = S1.begin();
361 auto i2 = S2.begin();
362
4/4
✓ Branch 0 taken 7343615 times.
✓ Branch 1 taken 1401236 times.
✓ Branch 2 taken 6762647 times.
✓ Branch 3 taken 580968 times.
 8744851 while(i1 < S1.end() && i2 < S2.end()) {
363
2/2
✓ Branch 0 taken 1401236 times.
✓ Branch 1 taken 5361411 times.
 6762647 if(*i1 < *i2) {
364 1401236 ++i1;
365 }
366
2/2
✓ Branch 0 taken 1397003 times.
✓ Branch 1 taken 3964408 times.
 5361411 else if(*i2 < *i1) {
367 1397003 ++i2;
368 }
369 else {
370 I.push_back(*i1);
371 3964408 ++i1;
372 3964408 ++i2;
373 }
374 }
375 1982204 }
376
377 /**
378 * \brief A set of three integers that encodes the
379 * equation of a vertex in GenericVoronoiDiagram.
380 *
381 * \details
382 * - Each positive entry i denotes the bisector of the segment that connects
383 * the center vertex to the i-th vertex (note that the center vertex
384 * needs to be stored elsewhere, but is known when a RVD is used,
385 * since we know which dual cell we are processing).
386 *
387 * - Each negative entry i denotes the i-th face in the boundary TriMesh.
388 * Note: indexing starts with 1 (resp. -1), 0 is kept for error codes.
389 *
390 * - There is some additional information for the following
391 * two configurations:
392 * - boundary vertex: (nb_boundary_facets = 3)
393 * the index of the boundary vertex is returned
394 * by get_boundary_vertex()
395 * - intersection between boundary edge and bisector:
396 * (nb_boundary_facets = 2)
397 * the indices v1,v2 of the extremities of the boundary edges
398 * are obtained by get_boundary_edge(v1,v2)
399 *
400 * Doing so avoids recomputing vertices that we already know
401 * (and avoids numerical problems when the boundary surface has
402 * coplanar (or nearly coplanar) facets).
403 * It also allows using exact predicates (not implemented yet).
404 *
405 * \note This is an internal implementation class, not meant to be
406 * used by client code.
407 */
408 class SymbolicVertex : public small_set<GEO::signed_index_t, 3> {
409
410 /** \brief This class type */
411 typedef SymbolicVertex thisclass;
412
413 /** \brief The base class of this class */
414 typedef small_set<GEO::signed_index_t, 3> baseclass;
415
416 public:
417 /**
418 * \brief Creates an uninitialized SymbolicVertex.
419 */
420 36342926 SymbolicVertex() :
421 36342926 v1_(0),
422 36342926 v2_(0) {
423 }
424
425 /**
426 * \brief Adds a bisector to the symbolic representation.
427 */
428 void add_bisector(index_t i) {
429 1982204 baseclass::insert(signed_index_t(i) + 1);
430 }
431
432 /**
433 * \brief Adds a boundary facet to the symbolic representation.
434 */
435 void add_boundary_facet(index_t i) {
436 1173884 baseclass::insert(-signed_index_t(i) - 1);
437 749915 }
438
439 /**
440 * \brief Gets the number of boundary facets in the
441 * symbolic representation.
442 */
443 index_t nb_boundary_facets() const {
444 index_t result = 0;
445 56224200 for(auto it = baseclass::begin();
446
12/12
✓ Branch 0 taken 88108568 times.
✓ Branch 1 taken 4082607 times.
✓ Branch 2 taken 38560171 times.
✓ Branch 3 taken 49548397 times.
✓ Branch 4 taken 3889794 times.
✓ Branch 5 taken 984574 times.
✓ Branch 6 taken 3577770 times.
✓ Branch 7 taken 312024 times.
✓ Branch 8 taken 3889794 times.
✓ Branch 9 taken 964691 times.
✓ Branch 10 taken 3557887 times.
✓ Branch 11 taken 331907 times.
 101920028 it != baseclass::end() && *it < 0; ++it) {
447 45695828 result++;
448 }
449 return result;
450 }
451
452 /**
453 * \brief Gets the number of bisectors in the symbolic representation.
454 */
455 index_t nb_bisectors() const {
456 index_t result = 0;
457 1495609 for(auto it = baseclass::end() - 1;
458
10/84
✓ Branch 0 taken 2503921 times.
✓ Branch 1 taken 53064 times.
✓ Branch 2 taken 1413486 times.
✓ Branch 3 taken 1090435 times.
✓ Branch 4 taken 247654 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 153140 times.
✓ Branch 7 taken 94514 times.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✓ Branch 12 taken 612584 times.
✗ Branch 13 not taken.
✓ Branch 14 taken 354988 times.
✓ Branch 15 taken 257596 times.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
✗ Branch 20 not taken.
✗ Branch 21 not taken.
✗ Branch 22 not taken.
✗ Branch 23 not taken.
✗ Branch 24 not taken.
✗ Branch 25 not taken.
✗ Branch 26 not taken.
✗ Branch 27 not taken.
✗ Branch 28 not taken.
✗ Branch 29 not taken.
✗ Branch 30 not taken.
✗ Branch 31 not taken.
✗ Branch 32 not taken.
✗ Branch 33 not taken.
✗ Branch 34 not taken.
✗ Branch 35 not taken.
✗ Branch 36 not taken.
✗ Branch 37 not taken.
✗ Branch 38 not taken.
✗ Branch 39 not taken.
✗ Branch 40 not taken.
✗ Branch 41 not taken.
✗ Branch 42 not taken.
✗ Branch 43 not taken.
✗ Branch 44 not taken.
✗ Branch 45 not taken.
✗ Branch 46 not taken.
✗ Branch 47 not taken.
✗ Branch 48 not taken.
✗ Branch 49 not taken.
✗ Branch 50 not taken.
✗ Branch 51 not taken.
✗ Branch 52 not taken.
✗ Branch 53 not taken.
✗ Branch 54 not taken.
✗ Branch 55 not taken.
✗ Branch 56 not taken.
✗ Branch 57 not taken.
✗ Branch 58 not taken.
✗ Branch 59 not taken.
✗ Branch 60 not taken.
✗ Branch 61 not taken.
✗ Branch 62 not taken.
✗ Branch 63 not taken.
✗ Branch 64 not taken.
✗ Branch 65 not taken.
✗ Branch 66 not taken.
✗ Branch 67 not taken.
✗ Branch 68 not taken.
✗ Branch 69 not taken.
✗ Branch 70 not taken.
✗ Branch 71 not taken.
✗ Branch 72 not taken.
✗ Branch 73 not taken.
✗ Branch 74 not taken.
✗ Branch 75 not taken.
✗ Branch 76 not taken.
✗ Branch 77 not taken.
✗ Branch 78 not taken.
✗ Branch 79 not taken.
✗ Branch 80 not taken.
✗ Branch 81 not taken.
✗ Branch 82 not taken.
✗ Branch 83 not taken.
 3417223 it != baseclass::begin() - 1 && *it > 0; --it) {
459 1921614 result++;
460 }
461 return result;
462 }
463
464 /**
465 * \brief Casts a signed_index_t into an (unsigned) index_t.
466 * \details In debug mode, throws an assertion failure
467 * exception whenever \p x is negative.
468 */
469 static index_t to_unsigned_int(signed_index_t x) {
470 geo_debug_assert(x >= 0);
471 47745605 return (index_t) (x);
472 }
473
474 /**
475 * \brief Gets a bisector
476 * \param[in] i local index of the bisector
477 * \return the index of the Delaunay vertex that corresponds to
478 * the second extremity of the bisector
479 * \pre i < nb_bisectors()
480 */
481 index_t bisector(signed_index_t i) const {
482 geo_debug_assert(i < (signed_index_t) nb_bisectors());
483
2/28
✓ Branch 0 taken 30218722 times.
✓ Branch 1 taken 65551 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✗ Branch 15 not taken.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
✗ Branch 20 not taken.
✗ Branch 21 not taken.
✗ Branch 22 not taken.
✗ Branch 23 not taken.
✗ Branch 24 not taken.
✗ Branch 25 not taken.
✗ Branch 26 not taken.
✗ Branch 27 not taken.
 36108267 return to_unsigned_int((baseclass::end()[-1 - i]) - 1);
484 }
485
486 /**
487 * \brief Gets a boundary facet
488 * \param[in] i local index of the boundary facet
489 * \return the index of the mesh facet
490 * \pre i < nb_boundary_facets()
491 */
492 index_t boundary_facet(signed_index_t i) const {
493 geo_debug_assert(i < (signed_index_t) nb_boundary_facets());
494
6/14
✓ Branch 0 taken 10904483 times.
✓ Branch 1 taken 579158 times.
✓ Branch 2 taken 29685 times.
✓ Branch 3 taken 30315 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✓ Branch 6 taken 59327 times.
✓ Branch 7 taken 60085 times.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
 12010406 return to_unsigned_int(-(baseclass::begin()[i]) - 1);
495 }
496
497 /**
498 * \brief Tests whether a bisector is present in the
499 * symbolic representation this vertex.
500 * \param[in] i global index of the bisector
501 */
502 bool has_bisector(index_t i) const {
503 return baseclass::find(signed_index_t(i) + 1) != baseclass::end();
504 }
505
506 /**
507 * \brief Tests whether a boundary facet is present in the
508 * symbolic representation of this vertex.
509 * \param[in] i global index of the boundary facet
510 */
511 bool has_boundary_facet(index_t i) const {
512 return baseclass::find(-signed_index_t(i) - 1) != baseclass::end();
513 }
514
515 /**
516 * \brief Gets the global index of the boundary vertex that corresponds
517 * to this vertex.
518 * \pre nb_boundary_facets() == 3
519 */
520 index_t get_boundary_vertex() const {
521 geo_debug_assert(nb_boundary_facets() == 3);
522 geo_debug_assert(v1_ != 0);
523
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 183494 times.
 5052529 return v1_ - 1;
524 }
525
526 /**
527 * \brief Gets the global indices of the boundary vertices that
528 * define the boundary edge on which this vertex is located.
529 * \param[out] v1 index of the first extremity of the boundary edge
530 * \param[out] v2 index of the second extremity of the boundary edge
531 * \pre nb_boundary_facets() == 2
532 */
533 void get_boundary_edge(index_t& v1, index_t& v2) const {
534 geo_debug_assert(nb_boundary_facets() == 2);
535 geo_debug_assert(v1_ != 0);
536 geo_debug_assert(v2_ != 0);
537 6357867 v1 = v1_ - 1;
538 6357867 v2 = v2_ - 1;
539 }
540
541 /**
542 * \brief Sets the boundary vertex on which this vertex is located.
543 * \param[in] v global index of the boundary vertex
544 */
545 void set_boundary_vertex(index_t v) {
546 443516 v1_ = v + 1;
547 443372 v2_ = 0;
548 144 }
549
550 /**
551 * \brief Sets the boundary edge on which this vertex is located.
552 * \param[in] v1 global index of the first boundary vertex
553 * \param[in] v2 global index of the second boundary vertex
554 */
555 void set_boundary_edge(index_t v1, index_t v2) {
556 786428 v1_ = v1 + 1;
557 786428 v2_ = v2 + 1;
558 786428 }
559
560 /**
561 * \brief Copies a boundary edge from the symbolic representation
562 * of another vertex.
563 */
564 void copy_boundary_edge_from(const thisclass& rhs) {
565 geo_debug_assert(rhs.nb_boundary_facets() == 2);
566 geo_debug_assert(rhs.nb_bisectors() == 1);
567 geo_debug_assert(rhs.v1_ > 0);
568 geo_debug_assert(rhs.v2_ > 0);
569 510170 v1_ = rhs.v1_;
570 510170 v2_ = rhs.v2_;
571 510170 }
572
573 /**
574 * \brief Computes the symbolic representation of the intersection
575 * between a segment and a bisector.
576 * \details Computes the intersection between
577 * the segment [\p v1, \p v2] and the bisector \p E
578 *
579 * \return false if there was a problem
580 * (happens sometimes in finite precision mode)
581 */
582 1982204 bool intersect_symbolic(
583 const thisclass& v1,
584 const thisclass& v2,
585 index_t E
586 ) {
587
588 // Compute the symbolic representation as the intersection
589 // of three planes.
590 1982204 sets_intersect(v1, v2, *this);
591 // this computes the set of planes that contain
592 // the edge [v1,v2]
593
594 add_bisector(E); // the intersection is on E.
595
596 // Compute the symbolic representation as intersection between
597 // bisector and boundary edge
598 // (it's redundant and less elegant than the representation
599 // as planes interactions,
600 // but we need this to handle degenerate configurations properly,
601 // and to use exact predicates with original boundary vertices
602 // coordinates).
603
604
2/2
✓ Branch 0 taken 1296598 times.
✓ Branch 1 taken 685606 times.
 1982204 if(nb_boundary_facets() == 2) {
605 // If *this is on the intersection of two boundary facets,
606 // then *this is on
607 // a boundary edge, and we need to retrieve the indices of the
608 // two extremities of this boundary edge.
609
610 index_t nb1 = v1.nb_boundary_facets();
611 index_t nb2 = v2.nb_boundary_facets();
612
2/2
✓ Branch 0 taken 786428 times.
✓ Branch 1 taken 510170 times.
 1296598 if(nb1 == 3 && nb2 == 3) {
613 // If v1 and v2 are boundary vertices,
614 // then I is on the boundary
615 // edge that connects v1 and v2
616 set_boundary_edge(
617 v1.get_boundary_vertex(),
618 v2.get_boundary_vertex()
619 );
620
2/2
✓ Branch 0 taken 312024 times.
✓ Branch 1 taken 198146 times.
 510170 } else if(nb1 == 2) {
621 geo_debug_assert(nb_boundary_facets() == 2);
622 // If v1 is on a boundary edge,
623 // then I is on the same boundary edge as v1
624 copy_boundary_edge_from(v1);
625
1/2
✓ Branch 0 taken 198146 times.
✗ Branch 1 not taken.
 198146 } else if(nb2 == 2) {
626 geo_debug_assert(nb_boundary_facets() == 2);
627 // If v2 is on a boundary edge,
628 // then I is on the same boundary edge as v2
629 copy_boundary_edge_from(v2);
630 }
631 }
632
633 // Sanity check: problem detected here, we
634 // notify the caller that will use a workaround
635 // (see clip_by_plane())
636
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1982204 times.
 1982204 if(baseclass::size() != 3) {
637 ✗ return false;
638 }
639 return true;
640 }
641
642 private:
643 index_t v1_;
644 index_t v2_;
645 };
646
647
648 /**
649 * \brief An allocator for points that are created
650 * from intersections in GenericVoronoiDiagram.
651 *
652 * \details Implementation is an array of chunk. We do not use
653 * std::deque since we want to control the chunk size,
654 * and we want to clear it without deallocating
655 * memory to avoid many calls to memory allocator (which
656 * would probably slow down the Windows version a lot, there
657 * seems to be a global multithreading lock on malloc()).
658 *
659 * In most cases, only the first chunk is used
660 * (but some degenerate cases may use more). There seems
661 * to be no measurable overhead as compared to a contiguous
662 * array in our scenario.
663 *
664 * \note This is an internal implementation class, not meant to be
665 * used by client code.
666 */
667
668 class PointAllocator {
669 public:
670 /**
671 * \brief Creates a new empty PointAllocator.
672 * \param[in] dim dimension of the points to be allocated
673 */
674 748 PointAllocator(coord_index_t dim) :
675 748 size_(0),
676 748 capacity_(0),
677
17/280
✓ Branch 1 taken 18 times.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
✗ Branch 19 not taken.
✗ Branch 20 not taken.
✗ Branch 22 not taken.
✗ Branch 23 not taken.
✗ Branch 25 not taken.
✗ Branch 26 not taken.
✗ Branch 28 not taken.
✗ Branch 29 not taken.
✗ Branch 31 not taken.
✗ Branch 32 not taken.
✗ Branch 34 not taken.
✗ Branch 35 not taken.
✗ Branch 37 not taken.
✗ Branch 38 not taken.
✗ Branch 40 not taken.
✗ Branch 41 not taken.
✗ Branch 43 not taken.
✗ Branch 44 not taken.
✗ Branch 46 not taken.
✗ Branch 47 not taken.
✗ Branch 49 not taken.
✗ Branch 50 not taken.
✗ Branch 52 not taken.
✗ Branch 53 not taken.
✗ Branch 55 not taken.
✗ Branch 56 not taken.
✓ Branch 58 taken 1 times.
✗ Branch 59 not taken.
✗ Branch 61 not taken.
✗ Branch 62 not taken.
✗ Branch 64 not taken.
✗ Branch 65 not taken.
✗ Branch 67 not taken.
✗ Branch 68 not taken.
✗ Branch 70 not taken.
✗ Branch 71 not taken.
✗ Branch 73 not taken.
✗ Branch 74 not taken.
✗ Branch 76 not taken.
✗ Branch 77 not taken.
✗ Branch 79 not taken.
✗ Branch 80 not taken.
✗ Branch 82 not taken.
✗ Branch 83 not taken.
✗ Branch 85 not taken.
✗ Branch 86 not taken.
✗ Branch 88 not taken.
✗ Branch 89 not taken.
✗ Branch 91 not taken.
✗ Branch 92 not taken.
✗ Branch 94 not taken.
✗ Branch 95 not taken.
✗ Branch 97 not taken.
✗ Branch 98 not taken.
✗ Branch 100 not taken.
✗ Branch 101 not taken.
✓ Branch 103 taken 160 times.
✗ Branch 104 not taken.
✗ Branch 106 not taken.
✗ Branch 107 not taken.
✗ Branch 109 not taken.
✗ Branch 110 not taken.
✓ Branch 112 taken 1 times.
✗ Branch 113 not taken.
✗ Branch 115 not taken.
✗ Branch 116 not taken.
✗ Branch 118 not taken.
✗ Branch 119 not taken.
✗ Branch 121 not taken.
✗ Branch 122 not taken.
✗ Branch 124 not taken.
✗ Branch 125 not taken.
✗ Branch 127 not taken.
✗ Branch 128 not taken.
✗ Branch 130 not taken.
✗ Branch 131 not taken.
✗ Branch 133 not taken.
✗ Branch 134 not taken.
✗ Branch 136 not taken.
✗ Branch 137 not taken.
✗ Branch 139 not taken.
✗ Branch 140 not taken.
✗ Branch 142 not taken.
✗ Branch 143 not taken.
✗ Branch 145 not taken.
✗ Branch 146 not taken.
✗ Branch 148 not taken.
✗ Branch 149 not taken.
✗ Branch 151 not taken.
✗ Branch 152 not taken.
✗ Branch 154 not taken.
✗ Branch 155 not taken.
✓ Branch 157 taken 160 times.
✗ Branch 158 not taken.
✗ Branch 160 not taken.
✗ Branch 161 not taken.
✗ Branch 163 not taken.
✗ Branch 164 not taken.
✓ Branch 166 taken 1 times.
✗ Branch 167 not taken.
✗ Branch 169 not taken.
✗ Branch 170 not taken.
✗ Branch 172 not taken.
✗ Branch 173 not taken.
✗ Branch 175 not taken.
✗ Branch 176 not taken.
✗ Branch 178 not taken.
✗ Branch 179 not taken.
✗ Branch 181 not taken.
✗ Branch 182 not taken.
✗ Branch 184 not taken.
✗ Branch 185 not taken.
✗ Branch 187 not taken.
✗ Branch 188 not taken.
✗ Branch 190 not taken.
✗ Branch 191 not taken.
✗ Branch 193 not taken.
✗ Branch 194 not taken.
✗ Branch 196 not taken.
✗ Branch 197 not taken.
✗ Branch 199 not taken.
✗ Branch 200 not taken.
✗ Branch 202 not taken.
✗ Branch 203 not taken.
✗ Branch 205 not taken.
✗ Branch 206 not taken.
✗ Branch 208 not taken.
✗ Branch 209 not taken.
✓ Branch 211 taken 160 times.
✗ Branch 212 not taken.
✗ Branch 214 not taken.
✗ Branch 215 not taken.
✗ Branch 217 not taken.
✗ Branch 218 not taken.
✓ Branch 220 taken 1 times.
✗ Branch 221 not taken.
✗ Branch 223 not taken.
✗ Branch 224 not taken.
✗ Branch 226 not taken.
✗ Branch 227 not taken.
✗ Branch 229 not taken.
✗ Branch 230 not taken.
✗ Branch 232 not taken.
✗ Branch 233 not taken.
✗ Branch 235 not taken.
✗ Branch 236 not taken.
✗ Branch 238 not taken.
✗ Branch 239 not taken.
✗ Branch 241 not taken.
✗ Branch 242 not taken.
✗ Branch 244 not taken.
✗ Branch 245 not taken.
✗ Branch 247 not taken.
✗ Branch 248 not taken.
✗ Branch 250 not taken.
✗ Branch 251 not taken.
✗ Branch 253 not taken.
✗ Branch 254 not taken.
✗ Branch 256 not taken.
✗ Branch 257 not taken.
✗ Branch 259 not taken.
✗ Branch 260 not taken.
✗ Branch 262 not taken.
✗ Branch 263 not taken.
✓ Branch 265 taken 160 times.
✗ Branch 266 not taken.
✗ Branch 268 not taken.
✗ Branch 269 not taken.
✗ Branch 271 not taken.
✗ Branch 272 not taken.
✗ Branch 274 not taken.
✗ Branch 275 not taken.
✗ Branch 277 not taken.
✗ Branch 278 not taken.
✗ Branch 280 not taken.
✗ Branch 281 not taken.
✗ Branch 283 not taken.
✗ Branch 284 not taken.
✗ Branch 286 not taken.
✗ Branch 287 not taken.
✗ Branch 289 not taken.
✗ Branch 290 not taken.
✗ Branch 292 not taken.
✗ Branch 293 not taken.
✗ Branch 295 not taken.
✗ Branch 296 not taken.
✗ Branch 298 not taken.
✗ Branch 299 not taken.
✗ Branch 301 not taken.
✗ Branch 302 not taken.
✗ Branch 304 not taken.
✗ Branch 305 not taken.
✗ Branch 307 not taken.
✗ Branch 308 not taken.
✗ Branch 310 not taken.
✗ Branch 311 not taken.
✗ Branch 313 not taken.
✗ Branch 314 not taken.
✗ Branch 316 not taken.
✗ Branch 317 not taken.
✗ Branch 319 not taken.
✗ Branch 320 not taken.
✗ Branch 322 not taken.
✗ Branch 323 not taken.
✗ Branch 325 not taken.
✗ Branch 326 not taken.
✗ Branch 328 not taken.
✗ Branch 329 not taken.
✗ Branch 331 not taken.
✗ Branch 332 not taken.
✗ Branch 334 not taken.
✗ Branch 335 not taken.
✗ Branch 337 not taken.
✗ Branch 338 not taken.
✗ Branch 340 not taken.
✗ Branch 341 not taken.
✗ Branch 343 not taken.
✗ Branch 344 not taken.
✗ Branch 346 not taken.
✗ Branch 347 not taken.
✗ Branch 349 not taken.
✗ Branch 350 not taken.
✗ Branch 352 not taken.
✗ Branch 353 not taken.
✗ Branch 355 not taken.
✗ Branch 356 not taken.
✗ Branch 358 not taken.
✗ Branch 359 not taken.
✗ Branch 361 not taken.
✗ Branch 362 not taken.
✗ Branch 364 not taken.
✗ Branch 365 not taken.
✗ Branch 367 not taken.
✗ Branch 368 not taken.
✗ Branch 370 not taken.
✗ Branch 371 not taken.
✗ Branch 373 not taken.
✗ Branch 374 not taken.
✗ Branch 376 not taken.
✗ Branch 377 not taken.
✗ Branch 379 not taken.
✗ Branch 380 not taken.
✗ Branch 382 not taken.
✗ Branch 383 not taken.
✗ Branch 385 not taken.
✗ Branch 386 not taken.
✗ Branch 388 not taken.
✗ Branch 389 not taken.
✗ Branch 391 not taken.
✗ Branch 392 not taken.
✗ Branch 394 not taken.
✗ Branch 395 not taken.
✗ Branch 397 not taken.
✗ Branch 398 not taken.
✗ Branch 399 not taken.
✗ Branch 400 not taken.
✗ Branch 401 not taken.
✗ Branch 402 not taken.
✓ Branch 403 taken 1 times.
✓ Branch 404 taken 4 times.
✓ Branch 405 taken 5 times.
✓ Branch 406 taken 20 times.
✓ Branch 407 taken 1 times.
✓ Branch 408 taken 4 times.
✓ Branch 409 taken 39 times.
✓ Branch 410 taken 12 times.
✗ Branch 411 not taken.
✗ Branch 412 not taken.
 748 dimension_(dim) {
678 }
679
680 /**
681 * \brief Allocates a new point.
682 * \return a pointer to the coordinates of the new point. Memory
683 * ownership remains to this PointAllocator.
684 */
685 39607406 double* new_item() {
686
2/2
✓ Branch 0 taken 863 times.
✓ Branch 1 taken 39606543 times.
 39607406 if(size_ == capacity_) {
687 863 grow();
688 }
689 39607406 size_++;
690 39607406 return item(size_ - 1);
691 }
692
693 /**
694 * \brief Clears this PointAllocator.
695 */
696 void clear() {
697
2/14
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✓ Branch 2 taken 983108 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✓ Branch 6 taken 2319039 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
 4111590 size_ = 0;
698 }
699
700 /**
701 * \brief PointAllocator destructor
702 * \details This releases all allocated chunks.
703 */
704 748 ~PointAllocator() {
705
2/2
✓ Branch 0 taken 863 times.
✓ Branch 1 taken 748 times.
 2359 for(index_t c = 0; c < chunks_.size(); c++) {
706 863 GEO::Memory::aligned_free(chunks_[c]);
707 }
708 748 }
709
710 /**
711 * \brief Gets the dimension of the points stored in
712 * this PointAllocator.
713 */
714 coord_index_t dimension() const {
715 return dimension_;
716 }
717
718 protected:
719 /**
720 * \brief Constants that determine the size of a chunk.
721 */
722 enum {
723 CHUNK_SHIFT = 8,
724 CHUNK_SIZE = 1 << CHUNK_SHIFT,
725 CHUNK_MASK = CHUNK_SIZE - 1
726 };
727
728 /**
729 * \brief Allocates a new chunk of memory.
730 */
731 863 void grow() {
732 863 chunks_.push_back(
733 863 reinterpret_cast<double*>(
734 863 GEO::Memory::aligned_malloc(
735 863 index_t(CHUNK_SIZE) * dimension_ * sizeof(double)
736 )
737 )
738 );
739 863 capacity_ += CHUNK_SIZE;
740 863 }
741
742 /**
743 * \brief Gets a pointer to one of the allocated points from its index.
744 * \param[in] i the index of the point in this PointAllocator
745 * \return A pointer to the coordinates of the point
746 */
747 double* item(index_t i) {
748 geo_debug_assert(i < size_);
749 39607406 return &(chunks_[i >> CHUNK_SHIFT][(i & CHUNK_MASK) * dimension_]);
750 }
751
752 private:
753 index_t size_;
754 index_t capacity_;
755 coord_index_t dimension_;
756 std::vector<double*> chunks_;
757 };
758
759 /**
760 * \brief Flags associated with edges.
761 */
762 enum {
763 ORIGINAL = 1, /**< Edge belongs to the input surface */
764 INTERSECT = 2 /**< Edge was generated by an intersection */
765 };
766
767 /**
768 * \brief A set of EdgeFlags
769 * \details EdgeFlag%s are combined with bitewise or.
770 */
771 typedef index_t EdgeFlags;
772
773 /**
774 * \brief An individual edge flag
775 */
776 typedef index_t EdgeFlag;
777
778 /**
779 * \brief Internal representation of vertices
780 * in GenericVoronoiDiagram.
781 * \details Vertex has both
782 * geometrical and symbolic representations.
783 * \note This is an internal implementation class, not meant to be
784 * used by client code (except in some particular case, such as
785 * subclassing GEO::IntegrationSimplex).
786 */
787 class Vertex {
788
789 /** \brief This class type */
790 typedef Vertex thisclass;
791
792 public:
793 /**
794 * \brief Creates a new Vertex
795 * \param[in] p geometric location at the vertex, shared with caller
796 * \param[in] w weight
797 * \param[in] f facet of the input mesh this Vertex comes from
798 * \param[in] sym symbolic representation
799 */
800 Vertex(
801 const double* p, double w, signed_index_t f,
802 const SymbolicVertex& sym
803 ) :
804 point_(p),
805 weight_(w),
806 f_(f),
807 seed_(-1),
808 sym_(sym),
809 flags_(ORIGINAL) {
810 }
811
812 /**
813 * \brief Creates a new Vertex
814 * \param[in] p geometric location at the vertex, shared with caller
815 * \param[in] w weight
816 * \param[in] f facet of the input mesh this Vertex comes from
817 */
818 1300944 Vertex(const double* p, double w, signed_index_t f) :
819 1300944 point_(p),
820 1300944 weight_(w),
821 1300944 f_(f),
822 1300944 seed_(-1),
823 1300944 flags_(ORIGINAL) {
824 }
825
826 /**
827 * \brief Creates an uninitialized Vertex.
828 */
829 35041982 Vertex() :
830 11213067 point_(nullptr),
831 35041982 weight_(1.0),
832 35041982 f_(-1),
833 35041982 seed_(-1),
834 34028106 flags_(0) {
835 }
836
837 /**
838 * \brief Gets the geometric location at this Vertex.
839 * \return a const pointer to the coordinates
840 */
841 const double* point() const {
842
10/84
✓ Branch 0 taken 2012115 times.
✓ Branch 1 taken 17349 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 12435843 times.
✓ Branch 5 taken 1120473 times.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✓ Branch 8 taken 16753752 times.
✓ Branch 9 taken 1469872 times.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✓ Branch 12 taken 19426770 times.
✓ Branch 13 taken 1787026 times.
✗ Branch 14 not taken.
✗ Branch 15 not taken.
✓ Branch 16 taken 19199667 times.
✓ Branch 17 taken 1839873 times.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
✗ Branch 20 not taken.
✗ Branch 21 not taken.
✗ Branch 22 not taken.
✗ Branch 23 not taken.
✗ Branch 24 not taken.
✗ Branch 25 not taken.
✗ Branch 26 not taken.
✗ Branch 27 not taken.
✗ Branch 28 not taken.
✗ Branch 29 not taken.
✗ Branch 30 not taken.
✗ Branch 31 not taken.
✗ Branch 32 not taken.
✗ Branch 33 not taken.
✗ Branch 34 not taken.
✗ Branch 35 not taken.
✗ Branch 39 not taken.
✗ Branch 40 not taken.
✗ Branch 41 not taken.
✗ Branch 42 not taken.
✗ Branch 43 not taken.
✗ Branch 44 not taken.
✗ Branch 45 not taken.
✗ Branch 46 not taken.
✗ Branch 50 not taken.
✗ Branch 51 not taken.
✗ Branch 52 not taken.
✗ Branch 53 not taken.
✗ Branch 54 not taken.
✗ Branch 55 not taken.
✗ Branch 56 not taken.
✗ Branch 57 not taken.
✗ Branch 61 not taken.
✗ Branch 62 not taken.
✗ Branch 63 not taken.
✗ Branch 64 not taken.
✗ Branch 65 not taken.
✗ Branch 66 not taken.
✗ Branch 67 not taken.
✗ Branch 68 not taken.
✗ Branch 72 not taken.
✗ Branch 73 not taken.
✗ Branch 74 not taken.
✗ Branch 75 not taken.
✗ Branch 76 not taken.
✗ Branch 77 not taken.
✗ Branch 78 not taken.
✗ Branch 79 not taken.
✗ Branch 83 not taken.
✗ Branch 84 not taken.
✗ Branch 85 not taken.
✗ Branch 86 not taken.
✗ Branch 87 not taken.
✗ Branch 88 not taken.
✗ Branch 89 not taken.
✗ Branch 90 not taken.
✗ Branch 94 not taken.
✗ Branch 95 not taken.
✗ Branch 96 not taken.
✗ Branch 97 not taken.
✗ Branch 98 not taken.
✗ Branch 99 not taken.
✗ Branch 100 not taken.
✗ Branch 101 not taken.
 336793116 return point_;
843 }
844
845 /**
846 * \brief Sets the geometric location at this vertex.
847 * \param[in] p the geometric location, shared with caller
848 */
849 void set_point(const double* p) {
850
4/14
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✓ Branch 2 taken 178947 times.
✓ Branch 3 taken 6924578 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✓ Branch 6 taken 408400 times.
✓ Branch 7 taken 16316990 times.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
 27103107 point_ = p;
851 }
852
853 /**
854 * \brief Gets Vertex weight.
855 * \details Used by non-uniform centroidal
856 * Voronoi tesselation.
857 */
858 double weight() const {
859
4/14
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✓ Branch 2 taken 3550344 times.
✓ Branch 3 taken 3553181 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✓ Branch 6 taken 8362695 times.
✓ Branch 7 taken 8362695 times.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
 23865263 return weight_;
860 }
861
862 /**
863 * \brief Sets the vertex weight.
864 * \details Used by non-uniform centroidal
865 * Voronoi tesselation..
866 */
867 void set_weight(double w) {
868
6/14
✓ Branch 0 taken 144 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 3550344 times.
✓ Branch 3 taken 3553181 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 19547 times.
✓ Branch 6 taken 9152573 times.
✓ Branch 7 taken 8362695 times.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
 24674832 weight_ = w;
869 }
870
871 /**
872 * \brief Gets the adjacent seed.
873 * \return the global index of the adjacent seed
874 */
875 signed_index_t adjacent_seed() const {
876
12/378
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✓ Branch 6 taken 194 times.
✓ Branch 7 taken 176836 times.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✗ Branch 15 not taken.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
✗ Branch 20 not taken.
✗ Branch 21 not taken.
✗ Branch 22 not taken.
✗ Branch 23 not taken.
✗ Branch 24 not taken.
✗ Branch 25 not taken.
✗ Branch 26 not taken.
✗ Branch 27 not taken.
✗ Branch 28 not taken.
✗ Branch 29 not taken.
✗ Branch 30 not taken.
✗ Branch 31 not taken.
✗ Branch 32 not taken.
✗ Branch 33 not taken.
✗ Branch 34 not taken.
✗ Branch 35 not taken.
✗ Branch 36 not taken.
✗ Branch 37 not taken.
✗ Branch 38 not taken.
✗ Branch 39 not taken.
✗ Branch 40 not taken.
✗ Branch 41 not taken.
✗ Branch 42 not taken.
✗ Branch 43 not taken.
✗ Branch 44 not taken.
✗ Branch 45 not taken.
✗ Branch 46 not taken.
✗ Branch 47 not taken.
✗ Branch 48 not taken.
✗ Branch 49 not taken.
✗ Branch 50 not taken.
✗ Branch 51 not taken.
✗ Branch 52 not taken.
✗ Branch 53 not taken.
✗ Branch 54 not taken.
✗ Branch 55 not taken.
✗ Branch 56 not taken.
✗ Branch 57 not taken.
✗ Branch 58 not taken.
✗ Branch 59 not taken.
✗ Branch 60 not taken.
✗ Branch 61 not taken.
✗ Branch 62 not taken.
✗ Branch 63 not taken.
✗ Branch 64 not taken.
✗ Branch 65 not taken.
✗ Branch 66 not taken.
✗ Branch 67 not taken.
✗ Branch 68 not taken.
✗ Branch 69 not taken.
✓ Branch 70 taken 421696 times.
✓ Branch 71 taken 419315 times.
✗ Branch 72 not taken.
✗ Branch 73 not taken.
✗ Branch 74 not taken.
✗ Branch 75 not taken.
✗ Branch 76 not taken.
✗ Branch 77 not taken.
✗ Branch 78 not taken.
✗ Branch 79 not taken.
✓ Branch 80 taken 76570 times.
✓ Branch 81 taken 17944 times.
✗ Branch 82 not taken.
✗ Branch 83 not taken.
✗ Branch 84 not taken.
✗ Branch 85 not taken.
✗ Branch 86 not taken.
✗ Branch 87 not taken.
✗ Branch 88 not taken.
✗ Branch 89 not taken.
✗ Branch 90 not taken.
✗ Branch 91 not taken.
✗ Branch 92 not taken.
✗ Branch 93 not taken.
✗ Branch 94 not taken.
✗ Branch 95 not taken.
✗ Branch 96 not taken.
✗ Branch 97 not taken.
✗ Branch 98 not taken.
✗ Branch 99 not taken.
✗ Branch 100 not taken.
✗ Branch 101 not taken.
✗ Branch 102 not taken.
✗ Branch 103 not taken.
✗ Branch 104 not taken.
✗ Branch 105 not taken.
✗ Branch 106 not taken.
✗ Branch 107 not taken.
✗ Branch 108 not taken.
✗ Branch 109 not taken.
✓ Branch 110 taken 3070758 times.
✓ Branch 111 taken 726190 times.
✗ Branch 112 not taken.
✗ Branch 113 not taken.
✗ Branch 114 not taken.
✗ Branch 115 not taken.
✗ Branch 116 not taken.
✗ Branch 117 not taken.
✗ Branch 118 not taken.
✗ Branch 119 not taken.
✗ Branch 120 not taken.
✗ Branch 121 not taken.
✗ Branch 122 not taken.
✗ Branch 123 not taken.
✗ Branch 124 not taken.
✗ Branch 125 not taken.
✗ Branch 126 not taken.
✗ Branch 127 not taken.
✗ Branch 128 not taken.
✗ Branch 129 not taken.
✗ Branch 130 not taken.
✗ Branch 131 not taken.
✗ Branch 132 not taken.
✗ Branch 133 not taken.
✗ Branch 134 not taken.
✗ Branch 135 not taken.
✗ Branch 136 not taken.
✗ Branch 137 not taken.
✗ Branch 138 not taken.
✗ Branch 139 not taken.
✗ Branch 140 not taken.
✗ Branch 141 not taken.
✗ Branch 142 not taken.
✗ Branch 143 not taken.
✗ Branch 144 not taken.
✗ Branch 145 not taken.
✗ Branch 146 not taken.
✗ Branch 147 not taken.
✗ Branch 148 not taken.
✗ Branch 149 not taken.
✗ Branch 150 not taken.
✗ Branch 151 not taken.
✗ Branch 152 not taken.
✗ Branch 153 not taken.
✗ Branch 154 not taken.
✗ Branch 155 not taken.
✗ Branch 156 not taken.
✗ Branch 157 not taken.
✗ Branch 158 not taken.
✗ Branch 159 not taken.
✗ Branch 160 not taken.
✗ Branch 161 not taken.
✗ Branch 162 not taken.
✗ Branch 163 not taken.
✗ Branch 164 not taken.
✗ Branch 165 not taken.
✗ Branch 166 not taken.
✗ Branch 167 not taken.
✗ Branch 168 not taken.
✗ Branch 169 not taken.
✗ Branch 170 not taken.
✗ Branch 171 not taken.
✗ Branch 172 not taken.
✗ Branch 173 not taken.
✗ Branch 174 not taken.
✗ Branch 175 not taken.
✗ Branch 176 not taken.
✗ Branch 177 not taken.
✗ Branch 178 not taken.
✗ Branch 179 not taken.
✗ Branch 180 not taken.
✗ Branch 181 not taken.
✗ Branch 182 not taken.
✗ Branch 183 not taken.
✓ Branch 184 taken 177494 times.
✓ Branch 185 taken 80102 times.
✗ Branch 186 not taken.
✗ Branch 187 not taken.
✗ Branch 188 not taken.
✗ Branch 189 not taken.
✗ Branch 190 not taken.
✗ Branch 191 not taken.
✗ Branch 192 not taken.
✗ Branch 193 not taken.
✗ Branch 194 not taken.
✗ Branch 195 not taken.
✗ Branch 196 not taken.
✗ Branch 197 not taken.
✗ Branch 198 not taken.
✗ Branch 199 not taken.
✗ Branch 200 not taken.
✗ Branch 201 not taken.
✗ Branch 202 not taken.
✗ Branch 203 not taken.
✗ Branch 204 not taken.
✗ Branch 205 not taken.
✗ Branch 206 not taken.
✗ Branch 207 not taken.
✗ Branch 208 not taken.
✗ Branch 209 not taken.
✗ Branch 210 not taken.
✗ Branch 211 not taken.
✗ Branch 212 not taken.
✗ Branch 213 not taken.
✓ Branch 214 taken 7121461 times.
✓ Branch 215 taken 3226795 times.
✗ Branch 216 not taken.
✗ Branch 217 not taken.
✗ Branch 218 not taken.
✗ Branch 219 not taken.
✗ Branch 220 not taken.
✗ Branch 221 not taken.
✗ Branch 222 not taken.
✗ Branch 223 not taken.
✗ Branch 224 not taken.
✗ Branch 225 not taken.
✗ Branch 226 not taken.
✗ Branch 227 not taken.
✗ Branch 228 not taken.
✗ Branch 229 not taken.
✗ Branch 230 not taken.
✗ Branch 231 not taken.
✗ Branch 232 not taken.
✗ Branch 233 not taken.
✗ Branch 234 not taken.
✗ Branch 235 not taken.
✗ Branch 236 not taken.
✗ Branch 237 not taken.
✗ Branch 238 not taken.
✗ Branch 239 not taken.
✗ Branch 240 not taken.
✗ Branch 241 not taken.
✗ Branch 242 not taken.
✗ Branch 243 not taken.
✗ Branch 244 not taken.
✗ Branch 245 not taken.
✗ Branch 246 not taken.
✗ Branch 247 not taken.
✗ Branch 248 not taken.
✗ Branch 249 not taken.
✗ Branch 250 not taken.
✗ Branch 251 not taken.
✗ Branch 252 not taken.
✗ Branch 253 not taken.
✗ Branch 254 not taken.
✗ Branch 255 not taken.
✗ Branch 256 not taken.
✗ Branch 257 not taken.
✗ Branch 258 not taken.
✗ Branch 259 not taken.
✗ Branch 260 not taken.
✗ Branch 261 not taken.
✗ Branch 262 not taken.
✗ Branch 263 not taken.
✗ Branch 264 not taken.
✗ Branch 265 not taken.
✗ Branch 266 not taken.
✗ Branch 267 not taken.
✗ Branch 268 not taken.
✗ Branch 269 not taken.
✗ Branch 270 not taken.
✗ Branch 271 not taken.
✗ Branch 272 not taken.
✗ Branch 273 not taken.
✗ Branch 274 not taken.
✗ Branch 275 not taken.
✗ Branch 276 not taken.
✗ Branch 277 not taken.
✗ Branch 278 not taken.
✗ Branch 279 not taken.
✗ Branch 280 not taken.
✗ Branch 281 not taken.
✗ Branch 282 not taken.
✗ Branch 283 not taken.
✗ Branch 284 not taken.
✗ Branch 285 not taken.
✗ Branch 286 not taken.
✗ Branch 287 not taken.
✗ Branch 288 not taken.
✗ Branch 289 not taken.
✗ Branch 290 not taken.
✗ Branch 291 not taken.
✗ Branch 292 not taken.
✗ Branch 293 not taken.
✗ Branch 294 not taken.
✗ Branch 295 not taken.
✗ Branch 296 not taken.
✗ Branch 297 not taken.
✗ Branch 298 not taken.
✗ Branch 299 not taken.
✗ Branch 300 not taken.
✗ Branch 301 not taken.
✗ Branch 302 not taken.
✗ Branch 303 not taken.
✗ Branch 304 not taken.
✗ Branch 305 not taken.
✗ Branch 306 not taken.
✗ Branch 307 not taken.
✗ Branch 308 not taken.
✗ Branch 309 not taken.
✗ Branch 310 not taken.
✗ Branch 311 not taken.
✗ Branch 312 not taken.
✗ Branch 313 not taken.
✗ Branch 314 not taken.
✗ Branch 315 not taken.
✗ Branch 316 not taken.
✗ Branch 317 not taken.
✗ Branch 318 not taken.
✗ Branch 319 not taken.
✗ Branch 320 not taken.
✗ Branch 321 not taken.
✗ Branch 322 not taken.
✗ Branch 323 not taken.
✗ Branch 324 not taken.
✗ Branch 325 not taken.
✗ Branch 326 not taken.
✗ Branch 327 not taken.
✗ Branch 328 not taken.
✗ Branch 329 not taken.
✗ Branch 330 not taken.
✗ Branch 331 not taken.
✗ Branch 332 not taken.
✗ Branch 333 not taken.
✗ Branch 334 not taken.
✗ Branch 335 not taken.
✗ Branch 336 not taken.
✗ Branch 337 not taken.
✗ Branch 338 not taken.
✗ Branch 339 not taken.
✗ Branch 340 not taken.
✗ Branch 341 not taken.
✗ Branch 342 not taken.
✗ Branch 343 not taken.
✗ Branch 344 not taken.
✗ Branch 345 not taken.
✗ Branch 346 not taken.
✗ Branch 347 not taken.
✗ Branch 348 not taken.
✗ Branch 349 not taken.
✗ Branch 350 not taken.
✗ Branch 351 not taken.
✗ Branch 352 not taken.
✗ Branch 353 not taken.
✗ Branch 354 not taken.
✗ Branch 355 not taken.
✗ Branch 356 not taken.
✗ Branch 357 not taken.
✗ Branch 358 not taken.
✗ Branch 359 not taken.
✗ Branch 360 not taken.
✗ Branch 361 not taken.
✗ Branch 362 not taken.
✗ Branch 363 not taken.
✗ Branch 364 not taken.
✗ Branch 365 not taken.
✗ Branch 366 not taken.
✗ Branch 367 not taken.
✗ Branch 368 not taken.
✗ Branch 369 not taken.
✗ Branch 370 not taken.
✗ Branch 371 not taken.
✗ Branch 372 not taken.
✗ Branch 373 not taken.
✗ Branch 374 not taken.
✗ Branch 375 not taken.
✗ Branch 376 not taken.
✗ Branch 377 not taken.
 15515355 return seed_;
877 }
878
879 /**
880 * \brief Sets the adjacent seed.
881 * \param[in] s the global index of the adjacent seed
882 */
883 void set_adjacent_seed(signed_index_t s) {
884 24842791 seed_ = s;
885 12419977 }
886
887 /** Symbolic representation */
888
889 /**
890 * \brief Gets the symbolic representation.
891 */
892 const SymbolicVertex& sym() const {
893 2963952 return sym_;
894 }
895
896 /**
897 * \brief Gets the symbolic representation.
898 */
899 SymbolicVertex& sym() {
900 380981 return sym_;
901 }
902
903 /**
904 * \brief Gets the adjacent facet.
905 * \return the global index of the adjacent facet
906 */
907 signed_index_t adjacent_facet() const {
908
16/378
✓ Branch 0 taken 362947 times.
✓ Branch 1 taken 2237 times.
✓ Branch 2 taken 362947 times.
✓ Branch 3 taken 2237 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✓ Branch 6 taken 177030 times.
✓ Branch 7 taken 79212 times.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✗ Branch 15 not taken.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
✗ Branch 20 not taken.
✗ Branch 21 not taken.
✗ Branch 22 not taken.
✗ Branch 23 not taken.
✗ Branch 24 not taken.
✗ Branch 25 not taken.
✗ Branch 26 not taken.
✗ Branch 27 not taken.
✗ Branch 28 not taken.
✗ Branch 29 not taken.
✗ Branch 30 not taken.
✗ Branch 31 not taken.
✗ Branch 32 not taken.
✗ Branch 33 not taken.
✗ Branch 34 not taken.
✗ Branch 35 not taken.
✗ Branch 36 not taken.
✗ Branch 37 not taken.
✗ Branch 38 not taken.
✗ Branch 39 not taken.
✗ Branch 40 not taken.
✗ Branch 41 not taken.
✗ Branch 42 not taken.
✗ Branch 43 not taken.
✗ Branch 44 not taken.
✗ Branch 45 not taken.
✗ Branch 46 not taken.
✗ Branch 47 not taken.
✗ Branch 48 not taken.
✗ Branch 49 not taken.
✗ Branch 50 not taken.
✗ Branch 51 not taken.
✗ Branch 52 not taken.
✗ Branch 53 not taken.
✗ Branch 54 not taken.
✗ Branch 55 not taken.
✗ Branch 56 not taken.
✗ Branch 57 not taken.
✗ Branch 58 not taken.
✗ Branch 59 not taken.
✗ Branch 60 not taken.
✗ Branch 61 not taken.
✗ Branch 62 not taken.
✗ Branch 63 not taken.
✗ Branch 64 not taken.
✗ Branch 65 not taken.
✗ Branch 66 not taken.
✗ Branch 67 not taken.
✗ Branch 68 not taken.
✗ Branch 69 not taken.
✓ Branch 70 taken 414883 times.
✓ Branch 71 taken 426128 times.
✗ Branch 72 not taken.
✗ Branch 73 not taken.
✗ Branch 74 not taken.
✗ Branch 75 not taken.
✗ Branch 76 not taken.
✗ Branch 77 not taken.
✗ Branch 78 not taken.
✗ Branch 79 not taken.
✓ Branch 80 taken 17944 times.
✓ Branch 81 taken 76570 times.
✗ Branch 82 not taken.
✗ Branch 83 not taken.
✗ Branch 84 not taken.
✗ Branch 85 not taken.
✗ Branch 86 not taken.
✗ Branch 87 not taken.
✗ Branch 88 not taken.
✗ Branch 89 not taken.
✗ Branch 90 not taken.
✗ Branch 91 not taken.
✗ Branch 92 not taken.
✗ Branch 93 not taken.
✗ Branch 94 not taken.
✗ Branch 95 not taken.
✗ Branch 96 not taken.
✗ Branch 97 not taken.
✗ Branch 98 not taken.
✗ Branch 99 not taken.
✗ Branch 100 not taken.
✗ Branch 101 not taken.
✗ Branch 102 not taken.
✗ Branch 103 not taken.
✗ Branch 104 not taken.
✗ Branch 105 not taken.
✗ Branch 106 not taken.
✗ Branch 107 not taken.
✗ Branch 108 not taken.
✗ Branch 109 not taken.
✓ Branch 110 taken 620542 times.
✓ Branch 111 taken 3176406 times.
✗ Branch 112 not taken.
✗ Branch 113 not taken.
✗ Branch 114 not taken.
✗ Branch 115 not taken.
✗ Branch 116 not taken.
✗ Branch 117 not taken.
✗ Branch 118 not taken.
✗ Branch 119 not taken.
✗ Branch 120 not taken.
✗ Branch 121 not taken.
✗ Branch 122 not taken.
✗ Branch 123 not taken.
✗ Branch 124 not taken.
✗ Branch 125 not taken.
✗ Branch 126 not taken.
✗ Branch 127 not taken.
✗ Branch 128 not taken.
✗ Branch 129 not taken.
✗ Branch 130 not taken.
✗ Branch 131 not taken.
✗ Branch 132 not taken.
✗ Branch 133 not taken.
✗ Branch 134 not taken.
✗ Branch 135 not taken.
✗ Branch 136 not taken.
✗ Branch 137 not taken.
✗ Branch 138 not taken.
✗ Branch 139 not taken.
✗ Branch 140 not taken.
✗ Branch 141 not taken.
✗ Branch 142 not taken.
✗ Branch 143 not taken.
✗ Branch 144 not taken.
✗ Branch 145 not taken.
✗ Branch 146 not taken.
✗ Branch 147 not taken.
✗ Branch 148 not taken.
✗ Branch 149 not taken.
✗ Branch 150 not taken.
✗ Branch 151 not taken.
✗ Branch 152 not taken.
✗ Branch 153 not taken.
✗ Branch 154 not taken.
✗ Branch 155 not taken.
✗ Branch 156 not taken.
✗ Branch 157 not taken.
✗ Branch 158 not taken.
✗ Branch 159 not taken.
✗ Branch 160 not taken.
✗ Branch 161 not taken.
✗ Branch 162 not taken.
✗ Branch 163 not taken.
✗ Branch 164 not taken.
✗ Branch 165 not taken.
✗ Branch 166 not taken.
✗ Branch 167 not taken.
✗ Branch 168 not taken.
✗ Branch 169 not taken.
✗ Branch 170 not taken.
✗ Branch 171 not taken.
✗ Branch 172 not taken.
✗ Branch 173 not taken.
✗ Branch 174 not taken.
✗ Branch 175 not taken.
✗ Branch 176 not taken.
✗ Branch 177 not taken.
✗ Branch 178 not taken.
✗ Branch 179 not taken.
✗ Branch 180 not taken.
✗ Branch 181 not taken.
✗ Branch 182 not taken.
✗ Branch 183 not taken.
✓ Branch 184 taken 79730 times.
✓ Branch 185 taken 177866 times.
✗ Branch 186 not taken.
✗ Branch 187 not taken.
✗ Branch 188 not taken.
✗ Branch 189 not taken.
✗ Branch 190 not taken.
✗ Branch 191 not taken.
✗ Branch 192 not taken.
✗ Branch 193 not taken.
✗ Branch 194 not taken.
✗ Branch 195 not taken.
✗ Branch 196 not taken.
✗ Branch 197 not taken.
✗ Branch 198 not taken.
✗ Branch 199 not taken.
✗ Branch 200 not taken.
✗ Branch 201 not taken.
✗ Branch 202 not taken.
✗ Branch 203 not taken.
✗ Branch 204 not taken.
✗ Branch 205 not taken.
✗ Branch 206 not taken.
✗ Branch 207 not taken.
✗ Branch 208 not taken.
✗ Branch 209 not taken.
✗ Branch 210 not taken.
✗ Branch 211 not taken.
✗ Branch 212 not taken.
✗ Branch 213 not taken.
✓ Branch 214 taken 3138330 times.
✓ Branch 215 taken 7209926 times.
✗ Branch 216 not taken.
✗ Branch 217 not taken.
✗ Branch 218 not taken.
✗ Branch 219 not taken.
✗ Branch 220 not taken.
✗ Branch 221 not taken.
✗ Branch 222 not taken.
✗ Branch 223 not taken.
✗ Branch 224 not taken.
✗ Branch 225 not taken.
✗ Branch 226 not taken.
✗ Branch 227 not taken.
✗ Branch 228 not taken.
✗ Branch 229 not taken.
✗ Branch 230 not taken.
✗ Branch 231 not taken.
✗ Branch 232 not taken.
✗ Branch 233 not taken.
✗ Branch 234 not taken.
✗ Branch 235 not taken.
✗ Branch 236 not taken.
✗ Branch 237 not taken.
✗ Branch 238 not taken.
✗ Branch 239 not taken.
✗ Branch 240 not taken.
✗ Branch 241 not taken.
✗ Branch 242 not taken.
✗ Branch 243 not taken.
✗ Branch 244 not taken.
✗ Branch 245 not taken.
✗ Branch 246 not taken.
✗ Branch 247 not taken.
✗ Branch 248 not taken.
✗ Branch 249 not taken.
✗ Branch 250 not taken.
✗ Branch 251 not taken.
✗ Branch 252 not taken.
✗ Branch 253 not taken.
✗ Branch 254 not taken.
✗ Branch 255 not taken.
✗ Branch 256 not taken.
✗ Branch 257 not taken.
✗ Branch 258 not taken.
✗ Branch 259 not taken.
✗ Branch 260 not taken.
✗ Branch 261 not taken.
✗ Branch 262 not taken.
✗ Branch 263 not taken.
✗ Branch 264 not taken.
✗ Branch 265 not taken.
✗ Branch 266 not taken.
✗ Branch 267 not taken.
✗ Branch 268 not taken.
✗ Branch 269 not taken.
✗ Branch 270 not taken.
✗ Branch 271 not taken.
✗ Branch 272 not taken.
✗ Branch 273 not taken.
✗ Branch 274 not taken.
✗ Branch 275 not taken.
✗ Branch 276 not taken.
✗ Branch 277 not taken.
✗ Branch 278 not taken.
✗ Branch 279 not taken.
✗ Branch 280 not taken.
✗ Branch 281 not taken.
✗ Branch 282 not taken.
✗ Branch 283 not taken.
✗ Branch 284 not taken.
✗ Branch 285 not taken.
✗ Branch 286 not taken.
✗ Branch 287 not taken.
✗ Branch 288 not taken.
✗ Branch 289 not taken.
✗ Branch 290 not taken.
✗ Branch 291 not taken.
✗ Branch 292 not taken.
✗ Branch 293 not taken.
✗ Branch 294 not taken.
✗ Branch 295 not taken.
✗ Branch 296 not taken.
✗ Branch 297 not taken.
✗ Branch 298 not taken.
✗ Branch 299 not taken.
✗ Branch 300 not taken.
✗ Branch 301 not taken.
✗ Branch 302 not taken.
✗ Branch 303 not taken.
✗ Branch 304 not taken.
✗ Branch 305 not taken.
✗ Branch 306 not taken.
✗ Branch 307 not taken.
✗ Branch 308 not taken.
✗ Branch 309 not taken.
✗ Branch 310 not taken.
✗ Branch 311 not taken.
✗ Branch 312 not taken.
✗ Branch 313 not taken.
✗ Branch 314 not taken.
✗ Branch 315 not taken.
✗ Branch 316 not taken.
✗ Branch 317 not taken.
✗ Branch 318 not taken.
✗ Branch 319 not taken.
✗ Branch 320 not taken.
✗ Branch 321 not taken.
✗ Branch 322 not taken.
✗ Branch 323 not taken.
✗ Branch 324 not taken.
✗ Branch 325 not taken.
✗ Branch 326 not taken.
✗ Branch 327 not taken.
✗ Branch 328 not taken.
✗ Branch 329 not taken.
✗ Branch 330 not taken.
✗ Branch 331 not taken.
✗ Branch 332 not taken.
✗ Branch 333 not taken.
✗ Branch 334 not taken.
✗ Branch 335 not taken.
✗ Branch 336 not taken.
✗ Branch 337 not taken.
✗ Branch 338 not taken.
✗ Branch 339 not taken.
✗ Branch 340 not taken.
✗ Branch 341 not taken.
✗ Branch 342 not taken.
✗ Branch 343 not taken.
✗ Branch 344 not taken.
✗ Branch 345 not taken.
✗ Branch 346 not taken.
✗ Branch 347 not taken.
✗ Branch 348 not taken.
✗ Branch 349 not taken.
✗ Branch 350 not taken.
✗ Branch 351 not taken.
✗ Branch 352 not taken.
✗ Branch 353 not taken.
✗ Branch 354 not taken.
✗ Branch 355 not taken.
✗ Branch 356 not taken.
✗ Branch 357 not taken.
✗ Branch 358 not taken.
✗ Branch 359 not taken.
✗ Branch 360 not taken.
✗ Branch 361 not taken.
✗ Branch 362 not taken.
✗ Branch 363 not taken.
✗ Branch 364 not taken.
✗ Branch 365 not taken.
✗ Branch 366 not taken.
✗ Branch 367 not taken.
✗ Branch 368 not taken.
✗ Branch 369 not taken.
✗ Branch 370 not taken.
✗ Branch 371 not taken.
✗ Branch 372 not taken.
✗ Branch 373 not taken.
✗ Branch 374 not taken.
✗ Branch 375 not taken.
✗ Branch 376 not taken.
✗ Branch 377 not taken.
 16324935 return f_;
909 }
910
911 /**
912 * \brief Sets the adjacent facet.
913 * \param[in] f the global index of the adjacent facet
914 */
915 void set_adjacent_facet(signed_index_t f) {
916 12419977 f_ = f;
917 }
918
919 /**
920 * \brief Implicit conversion that accesses the geometric location.
921 * \details With this implicit conversions, we can have template
922 * arguments for RestrictedVoronoiDiagram that take
923 * const double* as arguments instead of Vertices.
924 * \return a const pointer to the coordinates
925 */
926 operator const double* () const {
927 13945587 return point_;
928 }
929
930 /**
931 * \brief Clears this Vertex.
932 */
933 void clear() {
934 flags_ = 0;
935 f_ = -1;
936 }
937
938 /**
939 * \brief Sets an EdgeFlag in this Vertex.
940 */
941 void set_flag(EdgeFlag f) {
942 12422814 flags_ |= f;
943 }
944
945 /**
946 * \brief Resets an EdgeFlag in this Vertex.
947 */
948 void unset_flag(EdgeFlag f) {
949 flags_ &= ~f;
950 }
951
952 /**
953 * \brief Tests an EdgeFlag in this Vertex.
954 */
955 bool check_flag(EdgeFlag f) const {
956 return (flags_ & f) != 0;
957 }
958
959 /**
960 * \brief Copies adjacent facet and edge flags from another Vertex.
961 */
962 void copy_edge_from(const Vertex& rhs) {
963 set_adjacent_facet(rhs.adjacent_facet());
964 12419977 flags_ = rhs.flags_;
965 }
966
967 /**
968 * \brief Computes the intersection between
969 * a segment and a bisector.
970 * \details Computes the intersection between
971 * the segment [vq1, vq2] and the bisector
972 * of [p1,p2]..
973 * \tparam DIM dimension, specified as a template
974 * argument for efficiency considerations
975 */
976 template <index_t DIM>
977 31520634 void intersect_geom(
978 PointAllocator& target_intersections,
979 const Vertex& vq1, const Vertex& vq2,
980 const double* p1, const double* p2
981 ) {
982 const double* q1 = vq1.point();
983 const double* q2 = vq2.point();
984 31520634 double* Ipoint = target_intersections.new_item();
985 set_point(Ipoint);
986 double d = 0.0, l1 = 0.0, l2 = 0.0;
987
2/2
✓ Branch 0 taken 85054517 times.
✓ Branch 1 taken 15778491 times.
 201520624 for(coord_index_t c = 0; c < DIM; ++c) {
988 169999990 double n = p1[c] - p2[c];
989 169999990 d -= n * (p2[c] + p1[c]);
990 169999990 l1 += q2[c] * n;
991 169999990 l2 += q1[c] * n;
992 }
993 31520634 d = 0.5 * d;
994 31520634 l1 = ::fabs(l1 + d);
995 31520634 l2 = ::fabs(l2 + d);
996 31520634 double l12 = l1 + l2;
997
2/2
✓ Branch 0 taken 15736831 times.
✓ Branch 1 taken 41660 times.
 31520634 if(l12 > 1e-30) {
998 31437314 l1 /= l12;
999 31437314 l2 /= l12;
1000 } else {
1001 l1 = 0.5;
1002 l2 = 0.5;
1003 }
1004
2/2
✓ Branch 0 taken 85054517 times.
✓ Branch 1 taken 15778491 times.
 201520624 for(coord_index_t c = 0; c < DIM; ++c) {
1005 169999990 Ipoint[c] = l1 * q1[c] + l2 * q2[c];
1006 }
1007 31520634 set_weight(l1 * vq1.weight() + l2 * vq2.weight());
1008 31520634 }
1009
1010 /**
1011 * \brief Computes the side of this vertex relative
1012 * to a bisector.
1013 * \details This version is not exact.
1014 * \param[in] p1 first extremity of the bisector
1015 * \param[in] p2 second extremity of the bisector
1016 * \return POSITIVE if this vertex is on p1's side,
1017 * NEGATIVE if this vertex is on p2's side, and ZERO
1018 * if this vertex is on the bisector of [p1,p2].
1019 */
1020 template <index_t DIM>
1021 41891537 Sign side_fast(
1022 const double* p1, const double* p2
1023 ) const {
1024 double r = 0.0;
1025
2/2
✓ Branch 0 taken 116516526 times.
✓ Branch 1 taken 20954589 times.
 274871666 for(index_t c = 0; c < DIM; ++c) {
1026 232980129 r += GEO::geo_sqr(p2[c] - point()[c]);
1027 232980129 r -= GEO::geo_sqr(p1[c] - point()[c]);
1028 }
1029 41891537 return GEO::geo_sgn(r);
1030 }
1031
1032 private:
1033 const double* point_;
1034 double weight_;
1035
1036 /**
1037 * The facet adjacent to the edge
1038 * incident to this vertex.
1039 */
1040 signed_index_t f_;
1041
1042 /**
1043 * indicates the seed of the bisector that generated the
1044 * edge that has this vertex and the previous one as
1045 * extremities (or -1 if border).
1046 */
1047 signed_index_t seed_;
1048
1049 /** The symbolic representation of this vertex. */
1050 SymbolicVertex sym_;
1051
1052 /**
1053 * Indicates the type of edge
1054 * (virtual, original or intersection).
1055 */
1056 EdgeFlags flags_;
1057 };
1058 }
1059
1060 #endif
1061