|
|
|
|
|
| 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 |
| Download |
| Usage |
|
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.
|
| Notice |
|
If you find this tool useful, discover any bug or have any suggestions, feel free to contact us by |
| Update |
|
While the above code works, it is outdated, namely the dependencies. Plus, we wrote the code over a long time, from 2003 to 2008, and sometimes the development was deadline-oriented. As a result, you might find it hard to compile and run it now. Fortunately, several researchers have developed improved versions of this code more recently. You can find a couple of them on GitHub, namely by Catalin Stan and Pau Rosellò. |
| References |
| [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 |
Cross-platform source code [|
Funded by:
|
