An Experimental Evaluation of Offset Computation for Polygons
Computer-Aided Design and Applications Pages 807-818, Volume 21(5) January, 2024
@article{HeLoPa24,
author = {M. Held and S. de Lorenzo and P. Palfrader},
title = {{An Experimental Evaluation of Offset Computation for Polygons}},
journal = {Computer-Aided Design and Applications},
year = {2024},
volume = {21},
number = {5},
pages = {807-818},
month = jan,
doi = {10.14733/cadaps.2024.807-818},
}
We present an experimental evaluation of the computation of offset curves of polygons in the plane. Our evaluation involves several leading software packages for computing Boolean operations and for computing Voronoi diagrams. We compare these packages to our own codes CAPOP (for computing Boolean operations on closed curves consisting of straight-line and circular-arc edges) and Vroni (for computing Voronoi diagrams). Our extensive tests show that the differences in the run-times of the packages tested are substantial. In particular, only CAPOP and the Voronoi codes Vroni and OpenVoronoi exhibit a clearly sub-quadratic run-time complexity.
On the Recognition and Reconstruction of Weighted Voronoi Diagrams and Bisector Graphs
Computational Geometry Pages 101935, Volume 109 February, 2023
@article{EdHeLoPa22a,
author = {Stefan de Lorenzo},
title = {{On the Recognition and Reconstruction of Weighted Voronoi Diagrams and Bisector Graphs}},
author = {Günther Eder and Martin Held and Stefan {de Lorenzo} and Peter Palfrader},
journal = {Computational Geometry},
volume = {109},
pages = {101935},
year = {2023},
issn = {0925-7721},
doi = {https://doi.org/10.1016/j.comgeo.2022.101935},
url = {https://www.sciencedirect.com/science/article/pii/S0925772122000785},
}
A weighted bisector graph is a geometric graph whose faces are bounded by edges that are portions of multiplicatively weighted bisectors of pairs of (point) sites such that each of its faces is defined by exactly one site. A prominent example of a bisector graph is the multiplicatively weighted Voronoi diagram of a finite set of points which induces a tessellation of the plane into Voronoi faces bounded by circular arcs and straight-line segments. Several algorithms for computing various types of bisector graphs are known. In this paper we reverse the problem: Given a partition \(G\) of the plane into faces, find a set of points and suitable weights such that \(G\) is a bisector graph of the weighted points, if a solution exists. If \(G\) is a graph that is regular of degree three then we can decide in \(O(m)\) time whether it is a bisector graph, where \(m\) denotes the combinatorial complexity of \(G\). In the same time we can identify up to two candidate solutions such that \(G\) could be their multiplicatively weighted Voronoi diagram. Additionally, we show that it is possible to recognize \(G\) as a multiplicatively weighted Voronoi diagram and find all possible solutions in \(O(m \log m)\) time if \(G\) is given by a set of disconnected lines and circles.
Generalized Voronoi Diagrams: Theory and Related Applications
University of Salzburg July, 2021
@article{Lo21a,
author = {Stefan de Lorenzo},
title = {{Generalized Voronoi Diagrams: Theory and Related Applications}},
school = {University of Salzburg},
year = {2021},
}
The standard Voronoi diagram of points in the plane is one of the most prominent tools in computational geometry and has been intensively studied in the past. It can be generalized in a wide variety of ways. A natural extension is to associate multiplicative weights with the individual input points. In this scenario, the extent of a Voronoi region does not only depend on the location of the respective site, but is also influenced by the corresponding weight. In this cumulative dissertation, an efficient practice-minded strategy for computing the multiplicatively weighted Voronoi diagram (MWVD) of points is presented. Additionally, we will take a look at the recognition and reconstruction of weighted bisector graphs.
Another way to generalize the Voronoi diagram is to extend the range of permissible input sites. We will utilize the Voronoi diagram of straight-line segments and circular arcs, to generate tool paths inside planar shapes for NC machining. Of course, these generalizations can also be combined. The generalized weighted Voronoi diagram (GWVD) even allows the endpoints of one of its input straight-line segment to be associated with different multiplicative weights. We present an in-depth analysis of the GWVD and introduce an alternative structure that we will refer to as the variable-radius skeleton (VRS) inside a polygon. Both the GWVD as well as the VRS can be used to generate so-called variable-radius offsets.
Additionally, we take a close look at convex decompositions of points sets. In particular, several heuristics are presented that allow us to reduce the face count of an initial convex decomposition.
Weighted Skeletal Structures For Computing Variable-Radius Offsets
Computer-Aided Design and Applications Pages 875-889, Volume 18(5) January, 2021
BibTeX — abstract — [paper (PDF)] — [DOI]
@article{HeLo21a,
author = {Martin Held and Stefan de Lorenzo},
title = {{Weighted Skeletal Structures For Computing Variable-Radius Offsets}},
journal = {Computer-Aided Design and Applications},
year = {2021},
volume = {18},
number = {5},
pages = {875--889},
month = {January},
doi = {10.14733/cadaps.2021.875-889},
oa = {(Gold OA)},
}
Held et al. [CAD&A 2016] introduced generalized weighted Voronoi diagrams as a tool to construct variable-radius offsets. We revisit this structure and provide two algorithms to compute it. We also introduce variable-radius skeletons of polygons as a closely related structure which inherits most properties of generalized weighted Voronoi diagrams except that its skeletal regions are always connected. Experimental results obtained by our implementation of variable-radius skeletons are discussed. In addition to variable-radius offsets we demonstrate how this structure can be used to generate intricate roofs for polygonal footprints of buildings in an automated way.
An Efficient, Practical Algorithm and Implementation for Computing Multiplicatively Weighted Voronoi Diagrams
In Proceedings of the 28th Annual European Symposium on Algorithms (ESA 2020) Pages 56:1-56:15 Pisa, Italy September, 2020
BibTeX — abstract — talk — [paper (PDF)] — [slides (PDF)] — [DOI]
@inproceedings{HeLo20c,
author = {Martin Held and Stefan de Lorenzo},
title = {{An Efficient, Practical Algorithm and Implementation for Computing Multiplicatively Weighted Voronoi Diagrams}},
booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)},
year = {2020},
editor = {Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
volume = {173},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
pages = {56:1--56:15},
address = {Dagstuhl, Germany},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
annote = {Keywords: Voronoi Diagram, multiplicative weight, additive weight,
arc expansion, overlay arrangement, implementation, experiments, CGAL, exact arithmetic},
doi = {10.4230/LIPIcs.ESA.2020.56},
isbn = {978-3-95977-162-7},
issn = {1868-8969},
url = {https://drops.dagstuhl.de/opus/volltexte/2020/12922},
urn = {urn:nbn:de:0030-drops-129224},
}
We present a simple wavefront-like approach for computing multiplicatively weighted Voronoi diagrams of points and straight-line segments in the Euclidean plane. If the input sites may be assumed to be randomly weighted points then the use of a so-called overlay arrangement [Har-Peled&Raichel, Discrete Comput. Geom. 53:547–568, 2015] allows to achieve an expected runtime complexity of \(O(n\log^4 n)\), while still maintaining the simplicity of our approach. We implemented the full algorithm for weighted points as input sites, based on CGAL. The results of an experimental evaluation of our implementation suggest \(O(n\log^2 n)\) as a practical bound on the runtime. Our algorithm can be extended to handle also additive weights in addition to multiplicative weights, and it yields a truly simple \(O(n\log n)\) solution for solving the one-dimensional version of this problem.
Weighted Skeletal Structures for Computing Variable-Radius Offsets
In Proceedings of the 17th Computer-Aided Design Conference (CAD 2020) Pages 46-50 Barcelona, Spain July, 2020
@inproceedings{HeLo20b,
author = {Martin Held and Stefan de Lorenzo},
title = {Weighted {S}keletal {S}tructures for {C}omputing {V}ariable-{R}adius {O}ffsets},
booktitle = {Proceedings of the 17th Computer-Aided Design Conference (CAD 2020)},
pages = {46--50},
year = {2020},
address = {Barcelona, Spain},
month = {July},
doi = {10.14733/cadconfP.2020.46-50}
}
Computing Low-Cost Convex Partitions for Planar Point Sets Based on Tailored Decompositions
In Proceedings of the 36th International Symposium on Computational Geometry (SoCG 2020) Pages 85:1-85:10 Zürich, Switzerland June, 2020
BibTeX — abstract — talk — [paper (PDF)] — [slides (PDF)] — [DOI]
@inproceedings{Ede&20c,
author = {G{\"u}nther Eder and Martin Held and Stefan de Lorenzo and Peter Palfrader},
title = {{Computing Low-Cost Convex Partitions for Planar Point Sets Based on Tailored Decompositions (CG Challenge)}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {85:1--85:11},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Sergio Cabello and Danny Z. Chen},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12243},
URN = {urn:nbn:de:0030-drops-122438},
doi = {10.4230/LIPIcs.SoCG.2020.85},
annote = {Keywords: Computational Geometry, geometric optimization, algorithm engineering, convex decomposition}
}
Our work on minimum convex decompositions is based on two key components: (1) different strategies for computing initial decompositions, partly adapted to the characteristics of the input data, and (2) local optimizations for reducing the number of convex faces of a decomposition. We discuss our main heuristics and show how they helped to reduce the face count.
On Implementing Multiplicatively Weighted Voronoi Diagrams
In Proceedings European Workshop on Computational Geometry (EuroCG 2020) Würzburg, Germany March, 2020
BibTeX — abstract — talk — [paper (PDF)] — [slides (PDF)]
@inproceedings{HeLo20a,
author = {Martin Held and Stefan de Lorenzo},
title = {On {I}mplementing {M}ultiplicatively {W}eighted {V}oronoi {D}iagrams},
booktitle = {Proceedings of the 36th European Workshop on Computational Geometry (EuroCG 2020)},
year = {2020},
address = {Wuerzburg, Germany},
month = {March}
}
We present a simple wavefront-like approach for computing multiplicatively weighted Voronoi diagrams of points and straight-line segments in the Euclidean plane. If the input sites may be assumed to be randomly weighted points then the use of a so-called overlay arrangement [Har-Peled&Raichel, Discrete Comput. Geom., 2015] allows to achieve an expected runtime complexity of \(O(n\log^4 n)\), while still maintaining the simplicity of our approach. We implemented the full algorithm for weighted points as input sites, based on CGAL. The results of an experimental evaluation of our implementation suggest \(O(n\log^2 n)\) as a practical bound on the runtime. Our algorithm can be extended to handle also additive weights in addition to multiplicative weights.
A Wavefront-Like Strategy for Computing Multiplicatively Weighted Voronoi Diagrams
In Proceedings of the European Workshop on Computational Geometry (EuroCG 2019) Utrecht, Netherlands March, 2019
@inproceedings{HeLo19,
author = {Martin Held and Stefan de Lorenzo},
title = {A {W}avefront-{L}ike {S}trategy for {C}omputing {M}ultiplicatively {W}eighted {V}oronoi {D}iagrams},
booktitle = {Proceedings of the 35th European Workshop on Computational Geometry (EuroCG 2019)},
year = {2019},
address = {Utrecht, Netherlands},
month = {March}
}
We study multiplicatively weighted Voronoi diagrams (MWVDs) of point sites in the Euclidean plane and present a wavefront-like approach for computing the MWVD of \(n\) points in near-optimal \(O(n^2\log n)\) time and \(\Theta(n^2)\) space. The key advantage of our algorithm is its simplicity. Furthermore, it can be extended to handle additive weights at no additional computational cost.
On the Generation of Spiral-Like Paths Within Planar Shapes
Journal of Computational Design and Engineering Pages 348-357, Volume 5(3) July, 2018
BibTeX — abstract — [paper (PDF)] — [DOI]
@article{HeLo18b,
author = {Martin Held and Stefan de Lorenzo},
title = {On the {G}eneration of {S}piral-{L}ike {P}aths {W}ithin {P}lanar {S}hapes},
journal = {Journal of Computational Design and Engineering,
year = {2018},
number = {3},
pages = {348--357},
volume = {5},
publisher = {Elsevier},
doi = {10.1016/j.jcde.2017.11.011}
}
We simplify and extend prior work by Held and Spielberger [CAD 2009, CAD&A 2014] to obtain spiral-like paths inside of planar shapes bounded by straight-line segments and circular arcs: We use a linearization to derive a simple algorithm that computes a continuous spiral-like path which (1) consists of straight-line segments, (2) has no self-intersections, (3) respects a user-specified maximum step-over distance, and (4) starts in the interior and ends at the boundary of the shape. Then we extend this basic algorithm to double-spiral paths that start and end at the boundary, and show how these double spirals can be used to cover complicated planar shapes by composite spiral paths. We also discuss how to improve the smoothness and reduce the curvature variation of our paths, and how to boost them to higher levels of continuity.
Spiral-Like Paths on Triangulated Terrains
In Proceedings of the 7th Young Researchers Forum (CG Week 2018) Budapest, Hungary June, 2018
@inproceedings{HeLo18a,
author = {Martin Held and Stefan de Lorenzo},
title = {Spiral-{L}ike {P}aths on {T}riangulated {T}errains},
booktitle = {Proceedings of the 7th Young Researchers Forum (CG Week 2018)},
year = {2018},
address = {Budapest, Hungary},
month = {June}
}
On the Generation of Spiral Paths Within Planar Shapes
In Proceedings of the European Workshop on Computational Geometry (EuroCG 2017) Malmö, Sweden April, 2017
@inproceedings{HeLo17,
author = {Martin Held and Stefan de Lorenzo},
title = {On the {G}eneration of {S}piral-{L}ike {P}aths {W}ithin {P}lanar {S}hapes},
booktitle = {Proceedings of the 33th European Workshop on Computational Geometry (EuroCG 2017)},
year = {2017},
address = {Malmoe, Sweden},
month = {April}
}
We simplify and extend prior work by Held and Spiel-berger [CAD 2009, CAD&A 2014]: We use a linearization to derive a simple algorithm that computes a spiral path inside of planar shape bounded by straight-line segments and circular arcs. Our spiral paths are continuous and without self-intersection, respect a user-specified maximum step-over distance, start in the interior and end at the boundary of the shape.We also extend this basic algorithm to double spirals that start and end at the boundary.
On the Generation of a Spiral Tool Path for High Speed Pocket Machining and Related Applications
University of Salzburg November, 2016
@MastersThesis{Lo16,
author = {Stefan de Lorenzo},
title = {{On the Generation of a Spiral Tool Path for High Speed Pocket Machining and Related Applications}},
school = {University of Salzburg},
year = {2016},
}
Based on prior work by Held and Spielberger [CAD 41/7, 2009][CADA 11/3, 2014], we present a modified tool-path generation strategy suitable for high speed machining (HSM). A raw tool path is constructed which is not self-intersecting, respects the initially specified, maximum step-over, starts in the interior, and ends at the boundary of the pocket. Additionally, we formalize the idea of a dynamic boundary that changes its shape during the creation of the cutter trajectory, and results in a tool path with better kinematic features. By inserting bridges into the original pocket, the algorithm is able to handle pockets that include an arbitrary number of islands. In order to generate a \(G^1\)-continuous tool path, we approximate the raw cutter trajectory through a series of biarcs using the PowerApx-package developed by Held and Heimlich [IJCGA 18/3, 2008].
Complex pocket regions, i.e., cavities that contain a vast amount of narrow bottlenecks, result in exceedingly long tool paths. Thus, a decomposition scheme is discussed that subdivides the initial pocket into several sub-pockets which are milled out individually. This procedure tends to reduce the overall step-over variation, but has the drawback that each sub-pocket corresponds to a tool retraction.
Finally, the possibility of creating a double spiral, i.e., a curve that starts and ends at the pocket boundary, while simultaneously keeping all the aforementioned properties, is discussed. This scheme is unsuited for pocket milling, due to the fact that the cutter is highly engaged most of the time, but may find use in other applications, such as spray paintings, aerial surveillance, or path finding algorithms for rescue missions.