Computational Geometry Project

This project implements several computational geometry algorithms in C++, including convex hull, Delaunay triangulation, and kd-tree construction.
All results are visualized using Desmos, and both the code and plots are included in this repository.

---

📁 Project Structure

photos/

Contains all generated plots of the algorithms.
You can verify or modify them via the Desmos links listed in photos/links.txt.

results/

Contains the textual outputs of each algorithm — these are the data used to create the graphs in photos/.

---

📘 Source Files Overview

a1.cpp

• Contains the main() function.
• The code is organized in commented blocks — to run a specific algorithm, simply uncomment the corresponding block.
• Includes two optional colinear points that can be toggled (comment/uncomment) to observe how each algorithm behaves with colinear data.

funcs1.hpp

• Defines all core data structures:
  Point, Edge, Triangle, and Constraint.
• Includes utility functions for:
  • Derivative calculations
  • Point generation
  • Other helper operations used across the project
• Declares all functions implemented in convex_algorithms1.cpp.

funcs1.cpp

• Implements the basic computational functions declared in funcs1.hpp.

convex_algorithms1.cpp

• Implements various convex hull algorithms, including:
  • Incremental (Graham Scan)
  • Jarvis March
  • Divide and Conquer
  • Quickhull

delaunay.hpp / delaunay.cpp

• Functions to compute Delaunay triangulations.

kdtree.hpp / kdtree.cpp

• Implements kd-tree generation and orthogonal search:
  • kdtreegen() → builds a kd-tree from a set of points.
  • orthogonal_search() → performs box (range) search queries.

3dhull.cpp

• Implements a 3D convex hull algorithm using the incremental method, adapted from the CGAL documentation for this project.

---

⚙️ How to Run

Compile with:

make