# C Programming Examples on Computational Geometry Problems & Algorithms

This section covers C Programming Examples on Computational Geometry Problems & Algorithms. Every example program includes the description of the program, C code as well as output of the program. Here is the listing of C programming examples:

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

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”**

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”**

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”**

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”**

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”**

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”**

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”**

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 “**

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”**

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”**

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

**12. C Programming examples on “Shape Similarity”**

C Program to Perform Housdorff based Image Comparison |

**13. C Programming examples on “Motion Planning”**

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”**

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 |

If you want to learn implementations of all algorithms and programs in C,

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