Poison wrapping algorithm

from Wikipedia, the free encyclopedia
Animation of the poison wrapping algorithm. The red lines show the stretches of the convex hull that have already been found, the black line shows the current best, and the green line shows the route that is currently being checked.

The poison wrapping algorithm , also called Jarvis-March , is an algorithm for calculating the convex hull of a set of points in two-dimensional space. It was published in 1973 by RA Jarvis. The algorithm is one of the " output-sensitive " (English output-sensitive ) algorithms.

description

Given a set of points in a plane. The point with the smallest ordinate is selected as the starting point . If there are several, the point with the smallest abscissa is selected from these . The starting point is thus part of the convex hull. Now any point is chosen from the set with which the starting point forms a straight line . Next, the remaining points from the set are checked to see whether a point lies to the left of this straight line. In this context, right and left result from the angle between the direction vector of the dividing line and the vector defined by the starting point of the straight line and the point to be checked. If this angle is smaller than 180 °, then the point is considered to be to the right of the straight line, for angles greater than 180 ° it is considered to be to the left of it. If a point is found to the left of the straight line, it forms a new straight line with it. Then the rest of the crowd is checked. This process is repeated for each point to the left of this straight line. If all points have been checked, the last point found is the next point on the convex hull. Now select the new starting point and repeat the entire process until the starting point is again.

For each point on the convex hull the complete set has to be traversed. This part is executed in a loop, with each loop pass having a runtime of . Let the number of points on the convex hull give a running time of . In the worst case , when all points lie on the convex hull, this results in a running time of . Since the algorithm depends on the number of points on the convex hull, it belongs to the so-called output-sensitive algorithms.

Pseudocode

  jarvis(S)
    startpunkt = Punkt mit kleinster Ordinate
    i = 0
    wiederhole
        P[i] = startpunkt
        endpunkt = S[0]
        wenn startpunkt == endpunkt
          endpunkt = S[1]
        für j von 1 bis |S|
          ist (endpunkt == startpunkt) oder (S[j] links von der Geraden zwischen startpunkt und endpunkt)
            endpunkt = S[j]
        startpunkt = endpunkt
        i++
    bis endpunkt == P[0]

literature

Web links