# C Programming Examples on Computational Geometry Problems & Algorithms

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

Determinants are used to define the characteristic polynomial of a matrix. This section contains C programs on Robust Geometric Primitives. It explains how to check whether a point lies below, above or on the line. It also explains how to check whether a point lies inside, outside or on the circle. Other programs like how to find the area of a triangle and volume of Tetrahedron using determinant method. This section also contains programs on Implementation of Slicker Algorithm that avoids Triangulation and solves 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”

Convex hull is the smallest convex polygon containing the points. Quick Hull algorithm is one of the easiest to implement and has a reasonable expected running time of O(n log n). Jarvis March is a process of wrapping a piece of string around the points. Graham Scan Algorithm explicitly sorts the points in O(n log n) and then applies a linear-time scanning algorithm to finish building the hull. 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 code is a widely used 2D code for Voronoi diagrams and Delaunay triangulations. This section contains C programs on implementation of delaunay triangulation, triangle, fortunes sweep2 code, sweephull for fast delaunay triangulation and flip algorithm for non-delaunay triangles.

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”

Voronoi diagram is a famous structure of computational geometry. Fortune’s algorithm is a sweep line algorithm for generating a Voronoi diagram from a set of points in a plane using time and space. Lloyd’s algorithm allows clustering of vectors of any dimension. Bowyer-Watson Algorithm is used to obtain a Voronoi diagram of the points. 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”

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. Voronoi diagram is a famous structure of computational geometry. Static data structure is an collection of data in memory that is fixed in size. K-D Tree Search is used for organizing some number of points in a space with k dimensions. 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”

k-d tree is a space-partitioning data structure for organizing points in a k-dimensional space. k-d trees are a useful data structure for several applications. 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”

Trapezoidal decomposition can be used as a point-location algorithm. This section contains C programs on finding the location of point by using polygon triangulation, k*k grid construction, three dimensions using k-d trees, 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”

Intersecting a ray with a sphere is the simplest form of ray-geometry intersection test which shows many raytracers images of spheres. Brute-force approach that compares each object bounding volume with all others bounding volumes. Containment in convex polygons can be tested by adding the angles subtended by the edges from the point. 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 “

Bin packing is the problem of trying to find a set of objects to pack into containers. First Fit Decreasing strategy, operates by first sorting the items to be inserted in decreasing order by their sizes, and then inserting each item into the first bin. The C programs in this section deals with implementation of First fit Decreasing Bin Packing algorithm using m bins and binary tree, This section also contains the program to find minimum area of a rectangle to fit n rectangles of different sizes.

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 |

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

Polygon Partitioning is a polygon as the closed finite connected region of the plane bounded by vertices and edges. 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 douglas-peucker and chazelle’s linear time triangulation algorithm.

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 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. The other programs in this section Constructs 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”

Sweepline Algorithm first sorts the end points along the x axis from left to right, then it passes a vertical line through all points from left to right and checks for intersections. 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 and implementation of sweepline algorithm.

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 |

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