Gibt es eine Möglichkeit, den Graham Scan Algorithmus weiter zu optimieren, um die konvexe Hülle zu finden?

Question

Ich ging durch chans Algorithmus. Es scheint mir nicht viel besser zu sein. Gibt es eine Möglichkeit, den Sortierbereich in Graham Scan durch etwas anderes zu ersetzen? so dass O (nlogn) -Zeit weiter reduziert werden konnte. Java-Implementierung ist bevorzugt.

Answer 1

Die beste Möglichkeit, den Sortierschritt zu optimieren, besteht darin, Punkte zu vermeiden, die nicht Teil der konvexen Hülle sind. Dies wird Akl-Toussaint Heuristik http://www-cgrl.cs.mcgill.ca/~godfried/publications/fast.convex.hull.algorithm.pdf genannt. Sie können schnell durch alle Scheitelpunkte scannen und finden ein Viereck, das den Punktsatz bildet (Sie können die vier Punkte als Extrema für alle Scheitelpunkte in ± (x + y), ± (xy)) erhalten, dann löschen Sie einfach alle Scheitelpunkte in diesem Viereck.

Danach können Sie Graham-Scan oder Andrew Monotone-Kette-Algorithmus verwenden-mein Favorit, beide sind von O (n log n) Komplexität. Beachten Sie, dass, wie @Chill in den obigen Kommentaren erwähnt, Chan's Methode optimal ist.

In der Praxis ist diese Methode viel schneller, als einen der Algorithmen ohne Filterung auf den Punktsatz anzuwenden.

Das oben verlinkte Papier erwähnt eine "Wegwerf" - Idee im Abschnitt "Schlussfolgerungen". Dies ist eine leichte Verbesserung, da wir die meisten Vertices während auf der Suche nach dem Viereck selbst wegwerfen können. Ich füge nur für diese Heuristik einen Ausschnitt bei.

/** 
* Given verts: Array(Points). 
*/ 

/* 
* if we have more than 100 points use Akl-Toussaint heuristic to remove 
* points that we know are surely not part of the hull. 
* S.G. Akl & Godfried Toussaint, 1977, "A Fast Convex-hull Algorithm" 
*/ 
if (verts.length > 100) { 
    var min = Math.min, 
     max = Math.max; 
    var minU = minL = maxU = maxL = verts[0]; 
    var minUval = minU.x - minU.y; 
    var minLval = minL.x + minL.y; 
    var maxUval = maxU.x + maxU.y; 
    var maxLval = maxL.x - maxL.y; 
    var xMin = yMin = xMax = yMax = 0; 
    var vertList = []; 
    for (i = 0 ; i < verts.length; ++i) { 
     var v = verts[i]; 
     var x = v.x; 
     var y = v.y; 
     if (!(x > xMin && x < xMax && y > yMin && y < yMax)) { 
      vertList.push(v); 
      var sum = x + y; 
      var diff = x - y; 
      if (diff < minUval) minU = v; 
      if (diff > maxLval) maxL = v; 
      if (sum < minLval) minL = v; 
      if (sum > maxUval) maxU = v; 
      minUval = minU.x - minU.y; 
      maxLval = maxL.x - maxL.y; 
      minLval = minL.x + minL.y; 
      maxUval = maxU.x + maxU.y; 
      xMin = max(minU.x, minL.x); 
      yMin = max(minL.y, maxL.y); 
      xMax = min(maxU.x, maxL.x); 
      yMax = min(minU.y, maxU.y); 
     } 
    } 

    // reset the vert's array, and do one more filtering pass 
    // on vertList 
    verts.length = 0; 
    for (i = 0 ; i < vertList.length; ++i) { 
     var v = vertList[i]; 
     var x = v.x; 
     var y = v.y; 
     if (!(x > xMin && x < xMax && y > yMin && y < yMax)) 
      verts.push(v); 
    } 
    // verts now only contains a subset of vertices. 
} 
// Run a convexhull algorithm on verts. 
// ...