# Java Programming Examples on Computational Geometry Problems & Algorithms

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

The following section contains programs on Robust Geometric Primitives. It explains how to find the area of a triangle and volume of Tetrahedron using determinant method. It also explains how to check whether a point lies below, above or on the line. Other Programs like how to check whether a point lies inside, outside or on the circle. This section also contains programs on Implementation of Slicker Algorithm that avoids Triangulation and Directed Segment Problems.

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

## 2. Java Programming examples on “Convex Hull”

The following section deals with implementation of graham scan Algorithm, Gift Wrapping Algorithm, jarvis march and quick hull algorithm to find the convex hull. This section also explains other algorithms and methods like chan’s algorithm, incremental method, divide and conquer method as well as prune and search method to find the convex hull.

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

## 3. Java Programming examples on “Triangulation”

The following section deals with implementation of Triangulation, delaunay triangulation, triangle, fortune’s sweep2 code and flip algorithms.

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

## 4. Java Programming examples on “Voronoi Diagrams”

The following section demonstrates the implementation of Voronoi Diagrams and its Problems by using fortune’s algorithm, lloyd’s algorithm, bowyer-watson algorithm, graphs, divide and conquer Algorithms.

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

## 5. Java Programming examples on “Nearest Neighbor Search”

This section contains a program to find the nearest neighbour using linear search, dynamic data set, static data set, k-d tree search and voronoi diagrams.

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

## 6. Java Programming examples on “Range Search”

The programs in this section performs operations like insertion, deletion and searching in K-D Tree, 2-Dimension K-D Tree, 1-Dimensional and 3-Dimensional Range Querys.

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

## 7. Java Programming examples on “Point Location”

This section contains a program to find the location of points by using K*K Grid, triangulation, k-d trees, slab method and trapezoidal decomposition.

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

## 8. Java Programming examples on “Intersection Detection”

The 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.

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

## 9. Java Programming examples on “Bin Packing “

The following 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.

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

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

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

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

## 11. Java Programming examples on “Simplifying Polygons”

The following section demonstrates the implementation of douglas-peucker and chazelle’s linear time triangulation algorithm.

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

## 12. Java Programming examples on “Shape Similarity”

The program in this section performs housdorff based image comparison.

Java Program to Perform Housdorff based Image Comparison |

## 13. Java Programming examples on “Motion Planning”

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

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

## 14. Java Programming examples on “Maintaining Line Arrangements”

The programs in this section performs degeneracy testing, intersection detection and insertion 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.

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

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