2D空間内の最大点をカバーする矩形位置を見つける

X点を持つ2D空間が与えられた場合、固定小数点矩形をどこに配置すれば効率的にそれらのX点の最大数をカバーできるのでしょうか？2D空間内の最大点をカバーする矩形位置を見つける

ビルドしている2Dゲームにビューポートを配置するには、これらの線に沿って何かが必要です。

2015-09-06 Harry Mexican

あなたの四角形を回すために許可されている、または側面にはXとY軸に平行していますか？ – dasblinkenlight

ポイントの最小値と最大値XとYを決定し、そのエクステント矩形を構成してみませんか？矩形の軸が回転している場合は、それは最小面積の境界矩形であり、エクステント矩形のようなすべての点をカバーしますが、面積は小さくなります。最初のオプションは実装が簡単で、後者は難しいです。 –

は矩形を回転させることができません –

ポイントを左から右にソートします。一番左の点にはleftポインタを設定し、left + widthにある右端の点にはrightポインタを設定します。その後、最後のポイントになるまで、毎回rightポインターの位置を再計算し、すべてのポイントを繰り返し処理します。
左右のポイントの各サブセットを上から下にソートします。最も高いポイントにtopポインターを設定し、top + heightに該当する最も低いポイントにbottomポインターを設定します。次に、すべてのポイントを繰り返し、最後のポイントになるまで毎回bottomポインターの位置を再計算します。
左、右、上、下のポイントのサブセットごとに、それが持つポイントの数を確認し、最適なサブセットを保存します。
最適なサブセットが見つかると、四角形の中心は最も左と右のポイントの中間、最も高いポイントと最も低いポイントの中間になります。

以下は、Javascriptでの単純な実装であり、多くの点で最適化できます。コードスニペットを実行して、ランダムなデータで結果を確認します。

function placeRectangle(p, width, height) { 
 
    var optimal, max = 0; 
 
    var points = p.slice(); 
 
    points.sort(horizontal); 
 

 
    for (var left = 0, right = 0; left < points.length; left++) { 
 
     while (right < points.length && points[right].x <= points[left].x + width) ++right; 
 
     var column = points.slice(left, right); 
 
     column.sort(vertical); 
 

 
     for (var top = 0, bottom = 0; top < column.length; top++) { 
 
      while (bottom < column.length && column[bottom].y <= column[top].y + height) ++bottom; 
 
      if (bottom - top > max) { 
 
       max = bottom - top; 
 
       optimal = column.slice(top, bottom); 
 
      } 
 
      if (bottom == column.length) break; 
 
     } 
 
     if (right == points.length) break; 
 
    } 
 

 
    var left = undefined, right = undefined, top = optimal[0].y, bottom = optimal[optimal.length - 1].y; 
 
    for (var i = 0; i < optimal.length; i++) { 
 
     var x = optimal[i].x; 
 
     if (left == undefined || x < left) left = x; 
 
     if (right == undefined || x > right) right = x; 
 
    } 
 
    return {x: (left + right)/2, y: (top + bottom)/2}; 
 

 
    function horizontal(a, b) { 
 
     return a.x - b.x; 
 
    } 
 

 
    function vertical(a, b) { 
 
     return a.y - b.y; 
 
    } 
 
} 
 

 
var width = 160, height = 90, points = []; 
 
for (var i = 0; i < 10; i++) points[i] = {x: Math.round(Math.random() * 300), y: Math.round(Math.random() * 200)}; 
 
var rectangle = placeRectangle(points, width, height); 
 

 
// SHOW RESULT IN CANVAS 
 
var canvas = document.getElementById("canvas"); 
 
canvas.width = 300; canvas.height = 200; 
 
canvas = canvas.getContext("2d"); 
 
paintRectangle(canvas, rectangle.x - width/2, rectangle.y - height/2, width, height, 1, "red"); 
 
for (var i in points) paintDot(canvas, points[i].x, points[i].y, 2, "blue"); 
 
function paintDot(canvas, x, y, size, color) { 
 
    canvas.beginPath(); 
 
    canvas.arc(x, y, size, 0, 6.2831853); 
 
    canvas.closePath(); 
 
    canvas.fillStyle = color; 
 
    canvas.fill(); 
 
} 
 
function paintRectangle(canvas, x, y, width, height, line, color) { 
 
    canvas.beginPath(); 
 
    canvas.rect(x, y, width, height); 
 
    canvas.closePath(); 
 
    canvas.lineWidth = line; 
 
    canvas.strokeStyle = color; 
 
    canvas.stroke(); 
 
}

<BODY STYLE="margin: 0; border: 0; padding: 0;"> 
 
<CANVAS ID="canvas" STYLE="width: 300px; height: 200px; float: left; background-color: #F8F8F8;"></CANVAS> 
 
</BODY>

出典

2015-09-08 06:42:47 m69

これは、ばかばかしく完全な答えです。あなたがクリックできるランニングコード！良い仕事、それを受け入れる。私はそれを使用するようには見えませんが、私はいくつかのゲームプレイを変更して、質問の要件をこれ以上実行する必要がないためです。それはとにかく高価すぎると思います。 60fps +すべてのポイントですべてのフレームを実行する必要が絶えず動いている。並べ替えがそれを殺した可能性があります。いずれにしても、ありがとう。 –

@HarryMexican私はアイデアを示すコードを書いたが、実際にこれを行うことができるかどうかは、実際に何点あり、どれくらい速くする必要があるかに依存する。ゲームのフレームレートでそれを動かすことは、ほんの一握り以上の点では問題になるでしょう。アルゴリズムはソートに依存しているため、スキップして効率を上げる方法はありません。矩形を離れる直前の点だけを見て徐々に近づけるアルゴリズムは、おそらくあなたの場合より効率的です。 – m69

いずれにしても、それは面白い思考実験です。あなたがそれを書いて何かを得て、それがこの種のアルゴリズムを探している他の人に役立つことを願っています。:) –

2D空間内の最大点をカバーする矩形位置を見つける

答えて

関連する問題