/Computational-geometry

Computational geometry algorithms in Java

Primary LanguageJava

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