Polygon Detector v0.1

More that four years after the publication of the algorithm in the paper "Polygon Detection from a Set of Lines", I finally found time to re-write the code. Since it was implemented within a larger project, it was sharing several pieces of code and dependent of classes containing lots of functionalities unnecessary for this purpose.

The "Polygon Detector" prototype takes as input an SVG file containing a set of lines and produces another SVG file with the corresponding polygon set. Note that the polygon detection algorithm runs in O(n^4), where "n" is the number of lines obtained after intersection removal. Thus, for a complex line set, it may take a while to detect the polygons. For instance, processing the line set depicted below took around twelve minutes in a Intel Pentium M 2GHz 1MB RAM computer running Windows XP.

Line set with 100 random lines, corresponding to 2286 non-intersecting lines

The polygon detection algorithm created, from the line set illustrated above, a set of almost one thousand polygons depicted below. The current version of the prototype produces an SVG file containing colored polygons, however the coloring algorithm used is quite simple and still needs some improvements, namely to avoid (or at least minimize) color repetition. Something to be solved in a future version.

Set of detected polygons, containing 995 elements.

If interested, you can download the current stable version of the prototype [ZIP 434KB] or the paper where the algorithm was initially paper, "Polygon Detection from a Set of Lines", Ferreira, A., Fonseca, M.J. and Jorge, J.A., Actas do 12º Encontro Português de Computação Gráfica (12th EPCG), pages 159-162, Porto, Portugal, Oct 2003 [PDF 86KB].