Polygon Detection from a Set of Lines
No Thumbnail Available
Date
2021
Journal Title
Journal ISSN
Volume Title
Publisher
The Eurographics Association
Abstract
Detecting polygons defined by a set of line segments in a plane is an important step in the analysis of vectorial drawings. This paper presents an approach that combines several algorithms to detect basic polygons from a set of arbitrary line segments. The resulting algorithm runs in polynomial time and space, with complexities of O((N + M)4) and O((N + M)2) respectively, where N is the number of line segments and M is the number of intersections between line segments. Our choice of algorithms was made to strike a good compromise between efficiency and ease of implementation. The result is a simple and efficient solution to detect polygons from lines.
Description
@inproceedings{10.2312:pt.20031439,
booktitle = {12º Encontro Português de Computação Gráfica},
editor = {Marcos, Adérito and Mendonça, Ana and Leitão, Miguel and Costa, António and Jorge, Joaquim},
title = {{Polygon Detection from a Set of Lines}},
author = {Jr., Alfredo Ferreira and Fonseca, Manuel and Jorge, Joaquim},
year = {2021},
publisher = {The Eurographics Association},
ISBN = {978-3-03868-163-2},
DOI = {10.2312/pt.20031439}
}