Computing an arrangement of segments with some geometrical and topological guarantees is a critical step in many geometry processing applications. In this paper, we propose a method to efficiently compute arrangements of segments using a strip based data structure. Thanks to this new data structure, the arrangement computation algorithm can easily be parallelized as the per strip computations are independent. Another interest of our approach is that we can propose an out-of-core and streamed construction for large datasets, while keeping a low memory footprint. We prove the correctness of our structure and provide a complete comparative evaluation with respect to state-of-the-art demonstrating the interest of our construction for the computation of an exact arrangement.
@article{damiandFastArr2021,
author = {Guillaume Damiand, David Coeurjolly and Pierre Bourquat},
journal = {The Visual Computer Journal},
number = 6,
volume = 37,
month = jun,
title = {Stripped halfedge data structure for parallel computation of arrangements of segments},
year = {2021},
doi = {10.1007/s00371-021-02185-4}
}