Polygon Detection from a Set of Lines

Jr., Alfredo Ferreira; Fonseca, Manuel; Jorge, Joaquim

Polygon Detection from a Set of Lines

Files

159-162.pdf (82.03 KB)

Date

2021

Authors

Jr., Alfredo Ferreira
Fonseca, Manuel
Jorge, Joaquim

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.

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