# C++ Programming Examples on Computational Geometry Problems & Algorithms

## 1. C++ Programming examples on “Robust Geometric Primitives”

A determinant is a value associated with a square matrix. Delaunay triangulation algorithm to create an index list that can be used directly in the DirectX or OpenGL functions. Slicker algorithm assumes the usual mathematical convention that positive y points upwards. The following section contains C++ programs on Robust Geometric Primitives. It explains how to check whether point lies between below, above or on the line. It calculates cross product of two vectors, explains how to find the triangle area and tetrahedron volume using determinants. This section also contains programs on Implementation of Slicker Algorithm that avoids Triangulation, delaunay triangulation algorithm and Directed Segment Problems.

C++ Program to Apply Above-Below-on Test to Find the Position of a Point with respect to a Line C++ Program to Compute the Area of a Triangle Using Determinants C++ Program to Compute the Volume of a Tetrahedron Using Determinants C++ Program to Find the Area of any Polygon Using Triangulation C++ Program to Implement Slicker Algorithm that avoids Triangulation to Find Area of a Polygon C++ Program to Use Above Below Primitive to Test Whether Two Lines Intersect C++ Program to Check if a Point d lies Inside or Outside a Circle Defined by Points a, b, c in a Plane C++ Program to Apply Delaunay Triangulation Algorithm C++ Program to Solve the Directed Segment Problem C++ Program to Solve the Directed Segment Problem C++ Program to Compute Cross Product of Two Vectors |

## 2. C++ Programming examples on “Convex Hull”

Graham’s scan is a method of computing the convex hull of a finite set of points in the plane with time complexity O(n log n). Gift wrapping algorithm is an algorithm for computing the convex hull of a given set of points. Quick Hull algorithm, which is one of the easiest to implement and has a reasonable expected running time of O(n log n). The C++ programs in this section deals with the algorithms and methods to find convex hull they are graham scan algorithm, jarvis march, gift wrapping algorithm, quick hull algorithm, chan’s algorithm, prune and search methods, incremental method, divide and conquer methods.

C++ Program to Implement Graham Scan Algorithm to Find the Convex Hull C++ Program to Implement Gift Wrapping Algorithm in Two Dimensions C++ Program to Implement Jarvis March to Find the Convex Hull C++ Program to Implement Quick Hull Algorithm to Find Convex Hull C++ Program to Implement Chan’s Algorithm C++ Program to Implement Incremental Method to Find the Convex Hull C++ Program to Implement Divide and Conquer Method to Find the Convex Hull C++ Program to Implement Prune and Search Method to Find the Convex Hull |

## 3. C++ Programming examples on “Triangulation”

Fortune’s Sweep2 is a widely used 2D code for Voronoi diagrams and Delaunay triangulations. The C++ programs in this section demonstrates the implementation of Triangulation, delaunay triangulation, triangle, sweephull for fast delaunay triangulation, flip algorithm for non-delaunay triangles, triangulate by adding to the convex-hull diagonals.

C++ Program to Triangulate by Adding to the Convex-Hull Diagonals from the First Point to All of the Others C++ Program to Implement Delaunay Triangulation to Perform Triangulation C++ Program to Implement “Triangle” by Jonathan Shewchuk C++ Program to Implement Fortune’s Sweep2 Code C++ Program to Implement Flip Algorithm for Non-Delaunay Triangles C++ Program to Use SweepHull for Fast Delaunay Triangulation |

## 4. C++ Programming examples on “Voronoi Diagrams”

Fortune’s algorithm is a sweep line algorithm for generating a Voronoi diagram from a set of points in a plane using O(n log n) time and O(n) space. The LBG-algorithm or Lloyd’s algorithm allows clustering of vectors of any dimension. Bowyer-Watson algorithm is an insertion algorithm, it builds the Delaunay triangulation one vertex at a time. The C++ programs in this section deals with implementation of voronoi diagram using fortune’s, divide and conquer algorithms, solves voronoi diagram problems using graphs. This section also explains other algorithms like lloyd’s and bowyer-watson algorithms.

C++ Program to Implement Voronoi Diagram Using Fortune’s Algorithm C++ Program to Implement Voronoi Diagram Using Divide and Conquer Algorithm C++ Program to Implement Lloyd’s Algorithm C++ Program to Implement Voronoi Diagram Problem Using Graphs C++ Program to Implement Bowyer-Watson Algorithm |

## 5. C++ Programming examples on “Nearest Neighbor Search”

K-D Tree Search is used for organizing some number of points in a space with k dimensions, mainly used in range and nearest neighbor searches. Static data structure is an collection of data in memory that is fixed in size. Dynamic data set is an collection of data in memory that has the flexibility to grow in size. Linear Search is a method for finding a target value within a list. This section contains C++ programs to find the nearest neighbour using k-d tree search, voronoi diagram, linear search, static and dynamic data set.

C++ Program to Find the Nearest Neighbour Using K-D Tree Search C++ Program to Find Nearest Neighbour Using Voronoi Diagram C++ Program to Find Nearest Neighbour for Static Data Set C++ Program to Find Nearest Neighbour for Dynamic Data Set C++ Program to Find Nearest Neighbour Using Linear Search |

## 6. C++ Programming examples on “Range Search”

A K-D Tree is a binary search tree where data in each node is a K-Dimensional point in space. The C++ programs in this section performs operations like insertion, searching and deletion in k-d tree and 2-dimensional k-d tree, other operations like range searching in 2-dimension, 1-dimensional and 3-dimensional range query.

C++ Program to Construct K-D Tree for 2 Dimensional Data (assume static data) C++ Program to Perform Insertion in a 2 Dimension K-D Tree C++ Program to Perform Searching in a 2-Dimension K-D Tree C++ Program to Find the Node with Minimum Value (with respect to that cutting Dimension) for a Given Node, and a Cutting Dimension C++ Program to Perform Deletion in K-D Tree C++ Program to Perform 3-Dimensional Range Query C++ Program to Perform 1-Dimensional Range Query C++ Program to Perform Range Query in 2-Dimension C++ Program to Perform Dynamic Range Searching where Data is Dynamically Inserted or Deleted C++ Program to Perform Partial Key Search in a K-D Tree |

## 7. C++ Programming examples on “Point Location”

This section contains C++ program to find the location of points in polygon and k-d trees by using triangulation, k*k grid construction, three dimensions, slab method and trapezoidal decomposition.

C++ Program to Check Whether a Given Point is in a Given Polygon C++ Program to Find Location of a Point by Triangulation of the Given Polygon C++ Program to Find Location of a Point by Constructing K*K Grid on a Given Polygon C++ Program to Find Location of a Point Placed in Three Dimensions Using K-D Trees C++ Program to Find the Point Location Using Slab Method C++ Program to Find Location of a Point by Trapezoidal Decomposition |

## 8. C++ Programming examples on “Intersection Detection”

The C++ programs in this section performs Intersection Testing by doing sphere sphere, interval-interval, sphere-AABB, AABB-AABB, ray-sphere, ray-polygon and brute force collision detection. It also performs polygon containment testing.

C++ Program to Perform Sphere Sphere Intersection Testing C++ Program to Perform Interval-Interval Intersection Testing C++ Program to Perform AABB-AABB Intersection Testing C++ Program to Perform Sphere-AABB Intersection Testing C++ Program to Perform Ray-Sphere Intersection Testing C++ Program to Find Ray-Polygon Intersection Point C++ Program to Perform Polygon Containment Test C++ Program to Perform Brute Force Collision Detection C++ Program to Check Visibility of a Point X to Y C++ Program to Implement Plane Sweep Algorithms for Intersection of Lines |

## 9. C++ Programming examples on “Bin Packing “

The C++ programs in this section demonstrates the implementation of First fit Decreasing for 1-d objects using m bins and binary tree, This section also contains the program to find largest rectangle area in a histogram.

C++ Program to Implement First Fit Decreasing for 1-D Objects and M Bins C++ Program to Implement First Fit Decreasing for 1-D Objects Using Binary Tree C++ Program to Find the Minimum Area of a Rectangle to Fit N Rectangles of Different Sizes C++ Program to Find Largest Rectangular Area in a Histogram |

## 10. C++ Programming examples on “Polygon Partitioning”

The C++ programs in this section performs optimal convex partitioning using dynamic programming and triangulation partition, This section also explains hertel-mehlhorn heuristic for convex decomposition.

C++ Program to Implement Hertel-Mehlhorn Heuristic for Convex Decomposition Using Diagonals C++ Program to Delete All Lines from a Polygon such that it becomes a Convex Polygon C++ Program to Perform Triangulation to Partition the Polygon in Triangles C++ Program to Perform Optimal Convex Partitioning Using Dynamic Programming |

## 11. C++ Programming examples on “Simplifying Polygons”

Douglas–Peucker algorithm is an algorithm for reducing the number of points in a curve that is approximated by a series of points. The C++ programs in this section deals with the implementation of chazelle’s linear time triangulation and douglas-peucker algorithms.

C++ Program for Douglas-Peucker Algorithm Implementation C++ Program to Implement Chazelle’s Linear Time Triangulation Algorithm |

## 12. C++ Programming examples on “Shape Similarity”

The C++ program in this section performs image comparison using housdorff.

C++ Program to Perform Housdorff based Image Comparison |

## 13. C++ Programming examples on “Motion Planning”

This section contains C++ programs to find the set of legal configuration space points by randon sampling. Constructing visibility graph of polygonal obstacles.

C++ Program to Construct a Visibility Graph of the Polygonal Obstacles C++ Program to Find a Set of Legal Configuration Space Points by Randon Sampling |

## 14. C++ Programming examples on “Maintaining Line Arrangements”

The C++ programs in this section performs degeneracy testing, duality transformation, insertion and intersection detection of line arrangements. It also explains how to check given points lie on a single lino or not. This section contains programs on sweepline and bresenham line algorithms.

C++ Program to Perform Degeneracy Testing on a Set of n Lines C++ Program to Perform Insertion in a Line Arrangement C++ Program to Construct a Full Arrangement of n Lines C++ Program to Perform Intersection Detection of Line Arrangement C++ Program to Find a Point P that Satisfies Maximum Number of such Constraints for a Given Set of Constraints of type y<ax+b C++ Program to Show the Duality Transformation of Line and Point C++ Program to Check if a Given Set of Three Points Lie on a Single Line or Not C++ Program to Implement Sweepline Algorithm C++ Program to Solve N-Queen Problem |

**Here’s the list of 1000 C++ Algorithms, Problems & Programming Examples.**