Extension of CGAL to T2

Top
Up


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 T2, 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

bullet Developed using the Generic Programming paradigm in C++ (like CGAL);
bullet Geometric primitives and predicates extended to work with signed homogeneous coordinates;
bullet 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 T1) 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.;
bullet Algorithms extended to T2 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 T2 subdivisions, detection and enumeration of intersections of segments (of finite and infinite length) and range search with isothetic rectangles.

References

bullet You may read about our extension of CGAL to T2 in:
  1. This thesis: A. G. Oliveira. Implementação do Plano Projetivo Orientado na Biblioteca CGAL. Master's thesis, UNICAMP, 2004.
  2. This short paper: A. G. Oliveira, P. J. de Rezende, F. P. Selmi-Dei. An Extension of CGAL to the Oriented Projective Plane T2 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

bullet 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

bullet 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 3521-5860
FAX
+55 19 3521-5847

 

(c) 1998-2008 Pedro J. de Rezende. Last modified: 2008.08.06.