Geometric Algorithms

A comprehensive collection of computational geometry algorithms and visualizations implemented as part of the Geometric Algorithms laboratory course.

📋 Table of Contents

• About the Project
• Implemented Algorithms
• Tech Stack
• Installation & Setup
• Visualizations
• License

📖 About the Project

This repository focuses on the implementation, analysis, and visualization of fundamental algorithms in computational geometry. The project includes performance benchmarks for various datasets, such as points on circles, within squares, or collinear sets, handling edge cases and floating-point precision issues.

🧪 Implemented Algorithms

Lab 1: Orientation & Foundations

• Determinant Calculations: Implementation of $2 \times 2$ and $3 \times 3$ determinants to determine point orientation relative to a line.
• Classification: Categorizing points as Left, Right, or Collinear.
• Precision Analysis: Comparing results across different floating-point types.

Lab 2: Convex Hulls

• Jarvis March (Gift Wrapping algorithm).
• Graham Scan (using angular sorting).
• Benchmarking: Time complexity analysis and step-by-step construction visualization.

Lab 3: Line Segment Intersections

• Bentley-Ottmann Algorithm: A sweep-line approach to find all intersection points in a set of segments.
• Data Structures: Implementation of the Status Tree and Event Queue.

Lab 4: Polygon Triangulation

• Monotonicity Check: Identifying if a polygon is y-monotonic.
• Vertex Classification: Start, End, Split, Merge, and Regular vertices.
• Triangulation Algorithm: Efficient triangulation of monotonic polygons.

🛠 Tech Stack

• Python 3.x
• Jupyter Notebook (for interactive demonstrations)
• Matplotlib (dynamic visualizations and plots)
• NumPy (numerical computations)

🚀 Installation & Setup

1. Clone the repository:

   git clone [https://github.com/juliet2112/Geometric-algorithms.git](https://github.com/juliet2112/Geometric-algorithms.git)