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
} }
Citation