Exact Minkoski Sums of Polygons With Holes

Abstract

The running time of the three new methods,
The running time of the three new methods, which can handle polygons with holes fed with pairs of general polygons with \(n\) vertices and \(n/10\) holes. The \(n\)-axis indicates the time in seconds. RC—reduced convolution, TD—constrained triangulation decomposition, VD—vertical decomposition.

We present an efficient algorithm that computes the Minkowski sum of two polygons, which may have holes. The new algorithm is based on the convolution approach. We also present a simple theorem, related to the Minkowski sum of polygons with holes, exploited by the new algorithm. We introduce a robust implementation of the new algorithm, which follow the Exact Geometric Computation paradigm and thus guarantees exact results. We also present an empirical comparison of the performance of Minkowski sum constructions, where we show that the implementation of the new algorithm exhibits better performance then all other implementations in many cases. In particular, we compared the implementation of the new algorithm, an implementation of the standard convolution algorithm, and an implementation of the decomposition approach using various convex decomposition methods, including two new methods that handle polygons with holes—one is based on vertical decomposition and the other is based on triangulation.

Links

  • Alon Baram, Efi FogelDan HalperinMichael Hemmer, and Sebastian Morr
    Exact Minkowski Sums of Polygons With Holes
    In Proceedings of the 23rd European Symposium on Algorithms (ESA), 2015 [link][bibtex]
    arXiv:1502.06195v3 [link][bibtex]
  • Alon Baram
    Polygonal Minkowski Sums via Convolution: Theory and Practice
    M.Sc. Thesis, 2013 [pdf] [bibtex]

Contacts

Alon Baram
Dan Halperin
Efi Fogel
Michael Hemmer
Sebastian Morr
@inproceedings{bfhhm-emsph-15,
  author       = {Alon Baram and and Efi Fogel and Dan Halperin and Michael Hemmer and Sebastian Morr},
  editor       = {Nikhil Bansal and Irene Finocchi},
  title        = {Exact {M}inkowski Sums of Polygons With Holes},
  booktitle    = {Proceedings of the 23rd Annual European Symposium on Algorithms (ESA)},
  series       = {LNCS, Volume 9294},
  year         = {2015},
  publisher    = {Springer},
  pages        = {71--82},
  doi          = {0.1007/978-3-662-48350-3_7}
}
@article{bfhhm-emsph-15,
  author       = {Alon Baram and Efi Fogel and Michael Hemmer and Dan Halperin and Sebastian Morr},
  title        = {Exact Minkowski Sums of Polygons With Holes},
  journal      = {CoRR},
  volume       = {abs/1502.06195},
  year         = {2015},
  url          = {http://arxiv.org/abs/1502.06195},
  eprinttype   = {arXiv},
  eprint       = {1502.06195},
  timestamp    = {Mon, 13 Aug 2018 16:48:43 +0200},
  biburl       = {https://dblp.org/rec/journals/corr/BaramFHHM15.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}
@masterthesis{b-pmsct-13,
  author       = {Alon Baram},
  title        = {Polygonal Minkowski Sums via Convolution: Theory and Practice},
  type         = {{M}.{S}c. Thesis},
  school       = {The Blavatnik School of Computer Science, Tel-Aviv University},
  year         = {2013}
}

Yair Oz - Webcreator

Contact

Skip to content