Where to Find Geometry Algorithms in TheAlgorithms/Java: Complete Package Guide

All geometry algorithms in TheAlgorithms/Java are located in the com.thealgorithms.geometry package under src/main/java/com/thealgorithms/geometry, containing stateless implementations for convex hulls, line rasterization, and computational geometry primitives.

TheAlgorithms/Java is a comprehensive collection of algorithmic implementations, and its geometry module provides production-ready Java code for classic computational geometry problems. Every class in this package is designed as an independent, stateless utility that operates on simple value objects, making the geometry algorithms in TheAlgorithms/Java easy to integrate into larger projects.

Package Location and Structure

The geometry module resides in a single, flat package structure:

src/main/java/com/thealgorithms/geometry

This directory contains approximately 15 standalone Java files, each implementing a specific algorithm or geometric primitive. Unlike object-oriented geometry libraries that rely on mutable state, TheAlgorithms/Java uses immutable records and static methods. The core Point.java class serves as the fundamental building block for nearly every other algorithm in the package.

Core Geometric Primitives

Point.java

The Point record in src/main/java/com/thealgorithms/geometry/Point.java is the foundational data structure for all geometry algorithms in TheAlgorithms/Java. It provides:

• Immutable 2-D integer coordinates (x, y)
• Polar angle comparator for sorting around a centroid
• Static orientation() method determining counter-clockwise, clockwise, or collinear relationships between three points

Point a = new Point(0, 0);
Point b = new Point(4, 0);
Point c = new Point(2, 3);

// Returns >0 for counter-clockwise, <0 for clockwise, 0 for collinear
int orient = Point.orientation(a, b, c);
System.out.println("Orientation: " + orient);

Convex Hull Algorithms

The package provides three distinct approaches to computing convex hulls, each optimized for different educational and performance scenarios.

GrahamScan.java

src/main/java/com/thealgorithms/geometry/GrahamScan.java implements the classic O(n log n) Graham scan algorithm. It first sorts points by y-coordinate and polar angle, then builds the hull using a stack-based approach that eliminates concave points.

Point[] pts = {
    new Point(0, 3), new Point(2, 2), new Point(1, 1),
    new Point(2, 1), new Point(3, 0), new Point(0, 0),
    new Point(3, 3)
};

GrahamScan scanner = new GrahamScan(pts);
for (Point p : scanner.hull()) {
    System.out.println(p);
}

ConvexHull.java

src/main/java/com/thealgorithms/geometry/ConvexHull.java provides alternative implementations including a brute-force O(n³) method and a divide-and-conquer O(n log n) approach. Both rely on the Point.orientation method to determine edge validity.

List<Point> pts = List.of(
    new Point(0, 0), new Point(1, 2), new Point(2, 1),
    new Point(2, 4), new Point(3, 3)
);

List<Point> hull = ConvexHull.convexHullBruteForce(pts);
System.out.println("Hull points: " + hull);

Line and Shape Rasterization

The geometry package includes several classic computer graphics algorithms for rasterizing lines and curves on pixel grids.

BresenhamLine.java

src/main/java/com/thealgorithms/geometry/BresenhamLine.java implements the integer-only Bresenham line algorithm, efficiently determining which pixels to illuminate between two endpoints using only integer addition and bit shifting.

int x0 = 2, y0 = 2, x1 = 10, y1 = 6;
List<Point> line = BresenhamLine.calculate(x0, y0, x1, y1);
line.forEach(System.out::println);

DDALine.java and WusLine.java

• DDALine.java (src/main/java/com/thealgorithms/geometry/DDALine.java): Digital Differential Analyzer using floating-point increments
• WusLine.java (src/main/java/com/thealgorithms/geometry/WusLine.java): Wu's antialiased line algorithm for smoother rendering

MidpointCircle.java and MidpointEllipse.java

src/main/java/com/thealgorithms/geometry/MidpointCircle.java and MidpointEllipse.java provide midpoint algorithms for drawing circles and ellipses using decision parameters to select the next pixel.

Advanced Computational Geometry

Haversine.java

src/main/java/com/thealgorithms/geometry/Haversine.java implements the haversine formula for calculating great-circle distances between two latitude/longitude points on a sphere, essential for geospatial applications.

double lat1 = 40.7128, lon1 = -74.0060; // New York
double lat2 = 34.0522, lon2 = -118.2437; // Los Angeles

double km = Haversine.distance(lat1, lon1, lat2, lon2);
System.out.printf("Distance ≈ %.2f km%n", km);

BentleyOttmann.java

src/main/java/com/thealgorithms/geometry/BentleyOttmann.java provides a sweep-line implementation of the Bentley-Ottmann algorithm for efficiently finding all intersection points among a set of line segments in O((n + k) log n) time, where k is the number of intersections.

Summary

• Location: All geometry algorithms in TheAlgorithms/Java reside in src/main/java/com/thealgorithms/geometry under the com.thealgorithms.geometry package.
• Architecture: Stateless, static utility classes operating on immutable Point records with no external dependencies.
• Key Categories:
  • Convex Hulls: GrahamScan.java, ConvexHull.java (brute-force and divide-and-conquer)
  • Rasterization: BresenhamLine.java, DDALine.java, WusLine.java, MidpointCircle.java, MidpointEllipse.java
  • Geospatial: Haversine.java for great-circle distances
  • Advanced: BentleyOttmann.java for line segment intersection detection

Frequently Asked Questions

Where exactly are the geometry files located in TheAlgorithms/Java repository?

All geometry algorithm implementations are located in the directory src/main/java/com/thealgorithms/geometry. This path contains approximately 15 Java files covering convex hulls, line drawing algorithms, and computational geometry primitives, all organized under the com.thealgorithms.geometry package namespace.

What is the Point class used for in TheAlgorithms/Java geometry package?

The Point class in src/main/java/com/thealgorithms/geometry/Point.java is an immutable record representing a 2-D integer coordinate. It provides the foundation for all other geometry algorithms in the repository, offering static methods like orientation() to determine the relative positioning of three points (counter-clockwise, clockwise, or collinear), which is essential for convex hull and intersection algorithms.

How do I calculate the convex hull of a set of points using TheAlgorithms/Java?

You can use either GrahamScan.java or ConvexHull.java depending on your needs. For the classic Graham scan algorithm, instantiate GrahamScan with a Point[] array and call hull() to receive an Iterable<Point>. Alternatively, use ConvexHull.convexHullBruteForce(List<Point>) for educational purposes or the divide-and-conquer method for O(n log n) performance without the stack-based approach.

Does TheAlgorithms/Java include algorithms for drawing lines and circles?

Yes, the repository includes multiple rasterization algorithms in src/main/java/com/thealgorithms/geometry. For lines, you can use BresenhamLine.java (integer-only efficient line drawing), DDALine.java (Digital Differential Analyzer), or WusLine.java (antialiased lines). For curves, MidpointCircle.java and MidpointEllipse.java implement the midpoint algorithms for drawing circles and ellipses on pixel grids.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}