Computational geometry in Java

The project contains both implementations and visualization tools for basic computational geometry algorithms in two-dimensional space. These algorithms are implemented in Java programming language and are visualized using the Swing libraries.

List of implemented algorithms:

Two segments intersection

Algorithm using the cross product - O(1)

Any segments intersection

Sweeping line algorithm - O(n·lg(n)) Naive algorithm - O(n2)

Convex hull construction

Graham's scan - O(n·lg(n)) Jarvis' march - O(n·h)

Closest points pair

Divide&Conquer - O(n·lg(n)) Naive algorithm - O(n2)

Polygon triangulation

"Ear clipping" (Van Gogh) algorithm (improved) - O(n2) "Ear clipping" (Van Gogh) algorithm (naive) - O(n3) Primitive Divide&Conquer algorithm - O(n4)

Point set Delaunay triangulation

Randomized incremental construction - O(n·lg(n)) Brute force edge flipping algorithm - O(n3)
3D Terrain construction via VRML

Halfplanes intersection

Incremental algorithm - O(n2)

Voronoi diagram

Construction via Halfplanes intersection - O(n3)

Reference books:

• "Introduction to Algorithms" by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein
• "Computational Geometry: Algorithms and Applications" by Mark de Berg, Otfried Cheong, Marc van Kreveld and Mark Overmars
• "The Algorithm Design Manual" by Steven S. Skiena
• "Programming Challenges" by Steven S. Skiena and Miguel Revilla
• "Axioms and hulls" by Donald E. Knuth