Posted by NOTIFICATION: These examples are provided for educational purposes. Using this code is under your own responsibility and risk. The code and information is given ‘as is’. I do not take responsibilities of how they are used.
< List of Common Algoritms – Part 1 | List of Common Algorithms – Part 3 >
- Adjacency-matrix representation: Numbered vertices of a graph are represented in a matrix.
- Breadth-first search: Algorithm for searching a graph. All the edges of a graph are discovered in a systematic search. Computing the distance from the start point to each reachable vertex.
- Topological sort: Linear ordering of all vertices of a graph in with the one vertex must appear before another in an order.
- Minimum Spanning Trees: Algorithm design to solve undirected graphs.
- Kruskal’s algorithm: Algorithm based on the generic minimum-spanning-tree algorithm. It finds all the edges that connect any two trees in the forest.
- Prim’s algorithm: Algorithm based on the generic minimum-spanning-tree algorithm but behaves similar to Dijkstra algorithm. Used for finding the shortest path in a graph.
- Shortest-paths problem (SPP): Given a weighted, directed graph plus a weight function map the edges to real-valued weights. Find the shortest path.
- Bellman-Ford algorithm: Single-source shortest-paths problem in which edge weights may be negative.
- Single source shortest paths in directed acyclic graphs: Topologically sorting the directed acyclic path to provide a linear ordering on the vertices.
- Dijkstra’s algorithm: Repeatedly a vertex is selected with the minimum shortest-path estimate by adding the weight and relaxing all edges leaving the first edge.
- All-Pairs Shortest Paths: Finding the shortest paths between all pairs of vertices in a graph.
- Floyd-Warshall algorithm: Dynamic-programming formulation to solve all-pairs shortest-paths problem on a directed graph.
- Johnson’s algorithm for sparse graphs: Finding the shortest paths between all pairs. Better than either repeated squaring of matrices or Floyd-Warshall algorithm.
- Maximum Flow: Problem concerting flow networks.
- Ford-Fulkerson method: Methods for maximum flow problem which focus on residual networks, augmenting paths, and cuts. Essential concept for maximum flow min-cut theorem.
- Edmonds-Karp algorithm: Algorithm that implement the computation of the augmenting path with a breadth-first search.
- Maximum Bipartite Matching: Matching of maximum cardinality.
- Push-relabel Algorithm: Way to solve asymptotically fastest maximum-flow algorithms.
- Relabel-to-front algorithm: A push-relabel algorithm better fit for dense networks.
- Zero-one principle: Sorting a network with this principle allows to focus on their operation for input sequences consisting solely of 0’s and 1’s.
- Bitonic sorting network: A bitonic sequence that monotonically increases and then decreases. This is a comparison network that sorts bitonic sequences of 0’s and 1’s.
- Half-cleaner: Bitonic sorter which is composed of several stages. Each of these stages is called half-cleaner which are a comparison network of depth 1.
- Bitonic sorter: A network that sorts bitonic sequences.
- Merging network: Networks that can be merge two sorted input sequences into one sorted output sequence.
- Permutation network: inputs and output are connected according to any allowed permutation.
- Strassen’s algorithm: Recursively algorithm used for matrix multiplication.
- LUP decomposition: Find three matrices such that the multiplication of a permutation matrix with a custom defined matrix is the same as the multiplication of a a unit lower-triangular matrix with an upper-triangular matrix.
- Forward and back substitution: Way to solve lower-triangular system.
- Least-squares approximation: Way to provide curves to given sets of data points in symmetric positive-defined matrices.
- Rabin-Karp algorithm: string-matching algorithm.
- Knuth-Morris-Patt algorithm: linear-time sting-matching algorithm.
- Jarvis’s march: Way to compute the convex hull of a set of points by using package wrapping technique.
- Hamiltonian Cycles: A simple cycle that contains each vertex of an undirected graph.
- Vertex-cover problem: Undirected graph in which each vertex covers its incident edge.
- Digital Differential Analyzer (DDA): Scan-conversion line-drawing algorithm.
- Bresenham’s Line Algorithm: Efficient raster line-generating algorithm in which only incremental integer calculations are used.
- Midpoint Circle Algorithm: Raster algorithm in which each unit interval, we determine the closest pixel position that match the circle path at each step.
- Midpoint Ellipse Algorithm: Similar algorithm used for drawing circles. After determining the curve positions for the ellipse, all the points are shift using a fixed offset so that the ellipse is centered.
- Spilling Concave Polygons: Split identified concave polygon into a set of convex polygons. Another variation is to split the concave polygon into a set of triangles.
- Inside-Outside Test: System to identify interior areas of a plane figure by using odd-even rule (also known as odd-parity rule). Another method use is called non-zero winding-number rule.
- Odd-Parity Rule: Method to identify interior regions by counting the number of segments crossed by a line.
- Non-zero Winding-Number Rule: Method to define interior regions by counting the number of times the boundary of an object “winding” around a defined point in the counter-clockwise direction.
- Polygon Tables: Normally consistent of three listing of geometric data which provides reference to the individual components (such as edges, vertices, and surface facets) for each object.
- Linear Soft-Fill Algorithm: Algorithm which help to repaint an area which was originally painted by merging a single background color with foreground color.
- Scan-Line Fill Algorithm: Algorithm which help to identify the same interior regions as the Odd-Parity rule.
- Boundary-Fill Algorithm: This algorithm will fill the interior of a region pixel by pixel until a boundary specified by a color is encountered.
- Flood-Fill Algorithm: This algorithm paints an area defined by different color regions by replacing a specified interior color instead of searching for a boundary color.
- Pitteway-Watkinson Algorithm: This algorithm is a modification to Bresenham’s algorithm. Depending of the area of overlap of the line plus the pixel, each pixel is given an intensity; therefore, the effect of anti-aliasing is reduced due to the
- blurring effect which goes along the line edges.
- Rigid-body Transformation: Its a translation which moves objects without deforming them.
< List of Common Algoritms – Part 1 | List of Common Algorithms – Part 3 >
NOTIFICATION: These examples are provided for educational purposes. Using this code is under your own responsibility and risk. The code and information is given ‘as is’. I do not take responsibilities of how they are used.
- Digital Differential Analyzer (DDA): Scan-conversion line-drawing algorithm.
- Bresenham’s Line Algorithm: Efficient raster line-generating algorithm in which only incremental integer calculations are used.
- Midpoint Circle Algorithm: Raster algorithm in which each unit interval, we determine the closest pixel position that match the circle path at each step.
- Midpoint Ellipse Algorithm: Similar algorithm used for drawing circles. After determining the curve positions for the ellipse, all the points are shift using a fixed offset so that the ellipse is centered.
- Spilling Concave Polygons: Split identified concave polygon into a set of convex polygons. Another variation is to split the concave polygon into a set of triangles.
- Inside-Outside Test: System to identify interior areas of a plane figure by using odd-even rule (also known as odd-parity rule). Another method use is called non-zero winding-number rule.
- Odd-Parity Rule: Method to identify interior regions by counting the number of segments crossed by a line.
- Non-zero Winding-Number Rule: Method to define interior regions by counting the number of times the boundary of an object “winding” around a defined point in the counter-clockwise direction.
- Polygon Tables: Normally consistent of three listing of geometric data which provides reference to the individual components (such as edges, vertices, and surface facets) for each object.
- Linear Soft-Fill Algorithm: Algorithm which help to repaint an area which was originally painted by merging a single background color with foreground color.
- Scan-Line Fill Algorithm: Algorithm which help to identify the same interior regions as the Odd-Parity rule.
- Boundary-Fill Algorithm: This algorithm will fill the interior of a region pixel by pixel until a boundary specified by a color is encountered.
- Flood-Fill Algorithm: This algorithm paints an area defined by different color regions by replacing a specified interior color instead of searching for a boundary color.
- Pitteway-Watkinson Algorithm: This algorithm is a modification to Bresenham’s algorithm. Depending of the area of overlap of the line plus the pixel, each pixel is given an intensity; therefore, the effect of antialiasing is reduced due to the blurring effect which goes along the line edges.
- Rigid-body Transformation: Its a translation which moves objects without deforming them.
- Cohen-Sutherland Line Clipping Algorithm: Algorithm for fast line clipping. There are chances of clipping a single line segment multiple times.
- Cyrus–Beck Line Clipping Algorithm: Fast parametric line-clipping algorithm.
- Liang-Barsky Line Clipping Algorithm: simplified and optimized version of Cyrus-Beck line clipping algorithm for rectangular clip window.
- Nicholl–Lee–Nicholl Line Clipping Algorithm: Fast line clipping algorithm which reduces the chances of clipping a single line segment multiple times.
- Fast Clipping Algorithm: Using a nine area grid, start and end positions are classified. There exist some similarities between this algorithm and Cohen-Sutherland algorithm; however, this algorithm may have to iterate several times.
- O(log N) Algorithm: Vertices are classified against a given line using an implicit form.
- Skala Algorithm: This algorithm is use for line or line segment clipping against rectangular window and/or convex polygon.
- Sutherland-Hodgman Polygon Clipping Algorithm: Method for clipping a convex-polygon fill area.
- Weiler-Atherton Polygon Clipping Algorithm: Polygon-clipping used for clip a fill area that can be a concave polygon or convex polygon.
- All-or-None String-Clipping Strategy: Display only those strings that are inside the clipping window.
- All-or-None Character-Clipping Strategy: Display only those characters that are completed inside the clipping window.
- Character-Clipping Strategy: Clip the components of individual characters.
- Natural Cubic Splines: Used for spline curves in which two adjacent curve sections have the same first and second parametric derivatives at their common boundary.
- Hermite Interpolation: Interpolating piecewise cubic polynomial in which each control point is an specified tangent.
- Cardinal Splines: They are similar to Hermite splines; however, the user do not input the values for the endpoint tangents.
- Catmull-Rom Splines: Also known as Overhauser splines. They are cardinal splines in which the value of the tension is zero.
- Kochanek-Bartels Splines: These splines are an extension of the cardinal splines. They have two additional parameters which provide a further flexibility when adjusting the shapes of the curve sections.
- Bézier Spline Curves: This kind of spline can be fitted with any number of control points. The number of control points and their relative position determine the degree of the Bézier polynomial.
- Bézier Surfaces: Object surface designed using two sets of Bézier curves.
- B-Spline Curves: Similar to Bézier splines since they are generated by approximating a set of control points. However, the degree of polynomial are set independently of the number of control points plus these control points can be located over the shape of the spline.
- Uniform Periodic B-Spline Curves: This kind of curve is the result of a constant spacing between the knot values.
- Open Uniform B-Spline Curves: Special type of uniform B-Spline. With exception of the ends, the knot spacing is uniform plus the knot values are repeated a certain number of times.
- Non-uniform B-Spline Curves: Multiple internal knots values and unequal spacing between these knots values can be chosen.
- B-Spline Surfaces: By using a Cartesian product of B-Spline blending functions, we can obtain a vector point over the surface.
- Beta-Splines: They are formulated by imposing geometric continuity conditions over the first and second parametric derivatives.
- Rational Splines: The ratio of two spline functions.
- Horner’s Rule: Method for polynomial evaluation by performing successive factoring.
- Forward-Difference Calculations: By generating successive values recursively, this method can evaluate polynomial functions fast.
- Recursive Spline-Subdivision: Method for repeatedly division of a given curve section in half by increasing the number of control points at each division.
- Sweep Representation: Construction techniques use for the construction of three-dimensional objects.
- Constructive Solid-Geometry Methods: Also known as constructive solid geometry (CSG). Solid objects are constructed by applying the union, intersection, or difference operation of two other solid objects.
© 2011 – 2017, Alejandro G. Carlstein Ramos Mejia. All rights reserved.
