Computational Geometry Tutorial

CGTutorial is a computational geometry tutorial written in Java. It implements various CG algorithms and animates some of them. A library of CG methods and data structures is provided, in the form of Java packages. The library includes, among the others, the following algorithms:

Basic geometric tests: area of a polygon, 2-segment intersection
Convex hull: Jarvis's march, Graham scan
Polygon triangulation: O(n³) and O(n²) ear-cut, O(n log n) monotone partitioning
Point-in-polygon: ray crossings, O(n) test, O(log n) test
Segment intersection: sweeping line method for all and any intersection
HV segments windowing: slow and fast methods
Ray cross segment set: BSP tree method
Delaunay triangulation: Knuth's algorithm
Mesh generation: non-uniform mesh generation
Visibility graph: Dijkstra's shortest path
Voronoi Diagrams: Fortune's algorithm
Point location: Kirkpatrick's method, Chains Method
Rendering 3D: Torus, Trefoil Knots, Sierpinski tetrahedra
Measure and perimeter of a union of rectangles

Usage

CGTutorial can be run be any Java Runtime Environment, starting from version 1.6. To download the latest JRE, check out java.sun.com.

To view the applet, click here. Downloading and starting the applet can take a while (say few minutes).

To grant the applet privileges to open/save files on your local disk, you must take the following steps:

create a CGTutorial folder in your home directory;
set an appropriate .java.policy file, again in your home;
restart the applet.

Alternatively, you can download the tutorial, compile it (make all) and run it as a standalone application (java -jar CGTutorial.jar).

Code modifications

Code modifications must be done through the Subversion repository. You can check out the repository through svn as follows:

svn co https://cgtutorial.svn.sourceforge.net/svnroot/cgtutorial cgtutorial

Browse the online javadoc documentation.

Disclaimer

For comments and suggestions: piersushi at users.sourceforge.net

CGTutorial comes with ABSOLUTELY NO WARRANTY. This is free software, and you are welcome to redistribute it under certain conditions; see the GNU General Public License for details.