Polygon Detector
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. The polygon detection algorithm runs in O(n^4), where "n" is the number of lines. The paper where the algorithm was initially published [1] can be freely dowloaded and should be cited whenever the algotithm is used.

Input and output example
     Cross-platform source code [RAR 157KB]
The algorithm is developed in C++ and uses wxWidgets. Indeed, the use of wxWidgets is only because the original version of the algorithm was developed within a larger project based on wxWidgets and some wxWidgets features were used, such as list and error message handling. Although not complicated, it will be time consuming to replace things like 'wxList' with standard c++ 'std::list' and other stuff like that.

Nevertheless, developers that used the code reported that, apart from replacing the wxWidget classes with MFC or standard c++ templates, the biggest change they made was to include a small tolerance in many of the floating-point tests. For example, "if(p1->GetX() == p2->GetX()) changed to "if(fabs(p1->GetX() - p2->GetX()) <= 0.001)". These changes made the algorithm robust to floating point precision errors.

If you find this tool useful, discover any bug or have any suggestions, feel free to contact us by

[1] "Polygon Detection from a Set of Lines", Ferreira, A., Fonseca, M.J. and Jorge, J.A., Actas do 12º Encontro Portugues deComputação Gráfica (12th EPCG), pages 159-162, Porto, Portugal, Oct 2003

Funded by:

European Union — Structural Funds


Portuguese Republic