グレアムスキャンアルゴリズムをさらに最適化して凸包を見つける方法はありますか？

Question

私はchanのアルゴリズムを使いました。それは私にとってははるかに良いとは思わない。 グレアムスキャンのソート部分を他のものと置き換える方法はありますか？ O（nlogn）時間をさらに短縮することができる。 Java実装が推奨されます。

Answer 1

ソートステップを最適化する最も良い方法は、凸包の一部ではない点を考慮しないようにすることです。これはAkl-Toussaintヒューリスティックhttp://www-cgrl.cs.mcgill.ca/~godfried/publications/fast.convex.hull.algorithm.pdfと呼ばれています。すべての頂点をすばやくスキャンし、四角形がポイントセットを形成していることを確認できます（4点を±（x + y）、±（xy）のすべての頂点の極値として得ることができます）。四角形。

この後、GrahamのスキャンまたはAndrewのモノトーン連鎖アルゴリズムを使用することができます。どちらもO（n log n）の複雑さです。 上記の@Chillのように、Chanの方法は最適ですです。

実際には、この方法は、フィルタリングなしでアルゴリズムの1つをポイントセットに適用するよりもはるかに高速です。

私が上にリンクした論文は、結論のセクションで「スローアウェイ」のアイデアを述べています。これはわずかな改善です。なぜなら、の大部分を捨てることができるのに対し、は四辺形自体を探しているからです。私は、このヒューリスティックのためのスニペットを添付しています。

/** 
* 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. 
// ...