Extension of CGAL to T2

Extension of CGAL to T2

What is it about

Key Words: Computational Geometry, Visualization, Oriented Projective Plane

Since CGAL was developed using the Generic Programming paradigm in C++, we adopted the the same approach. In order to allow for the implementation of algorithms on T², firstly, geometric primitives and predicates were extended to work with signed homogeneous coordinates. Later, we also extended (Euclidean) algorithms to work on the Oriented Projective Plane which showed that a significant number of special cases, dealt with on the Euclidean plane, did not need separate treatment in the extended algorithms.

Key Benefits

	Developed using the Generic Programming paradigm in C++ (like CGAL);
	Geometric primitives and predicates extended to work with signed homogeneous coordinates;
	Extended primitives and predicates include: points (proper and improper), straight lines, segments, rays, vectors, triangles, isothetic rectangles, bounding boxes and circles; distance computation (finite and infinite, in the sense of T¹⁾ and comparisons (absolute and relative, among proper and improper points), orientation of triples of points, point-segment incidence, relative position with respect to lines, etc.;
	Algorithms extended to T² include: construction of the convex hull of sets of points, arbitrary and Delaunay triangulation (covering the entire space and not just one range), Voronoi diagram (closest and farthest neighbor), minimum distance spanning tree, largest empty circle (with proper center), all nearest neighbor graph, point location on T² subdivisions, detection and enumeration of intersections of segments (of finite and infinite length) and range search with isothetic rectangles.

References

You may read about our extension of CGAL to T² in:

This thesis: A. G. Oliveira. Implementação do Plano Projetivo Orientado na Biblioteca CGAL. Master's thesis, UNICAMP, 2004.
This short paper: A. G. Oliveira, P. J. de Rezende, F. P. Selmi-Dei. An Extension of CGAL to the Oriented Projective Plane T² and its Dynamic Visualization System. 21st Annual ACM Symp. on Computational Geometry, Pisa, Italy, 2005.

What is available

You may download the source code for the Extension of CGAL to the Oriented Projective Plane.

License Terms

Open Source License

Extension of CGAL to the Oriented Projective Plane is available under an Open Source license. More exactly, it is under the GPL License. If you intend to modify or write your own software based on components of this Extension of CGAL to the Oriented Projective Plane, make sure you read the GPL license and abide by the terms therein.

Download

The Source code of the Extension of CGAL to the Oriented Projective Plane is available here: INSTALL, Source Code=tar.gz

Contact Information

If you have questions not answered in these pages, feel free to contact us. However, we should point out that all the documentation we have available is posted here as well as all the sources we have.

People involved: Alessandra G. de Oliveira; Pedro J. de Rezende
Electronic mail: General Information:
Postal address: Institute of Computing, UNICAMP, Campinas SP, Brazil
Telephone: +55 19 3788-5860
FAX: +55 19 3788-5847