computational-geometry's Introduction

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(n²)

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(n²)

Polygon triangulation

"Ear clipping" (Van Gogh) algorithm (improved) - O(n²)
"Ear clipping" (Van Gogh) algorithm (naive) - O(n³)
Primitive Divide&Conquer algorithm - O(n⁴)

Point set Delaunay triangulation

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

Halfplanes intersection

Incremental algorithm - O(n²)

Voronoi diagram

Construction via Halfplanes intersection - O(n³)

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

Recommend Projects