What Happened Sandramodel

Algorithm for Convex Lock Simulation in Java with Radius Server in Debian

For in this post I will describe what related to QuickHull algorithm for finding the convex hull of a set of points. Obviously the scheme is the same as has been shown throughout all of my post related to computational geometry.

First of all, we understand what this algorithm, and no better than by the pseudocode and an example where to test your performance. QuickHull algorithm tells us that:

So, given a point cloud as the picture:

The algorithm tells us that as a first step we select the leftmost point and the point most right, is something like

Then we separated into two sets, which are on the right of the segment formed by the two points found above, and those who are left. These sets will be called S1 and S2 respectively.

add to the lock point min points to find the whole process S1, the max point and finally the points which we find to process the set S2.

in the stack where items are stored there are two elements that are a target background color, this is because I want to indicate that these positions are inserted sets of points to be found recursively, given the nature of the algorithm.

S1 will process now. This part is called the function responsible for processing the subset of puntosd. What you do is choose the farthest point of the line formed by the points to and b , which are the entries for this subprocedure. The furthest point is the point 6 and this point has no point, neither right nor left, as indicated by the pseudocode shown. Then the result of processing the subset S1 is the point 6.

Now is the turn of the subset S2. The furthest point is the point 2, which in forming the segment cb has no points on your right, but if your right (yellowfin area), but to be ac segment, presents a right point . Something here is that the rescue of proesamiento S2 will return more than one point.

Then add the result of processing subset A (yellow region) on the stack and then point 2.

Now, following the above processing, the result of processing the yellow area, we will return only the point 3 which will be added to the stack and end with this recursive algorithm to meet the end condition ( if noEsVacio (s) ) because we have no points to be processed.

using the points stored in the battery can generate the convex hull of our cloud of points, ending with this whole process.

Obviously all this must be contrasted with a model to certify that the foregoing is true and good, here are a simulation, interactive way, we will verify that the algorithm works .

QuickHull The implementation of the algorithm is as follows: public static List

 \u0026lt;Point2D> quickHull (List \u0026lt;Point2D> tag) {List \u0026lt;Point2D> 
 lock = new ArrayList \u0026lt; Point2D> (); 
 min_x = new Point2D Point2D.Double (Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY); 
 max_x = new Point2D Point2D.Double (Double.NEGATIVE_INFINITY, Double.NEGATIVE_INFINITY); 
 for (Point2D aux: cloud) 
 {if (Aux. getX () = \u0026lt;min_x.getX()) {
 min_x aux; 
} 
 if(aux.getX()> max_x.getX ()) {
 max_x = aux;}} 
 
 
 \u0026lt;Point2D> List S1 = puntosLado (min_x, max_x, cloud); 
 List \u0026lt;Point2D> puntosLado S2 = (max_x, min_x, cloud); 
 cerradura.add (min_x); 
 cerradura.addAll (findHull (min_x, max_x, S1)); 
 cerradura.add (max_x) 
 cerradura.addAll (findHull (max_x, min_x, S2)); 
 return lock; 
} public static List 
 
 \u0026lt;Point2D> findHull (Point2D a, Point2D b , S \u0026lt;Point2D> List) {List 
 \u0026lt;Point2D> \u0026lt;Point2D> lock = new ArrayList (); 
 Point2D.Double Point2D c = new (); 
 if (! S.isEmpty ()) {List \u0026lt;Point2D> 
 \u0026lt;Point2D> A = new ArrayList (); 
 \u0026lt;Point2D> List \u0026lt;Point2D> B = new ArrayList (); 
 puntosMayorArea c = (a, b, S); 
 puntosLado A = (a, c, S); 
 puntosLado B = (c, b, S); 
 cerradura.addAll (findHull (a, c, A)); 
 cerradura.add (c); 
 cerradura.addAll (findHull (c, b, B));} 
 
 return lock;} 
 
 

The complete source code can be downloaded here:

Well, I hope you find it useful. Soon I'll post other algorithms for convex lock. Do not forget to leave your comments and criticisms.

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