1. Graham’s Scan | An algorithm for computing the convex hull of a finite set of points. |
2. Gift Wrapping | Also known as Jarvis march, used for computing the convex hull of a given set of points. |
3. Quickhull | A method of computing the convex hull with a divide-and-conquer approach. |
4. Kirkpatrick–Seidel Algorithm | An algorithm to find the convex hull in the Euclidean plane with the principle of divide and conquer. |
5. Chan’s Algorithm | An output-sensitive algorithm for computing the 2D convex hull combining the approaches of both Jarvis’s march and QuickHull. |
6. Bentley–Ottmann Algorithm | Used for listing all crossings in a set of line segments or in other words, it’s used to solve the line segment intersection problem. |
7. de Berg’s Algorithm | Utilized to solve the problem of hidden surface removal in 3-dimensions. |
8. Line Sweep Algorithm | Common computational geometry algorithm, which is used when the points have an order and it involves sorting of points. |
9. Voronoi Diagram/ Delaunay Triangulation | Algorithms used to divide a space based on a set of points so that each division contains exactly one point. They are dual to each other. |
10. Dijkstra’s Algorithm | Used to find the shortest path in a graph from one vertex to another. |
11. Lee Algorithm | Is an algorithm for pathfinding in 2D grid. It always finds the shortest path. |
12. Rasterization Algorithms | Used to convert an image described in a vector graphics format into a raster image. Common algorithms include Bresenham’s line algorithm and Flood fill. |
13. Flood Fill Algorithm | An algorithm used to determine the area connected to a given node in a multi-dimensional array, often applied in painting tools for filling regions. |
14. Ray Casting Algorithm | Used in computer graphics for the rendering of 3D scenes to 2D screens, e.g., in determination of a point inside a polygon, or for visibility computation. |
15. Clipping Algorithms (e.g., Cohen-Sutherland, Liang-Barsky) | Used to remove objects or lines or portions of lines that are outside of an area of interest. |
16. Search Algorithms (Kd-Tree) | A partitioning space algorithm useful in range and nearest neighbour searches, especially in multiple dimensions. |
17. Separating Axis Theorem | A method to check for collision detection between convex polygons in 2D space. |
18. Distance Transform Algorithm | Used to calculate the distance from each pixel of a binary image to the nearest zero pixel. |
19. Bresenham’s Line Algorithm | It is an algorithm that determines the points of a line that will be displayed on a screen. The effective use of integer arithmetic makes it faster than other similar algorithms like direct use of the line equation. |
20. Point in Polygon Algorithms | Used to determine whether a given point in the plane lies inside, outside, or on the boundary of a polygon. Algorithms can include Ray casting and Winding number algorithm. |