This is a Java Program to Implement Jarvis Algorithm. Jarvis algorithm or the gift wrapping algorithm is an algorithm for computing the convex hull of a given set of points.
Here is the source code of the Java Program to Implement Jarvis Algorithm. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.
/** ** Java Program to Implement Jarvis Algorithm **/ import java.util.Scanner; import java.util.Arrays; /** Class point **/ class Point { int x, y; } /** Class Jarvis **/ public class Jarvis { private boolean CCW(Point p, Point q, Point r) { int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y); if (val >= 0) return false; return true; } public void convexHull(Point[] points) { int n = points.length; /** if less than 3 points return **/ if (n < 3) return; int[] next = new int[n]; Arrays.fill(next, -1); /** find the leftmost point **/ int leftMost = 0; for (int i = 1; i < n; i++) if (points[i].x < points[leftMost].x) leftMost = i; int p = leftMost, q; /** iterate till p becomes leftMost **/ do { /** wrapping **/ q = (p + 1) % n; for (int i = 0; i < n; i++) if (CCW(points[p], points[i], points[q])) q = i; next[p] = q; p = q; } while (p != leftMost); /** Display result **/ display(points, next); } public void display(Point[] points, int[] next) { System.out.println("\nConvex Hull points : "); for (int i = 0; i < next.length; i++) if (next[i] != -1) System.out.println("("+ points[i].x +", "+ points[i].y +")"); } /** Main function **/ public static void main (String[] args) { Scanner scan = new Scanner(System.in); System.out.println("Jarvis Algorithm Test\n"); /** Make an object of Jarvis class **/ Jarvis j = new Jarvis(); System.out.println("Enter number of points n :"); int n = scan.nextInt(); Point[] points = new Point[n]; System.out.println("Enter "+ n +" x, y cordinates"); for (int i = 0; i < n; i++) { points[i] = new Point(); points[i].x = scan.nextInt(); points[i].y = scan.nextInt(); } j.convexHull(points); } }
Jarvis Algorithm Test Enter number of points n : 8 Enter 8 x, y cordinates 0 3 4 2 3 5 5 3 3 0 1 1 1 2 2 2 Convex Hull points : (0, 3) (3, 5) (5, 3) (3, 0) (1, 1)
Related posts:
How to Convert List to Map in Java
Intro to Inversion of Control and Dependency Injection with Spring
Registration with Spring Security – Password Encoding
New in Spring Security OAuth2 – Verify Claims
REST Web service: Upload và Download file với Jersey 2.x
Validate email address exists or not by Java Code
Java Program to Generate All Pairs of Subsets Whose Union Make the Set
The “final” Keyword in Java
Spring Data Java 8 Support
Java Program to Use the Bellman-Ford Algorithm to Find the Shortest Path
Các nguyên lý thiết kế hướng đối tượng – SOLID
Spring REST API + OAuth2 + Angular
How to Count Duplicate Elements in Arraylist
So sánh HashMap và HashSet trong Java
Java Program to Compute the Area of a Triangle Using Determinants
Map to String Conversion in Java
Working with Kotlin and JPA
Java Program to Implement Johnson’s Algorithm
Java Program to Find Minimum Element in an Array using Linear Search
Java Program to Check whether Graph is Biconnected
Send email with SMTPS (eg. Google GMail)
Java Program to Find Basis and Dimension of a Matrix
Removing Elements from Java Collections
Giới thiệu Google Guice – Injection, Scope
ETL with Spring Cloud Data Flow
Giới thiệu Java 8
Spring Boot - Admin Client
Guide to ThreadLocalRandom in Java
How To Serialize and Deserialize Enums with Jackson
Using Optional with Jackson
Jackson Unmarshalling JSON with Unknown Properties
Primitive Type Streams in Java 8