Geogram Version 1.9.2
A programming library of geometric algorithms
Loading...
Searching...
No Matches
generic_RVD_utils.h
Go to the documentation of this file.
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_UTILS
41#define GEOGRAM_VORONOI_GENERIC_RVD_UTILS
42
48#include <stack>
49#include <vector>
50
57namespace GEOGen {
58
68 template <class T>
70 public:
74 void push(const T& x) {
75 rep_.push_back(x);
76 }
77
82 void pop() {
83 rep_.pop_back();
84 }
85
91 const T& top() const {
92 return *rep_.rbegin();
93 }
94
98 bool empty() const {
99 return rep_.size() == 0;
100 }
101
102 private:
103 GEO::vector<T> rep_;
104 };
105
106 /************************************************************************/
107
114 struct FacetSeed {
115
121 FacetSeed(index_t f_in, index_t seed_in) :
122 f(f_in),
123 seed(seed_in) {
124 }
125
131 }
132
138 bool operator< (const FacetSeed& rhs) const {
139 if(f < rhs.f) {
140 return true;
141 }
142 if(f > rhs.f) {
143 return false;
144 }
145 return seed < rhs.seed;
146 }
147
148 index_t f;
149 index_t seed;
150 };
151
159 /************************************************************************/
160
161#ifdef GEO_OS_ANDROID
162 // VectorStack uses AlignedAllocator, that is protected
163 // by a global lock under Android (needed because it
164 // seems that malloc() is not SMP-thread-safe under Android).
165
171
177
183#else
184
189 typedef std::stack<FacetSeed> FacetSeedStack;
190
195 typedef std::stack<TetSeed> TetSeedStack;
196
201 typedef std::stack<index_t> SeedStack;
202#endif
203
204 /************************************************************************/
205
218 public:
223 FacetSeedMarking(index_t /* nb_facets*/, index_t nb_seeds) {
224 set_size(nb_seeds);
225 }
226
230 bool is_marked(index_t facet, index_t seed) const {
231 return find_index(seed, facet) != -1;
232 }
233
237 bool is_marked(const FacetSeed& fs) const {
238 return is_marked(fs.f, fs.seed);
239 }
240
245 signed_index_t get_connected_component(const FacetSeed& fs) const {
246 return find_value(fs.seed, fs.f);
247 }
248
253 void mark(const FacetSeed& fs, index_t conn_comp) {
254 insert(fs.seed, fs.f, conn_comp);
255 }
256
261 for(index_t i = 0; i < nb_arrays(); ++i) {
262 free(keys_[i]);
263 }
264 for(index_t i = 0; i < nb_arrays(); ++i) {
265 free(values_[i]);
266 }
267 }
268
269 protected:
273 index_t nb_arrays() const {
274 return index_t(keys_.size());
275 }
276
281 void set_size(index_t nb_arrays) {
282 keys_.assign(nb_arrays, nullptr);
283 values_.assign(nb_arrays, nullptr);
284 size_.assign(nb_arrays, 0);
285 }
286
292 index_t array_size(index_t array) const {
293 return size_[array];
294 }
295
305 index_t array_capacity(index_t array) const {
306 index_t size = array_size(array);
307 if(size == 0) {
308 return 0;
309 }
310 index_t result = 1;
311 index_t mask = 1;
312 for(index_t i = 0; i < 32; i++) {
313 mask = mask << 1;
314 if((size & mask) != 0) {
315 result = mask;
316 }
317 }
318 // If size is not already a power of two,
319 if(result != size) {
320 result = result << 1;
321 }
322 return result;
323 }
324
331 signed_index_t find_index(index_t array, index_t key) const {
332 index_t* K = keys_[array];
333 for(index_t i = 0; i < array_size(array); ++i) {
334 if(K[i] == key) {
335 return signed_index_t(i);
336 }
337 }
338 return -1;
339 }
340
349 signed_index_t find_value(index_t array, index_t key) const {
350 signed_index_t i = find_index(array, key);
351 if(i == -1) {
352 return -1;
353 }
354 return signed_index_t(values_[array][i]);
355 }
356
363 void insert(index_t array, index_t key, index_t value) {
364 signed_index_t si = find_index(array, key);
365 if(si == -1) {
366 // If not found, append at the end of array
367 index_t i = size_[array];
368 if(i == array_capacity(array)) {
369 // If capacity is reached, grow storage
370 index_t new_nb = index_t(2*i);
371 if(new_nb == 0) {
372 new_nb = 1;
373 }
374 keys_[array] = reinterpret_cast<index_t*>(
375 realloc(keys_[array], sizeof(index_t) * new_nb)
376 );
377 values_[array] = reinterpret_cast<index_t*>(
378 realloc(values_[array], sizeof(index_t) * new_nb)
379 );
380 }
381 size_[array] = i + 1;
382 si = signed_index_t(i);
383 }
384 keys_[array][si] = key;
385 values_[array][si] = value;
386 }
387
388 private:
389 std::vector<index_t*> keys_;
390 std::vector<index_t*> values_;
391 std::vector<index_t> size_;
392 };
393
394 /************************************************************************/
395
401
402 /************************************************************************/
403}
404
405#endif
Common include file, providing basic definitions. Should be included before anything else by all head...
Stores associations between (facet,seed) pairs and the index of a connected component.
void insert(index_t array, index_t key, index_t value)
Inserts a (key,value) pair into one of the arrays.
index_t array_size(index_t array) const
Gets the size of one of the arrays.
signed_index_t find_index(index_t array, index_t key) const
Finds the index of one of the keys in one of the arrays.
signed_index_t find_value(index_t array, index_t key) const
Finds the value associated with a key in one of the arrays.
bool is_marked(const FacetSeed &fs) const
Tests whether a fiven FacetSeed is marked.
FacetSeedMarking(index_t, index_t nb_seeds)
Creates a new FacetSeedMarking.
signed_index_t get_connected_component(const FacetSeed &fs) const
Gets the index of the connected component associated with a given FacetSeed.
index_t array_capacity(index_t array) const
Gets the capacity of one of the arrays.
void mark(const FacetSeed &fs, index_t conn_comp)
Marks a FacetSeed and sets the associated connected component index.
index_t nb_arrays() const
Gets the number of arrays used internally.
~FacetSeedMarking()
FacetSeedMarking destructor.
bool is_marked(index_t facet, index_t seed) const
Tests whether a given facet,seed couple is marked.
void set_size(index_t nb_arrays)
Sets the number of arrays to be used.
A stack implemented in a GEO::vector.
const T & top() const
Gets the item on the top.
void pop()
Pops the top of the stack.
void push(const T &x)
Pushes a new item onto the stack.
bool empty() const
Tests whether the stack is empty.
Vector with aligned memory allocation.
Definition memory.h:660
Internal representation of polyhedra for GEO::GenericVoronoiDiagram.
Internal representation of polygons for GenericVoronoiDiagram.
std::stack< TetSeed > TetSeedStack
A stack of TetSeed.
std::stack< FacetSeed > FacetSeedStack
A stack of FacetSeed.
std::stack< index_t > SeedStack
A stack of seed indices (index_t).
Types and utilities for manipulating vertices in geometric and symbolic forms in restricted Voronoi d...
Types and functions for memory manipulation.
A (facet,seed) pair.
FacetSeed()
Creates a new uninitialized FacetSeed.
bool operator<(const FacetSeed &rhs) const
Compares two facet seeds using lexicographic order.
FacetSeed(index_t f_in, index_t seed_in)
Creates a new FacetSeed.