|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.
|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.