Can I Ruin Someones Computser With Their Ip

Jarvis Algorithm for Convex lock with Java

This time we will see how the algorithm for the fastening Jarvis convex. Let's see what the algorithm is:

Well, the pseudocode is very clear, but let's see how to work with a small set of points. Suppose we have the following set of points:

First select the lowest point coordinate and call p .

Then choose the point which forms the smallest angle with the horizontal, we will call and add pa q battery that will keep the points that form the lock convex.

We enter the loop and we will begin to find points that are convex lock having a condition that it must be the smallest angle with the line shape points and p q .

In the first iteration this would happen:

Point 3 is the one that forms the smallest angle at which it will become part of the lock convex. Go to the next iteration.

The next point is now the point 2. Point 3 and became part of the lock convex. Now for the next iteration.

We see that the lowest point angle is the starting point, the stop condition also tells us that q! = start. And the next iteration will not run because we will be something like this:

The loop is completed and the lock convex plot points stored in our battery, staying well:

Here I leave a aplet to verify the performance of our algorithm.





The implementation of the Jarvis algorithm is as follows:

 / ** 
 * * @ author Rolando 
 
 * / public static List 
 \u0026lt;Point2D> jarvis (List \u0026lt;Point2D> tag) {List 
 \u0026lt;Point2D> \u0026lt;Point2D> lock = new ArrayList (); 
 double min = 0, ang = 0; 
 / / O (n) 
 Point2D.Double Point2D p = new (); 
 Point2D q = Point2D.Double new (); 
 pInicio = new Point2D.Double Point2D (); 
 posMin = new Point2D.Double Point2D (); 
 p = menorCoordenadaY (tag); 
 pInicio = p; 
 calcularMenorAngulo q = (tag, p ) 
 cerradura.add (p); 
 while (q! = pInicio) {
 cerradura.add (q); 
 min = 180; 
 for (Point2D aux: tag) {
 if (aux! = q) 
 {ang = angle (q, p, aux); 
 if (ang \u0026lt;min) {
 posMin = aux; 
 min = ang; 
 
}}} 
 
 p = q, q = posMin 
; 
 
} return lock;} 
 
 

The complete source code can be downloaded here:

Well, I hope you find it useful. Soon I'll post QuickHull algorithm. Do not forget to leave your comments and criticisms.

You might also be interested in these posts:
http://rolandopalermo.blogspot.com/2010/09/algoritmo-de-graham-para-la-cerradura.html
http://rolandopalermo.blogspot.com/2010/11/quickhull-java-convex-hull.html