📐 Computational Geometry – Comprehensive Study Guide

**Computational Geometry** is the study of **geometric algorithms** that solve problems related to points, lines, and shapes in 2D and 3D space.

⚡ Why is Computational Geometry Important?

  • 🚀 **Used in Computer Graphics & Image Processing**.
  • 📌 **Essential for AI & Robotics (Path Planning, Object Detection)**.
  • 📡 **Used in Geographic Information Systems (GIS)**.
  • 🔍 **Helps in 3D Modeling & Simulations**.

📌 Basic Geometric Concepts

1️⃣ **Points & Coordinate Geometry**

Each point is represented as **(x, y) in 2D space**.

2️⃣ **Distance Between Two Points**


                double distance(Point p1, Point p2) {
                    return sqrt(pow(p2.x - p1.x, 2) + pow(p2.y - p1.y, 2));
                }

3️⃣ **Line Equation (y = mx + c)**

Formula to find slope **m**:


                m = (y2 - y1) / (x2 - x1);

4️⃣ **Area of a Triangle (Using Determinant)**


                double triangleArea(Point p1, Point p2, Point p3) {
                    return abs((p1.x * (p2.y - p3.y) + 
                                p2.x * (p3.y - p1.y) + 
                                p3.x * (p1.y - p2.y)) / 2.0);
                }

🔄 Convex Hull Algorithms

📌 **1. Graham’s Scan Algorithm (O(n log n))**

Finds the smallest **convex polygon** that encloses all given points.


                bool ccw(Point a, Point b, Point c) {
                    return (b.y - a.y) * (c.x - b.x) > (b.x - a.x) * (c.y - b.y);
                }
            
                vector convexHull(vector& points) {
                    sort(points.begin(), points.end(), [](Point a, Point b) {
                        return a.x < b.x || (a.x == b.x && a.y < b.y);
                    });
            
                    vector hull;
                    for (int i = 0; i < 2; i++) {
                        int start = hull.size();
                        for (auto& p : points) {
                            while (hull.size() >= start + 2 && !ccw(hull[hull.size()-2], hull.back(), p))
                                hull.pop_back();
                            hull.push_back(p);
                        }
                        hull.pop_back();
                        reverse(points.begin(), points.end());
                    }
                    return hull;
                }

📌 **2. Jarvis March Algorithm (O(nh))**

Finds the convex hull by selecting the **leftmost point** and iteratively adding the next extreme point.

🛠️ Line Intersection & Closest Pair of Points

📌 **1. Checking if Two Lines Intersect**


                bool doIntersect(Point p1, Point q1, Point p2, Point q2) {
                    return (ccw(p1, q1, p2) != ccw(p1, q1, q2)) && 
                           (ccw(p2, q2, p1) != ccw(p2, q2, q1));
                }

📌 **2. Closest Pair of Points Algorithm (O(n log n))**


                double closestPair(vector& points) {
                    sort(points.begin(), points.end(), [](Point a, Point b) { return a.x < b.x; });
                    return closestUtil(points, 0, points.size() - 1);
                }

🌀 Triangulation & Voronoi Diagrams

**Triangulation** is the process of **dividing a shape into triangles**, making computations easier.

🌍 Real-World Applications of Computational Geometry

  • 📡 **Geographic Information Systems (GIS)** – Mapping and navigation.
  • 🎮 **Game Development** – Collision detection & physics engines.
  • 🤖 **Artificial Intelligence & Robotics** – Object detection & pathfinding.
  • 🖼️ **Computer Graphics & 3D Modeling** – Used in rendering 3D shapes.

⏳ Time Complexity Analysis

Algorithm Time Complexity
Convex Hull (Graham’s Scan) O(n log n)
Closest Pair of Points O(n log n)
Line Intersection Check O(1)
Voronoi Diagram O(n log n)

🔗 Next Topics