3D Convex Hull

This repository contains an implementation of the 3D Convex Hull algorithm. The 3D Convex Hull is a fundamental algorithm in computational geometry that computes the smallest convex polyhedron that encloses a given set of points in three-dimensional space.

Usage

To use this implementation, follow these steps:

1. Clone the repository: git clone https://github.com/mauragkas/3D-Convex-Hull.git
2. Navigate to the project directory: cd 3D-Convex-Hull
3. Compile the code: cargo build --release
   • This will create an executable in the target/release directory.
4. Run the program: cargo run --release
   • This will run the program with the default parameters.
   • You can also run the program with custom parameters by passing them as arguments. For example: cargo run --release -- -n 1000 -o output.json
   • The available parameters are:
     • -n or --num-points: The number of points to generate. Default is 1000.
     • -o or --output-file: The name of the output file. Default is output.json.
     • -h or --help: Print the help message.
5. The program will compute the 3D Convex Hull and save it to a json file.
6. run the visualization script: python3 visualize.py output.json
   • This will create a 3D plot of the convex hull.

Algorithm

The 3D Convex Hull algorithm implemented in this repository is based on the QuickHull algorithm. The QuickHull algorithm is a divide-and-conquer algorithm that computes the convex hull of a set of points in three-dimensional space. The algorithm works by recursively dividing the set of points into two subsets, and then finding the convex hull of each subset. The convex hull of the entire set of points is then constructed by merging the convex hulls of the two subsets.

The QuickHull algorithm has a time complexity of O(n log n) in the average case, where n is the number of points in the input set. The algorithm is efficient and robust, and can handle large input sets with ease.

Visualization

The visualize.py script in this repository can be used to visualize the 3D Convex Hull computed by the algorithm. The script reads the output file generated by the algorithm and creates a 3D plot of the convex hull. The plot is interactive, and allows you to rotate and zoom in on the convex hull to get a better view of its structure.

Example

Here is an example of how to use the 3D Convex Hull algorithm:

fn main() {
    // Generate a set of random points
    let points = create_rng_ponts(1000);

    // Compute the 3D Convex Hull
    let convex_hull = convex_hull_3d(&points);

    // Print the convex hull
    println!("{:?}", convex_hull);
}

This code generates a set of 1000 random points in three-dimensional space, computes the 3D Convex Hull of the points, and then prints the convex hull to the console.