Las bibliotecas CGAL

La implementación de rutinas de geometría computacional es, por lo general, bastante difícil. Por lo general, es muy sencillo implementar un método que funcione pero tenga un mal escalado con el número de puntos. Por ejemplo, es trivial encontrar el nodo más cercano a uno dado probando todas las $N-1$ posibilidades; es mucho más difícil mejorar esto y conseguirlo en tiempo que escale como, por ejemplo, $\log N$ .

Igual que se hace en otras áreas que han sido muy estudiadas, como por ejemplo el álgebra lineal computacional, lo más indicado es utilizar bibliotecas desarrolladas por expertos. En nuestro caso, hemos venido empleando las las bibliotecas CGAL, desarrolladas por un consorcio de universidades y centros de investigación en su mayor parte europeos [7]. Se trata de una iniciativa de código abierto de gran complejidad (más de xxx líneas de código a día de hoy) y, lo que es muy importante en la práctica, dotada de una documentación exhaustiva y muy útil.

En este campo, la gran complejidad de las estructuras hace que muchos lenguajes de bajo nivel, como fortran o c no sean realmente adecuados. Por ello, las bibliotecas CGAL se han decantado desde su fundación por una implementación en c++. Más aún, han utilizado algunos de los conceptos más avanzados del lenguage. Destacamos brevemente algunos.