• Home
    Tables – Mathematics – Geometric Algorithms

    1. Graham’s ScanAn algorithm for computing the convex hull of a finite set of points.
    2. Gift WrappingAlso known as Jarvis march, used for computing the convex hull of a given set of points.
    3. QuickhullA method of computing the convex hull with a divide-and-conquer approach.
    4. Kirkpatrick–Seidel AlgorithmAn algorithm to find the convex hull in the Euclidean plane with the principle of divide and conquer.
    5. Chan’s AlgorithmAn output-sensitive algorithm for computing the 2D convex hull combining the approaches of both Jarvis’s march and QuickHull.
    6. Bentley–Ottmann AlgorithmUsed 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 AlgorithmUtilized to solve the problem of hidden surface removal in 3-dimensions.
    8. Line Sweep AlgorithmCommon computational geometry algorithm, which is used when the points have an order and it involves sorting of points.
    9. Voronoi Diagram/ Delaunay TriangulationAlgorithms 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 AlgorithmUsed to find the shortest path in a graph from one vertex to another.
    11. Lee AlgorithmIs an algorithm for pathfinding in 2D grid. It always finds the shortest path.
    12. Rasterization AlgorithmsUsed 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 AlgorithmAn 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 AlgorithmUsed 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 TheoremA method to check for collision detection between convex polygons in 2D space.
    18. Distance Transform AlgorithmUsed to calculate the distance from each pixel of a binary image to the nearest zero pixel.
    19. Bresenham’s Line AlgorithmIt 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 AlgorithmsUsed 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.