点をkd 木として表します。
つまり、すべてのノードがポイントの 1 つを表し、すべての非リーフ ノードがそのノードの x または y 値で現在の領域を垂直または水平 (各レベルで交互に) に分割するバイナリ ツリーと考えることができます。
次に、クエリを実行します。
現在のノード = ルート
現在の面積 = 現在のノードの面積 (ツリーを再帰的に追跡/計算できます)
現在の領域が四角形の内部に完全に含まれている場合は、このノードが子として持つポイントの数を追加します (現在のノードの場合は +1)。
現在の領域が長方形の内側に完全にある場合は、何もしません。
現在の領域が長方形の中に部分的に含まれている場合:
エリアまたはポイントが長方形に含まれているかどうかを計算するのは簡単です。
各クエリは、ランダム データに対して平均で O(log n) 時間かかるはずです。
O(n) 時間かかる (つまり、ツリー全体/大部分を探索する必要がある)病理学的なケースが存在しますが。このようなケースの考えられる例の 1 つは、ほとんどのポイントが (軸が揃っていない) 長方形 (内側または外側) の端の周りにある場合です。つまり、上記の「何もしない」部分はほとんど適用されません。
古い回答（事前にポイントを前処理できない場合）：
側面/エッジが xy 軸として方向付けられた内接長方形にとどまるポイントをすばやく含めることで、パフォーマンスが向上する可能性があります (それほどではありませんが、長方形の方向によって異なります)。これにはある程度の事前計算が必要ですが、多くのポイントがあるという事実を考えると無視できます。
新しい答え:
rect入力長方形ですf1(point,rect)ポイントが長方形の内側にあるかどうかをチェックするものがあると仮定します。上記のものを使用できます。f2(shape,rect)。これは、形状が rect に完全に含まれているか、rect が形状に完全に含まれているか、形状と rect が交差するか、まったく交差しないかを示すことができます。f2) O(1)、または 2 つの辺で区切られ、無限に広がる 2D 平面内の領域 (たとえば、 xy 軸の正のセクション)取得したいのは、実行時に f1 と f2 を最小回数呼び出すアルゴリズムです。たとえば、（同じオーダーの）に比例するものlog(n)
そこで、2D 平面をm形状ごとに分割し、それぞれにp点が含まれるようにします。実行時に、各形状を f2 でチェックすると、4 つのケースが考えられます。
(O(p) )終了します。 (O(1) ) (O(p) )続行します。ケース 1 の場合は幸運ですぐにドロップする可能性がありますが、通常はすべての形状をチェックする必要があり、そのうちの少なくとも 1 つについては、含まれるすべてのポイントをチェックする必要があります。したがって、このアルゴリズムはO(p) + O(m). それを考慮してp * m = n、選択した場合、この方法で取得できる最高のものを取得しますp = m = sqrt(n)。O(sqrt(n) )(注: f1 を実行する回数は? この数は実際には長方形の形状に依存するため、たとえば長方形が非常に細長い場合、多くの領域と交差し、多くの f1 が呼び出されます。しかし、私は、長方形の測定値がn、またはsqrt(n):の順序と同じでないと仮定できlog(n)ますn。)
ここから強化できます。たとえば、形状間に隣接関係があると言えます。形状と長方形の間の重なりを最初に見つけたときは、隣接する形状のみをチェックします。ただし、チェックする必要がある形状の平均数は、とにかく約 p/2 とO(p/2) = (O(p) ). したがって、有効なゲインはありません。
本当の利点は、形状に階層を配置することです。
まず、すべてのポイントをチェックし、バインドされた値 max_x、max_y、min_x、min_y を見つけます。(これらの境界が > > n であると仮定しましょう。点の分布について前もって知ることができれば、目標とする最適化はまったく異なるものになります) log(n) 個の点を (前後に) 含む形状に空間を分割します。まず、xy 軸を使用して 2D 平面を 4 つの形状に分割します (バインドされた値に従って中央に配置することもできます)。これは、逆さまのピラミッドの最初のレベルになります。周期的: log(n) 点を超える点を含む領域ごとに、垂直線または水平線を使用して領域を半分に分割します (交互に行います)。1 つの境界が無限に設定されている場合、半分に分割するには、対応する境界値を使用します。分割された各領域にはポインターが含まれていますそれが分割されている地域に。新しい地域は、ピラミッドの第 2 レベルです。すべての領域に (約) log(n) ポイントが含まれるまで分割を続けます。リージョンが分割されると、「子」リージョンへのポインタが含まれます。私は自分のピラミッドを構築しました。逆さまのピラミッドのトップ レベルには n/log(n) の形状が含まれており、これはかなり大きいですが、重要なのは、log(n) のピラミッド レベルがあることです。注: 各レベルの各シェイプには、含まれるポイントの数がわかっています。注 2: この事前精緻化は、各ポイントを平均してピラミッド レベルごとに 1 回分析するため、その複雑さは O(n*(log(n) ) です。
入力で長方形を取得したら、f2 を使用して最初のレベルで形状をチェックします。
O(log(n))) 他の形状は破棄します。O(1)(O(log(n) )。ここで難しいのは、何個の図形を訪問するかということです。繰り返しますが、これは長方形の形状、接触する形状の数に依存します。ただし、各レベルでは、 に依存しない形状の数を訪問するため、訪問したn形状の数は に比例しO(log(n) )ます。
n は非常に大きいため、四角形の辺が交差する形状の数 (f1 への高価な呼び出しの原因となる) は よりもはるかに少ないと想定できますO(log(n) )。アルゴリズム全体はO(log(n) ).
最適化する方法は他にもありますが、何でも平均にとどまりますO(log(n) )
最後の注意: 空間を分割する方法は、多角形が持つ辺の数が制御されるようにする必要があります。これは、形状が多数の辺を持つことができる場合、ポイントの数に何らかの形で依存するためです (呼び出す関数によると)。g)、f2 は になりO(g(n) )、その複雑さは、チェックする必要がある形状の数に応じて、何かを掛けn直す必要があるため、おそらく良くありません。
三角形を作ります。abcd が四角形で x が点であるとするとarea(abx)+area(bcx)+area(cdx)+area(dax) equals area(abcd)、点がその内部にあるとします。
速度が問題で、メモリ/ディスク容量がそうでない場合は、次のことを検討してください。これは可能な限り最も効率的な方法です。
このようにして、重要な計算を行う前に、いくつかの非常に高速なテストを実行できます。
public class DataPoint
{
double X, Y;
...
}
public bool IsInBoundingBox(Point p1, Point p2, Point p3, Point p4)
{
// assume p1, p2, p3, p4 to be sorted
return (X>p1.X && X<p3.X && Y>p4.Y && Y<p2.Y);
}
では、実際に作業を行う順番は次のようになるはずです...
// sort points of QueryRectangle: p1 is left-most, p2 is top-most, p3 is right-
// most, and p4 to be bottom-most; if there is a tie for left-most, p1 should
// be the bottom-left corner, p2 the top-left corner, p3 the top-right corner,
// and p4 the bottom-right corner
// See if the QueryRectangle in question is aligned with the grid; if it is,
// then the set of DataPoints that lie within the BoundingBox are within the
// QueryRectangle and no further calculation is needed
if (p1.X == p2.X || p1.X == p3.X || p1.X == p4.X)
{
// is orthogonal (aligned with axes)
foreach(DataPoint dp in listDataPoints)
if(dp.IsInBoundingBox())
{
// dp is in QueryRectangle; perform work
}
}
else
{
foreach(DataPoint dp in listDataPoints)
if(dp.IsInBoundingBox())
{
// perform further testing to see if dp is in QueryRectangle
}
}
または、viraptor が提案するように回転/平行移動ソリューションを使用する場合は...
// sort points of QueryRectangle: p1 is left-most, p2 is top-most, p3 is right-
// most, and p4 to be bottom-most; if there is a tie for left-most, p1 should
// be the bottom-left corner, p2 the top-left corner, p3 the top-right corner,
// and p4 the bottom-right corner
public class DataPointList : List<DataPoint>
{
public List<DataPoint> GetPointsInRectangle(Point p1, Point p2, Point p3, Point p4)
{
List<DataPoint> tempListDataPoints = new List<DataPoint>();
foreach(DataPoint dp in this)
if(dp.IsInBoundingBox()) tempListDataPoints.Add(dp);
if (!(p1.X == p2.X || p1.X == p3.X || p1.X == p4.X))
{
// needs transformation
tempListDataPoints.TranslateAll(-1 * p1.X, -1 * p1.Y);
tempListDataPoints.RotateAll(/* someAngle derived from the arctan of p1 and p2 */);
// Note: you should be rotating counter-clockwise by some angle >0 but <90
// the new p1 will be 0,0, but p2, p3, and p4 all need to undergo the same transformations
// transP1 = new Point(0,0);
// transP2 = new Point(p2.Translate(-1 * p1.X, -1 * p1.Y).Rotate(/* someAngle derived from the arctan of p1 and p2 */));
// transP3 = ...; transP4 = ...;
foreach(DataPoint dp in tempListDataPoints)
if (!(dp.X>transP1.X && dp.X<transP3.X && dp.Y>transP1.Y && dp.Y<transP3.Y)) tempListDataPoints.Remove(dp);
}
else
{
// QueryRectangle is aligned with axes, all points in bounding box
// lie within the QueryRectangle, no need for transformation or any
// further calculation
// no code needs to go here, but you may want to keep it around for notes
}
return tempListDataPoints;
}
}
または、配列を使用して上記のコードを実行することもできます。それを理解するのはあなたに任せます...
免責事項: 昨夜は 2 時間睡眠をとったので、校正はしません。いくつかのマイナーな修正を行う必要がある場合があります。または主要なもの。知るか。:)
ポイント配列を任意の軸 (x とする) に沿って事前に並べ替えることから始めます。次に、長方形のバウンディングボックスのx投影でx投影を持つポイントをバイナリ検索します。それに伴い、チェックするポイントの数が大幅に減少します。
次に、それらが四角形の境界ボックス内にあるかどうかを確認するだけで、ポイントをさらにフィルタリングできます。しかし、はい、それは線形です。
次に、長方形の変換行列を取得できます (既にあると仮定します)。Rectangle は特異な 2-cube のアフィン変換であるため、実際の逆行列を計算しなくても逆変換を求めることができます。
の直接変換行列の場合
A D a
B E b
C F c
解決策は次のとおりです。
d = 1/(AE − BD)
A' = Ed
B' = −Bd
C' = (BF − EC)d
D' = −Dd
E' = Ad
F' = (DC − AF)d
a' = b' = 0
c' = 1
次に、すべてのポイントに逆変換を適用することにより、それを単一の立方体に変換します。これは(0, 1)x(0, 1)、元が長方形の場合は であり、そうでない場合はそうではありません。
UPD:または、すべての変換の代わりに、次のことができます。
長方形P1..P4の点を とし、チェックする点を とするA。
としてi = 1..4計算するためPAiPi - A
の外積は(Pi.x, Pi.y, 0)x(Pj.x, Pj.y, 0)、A と対応する長方形の辺によって作られる三角形を測定します。そして、原点はすべてxy平面上にあるため、結果は のよう(0, 0, Sij)になります。ここで、Sij は三角形の符号付き 2 乗です。合計を計算するだけです：
|(P1.x, P1.y, 0)x(P2.x, P2.y, 0)[3]|+
|(P2.x, P2.y, 0)x(P3.x, P3.y, 0)[3]|+
|(P3.x, P3.y, 0)x(P4.x, P4.y, 0)[3]|+
|(P4.x, P4.y, 0)x(P1.x, P1.y, 0)[3]|
そしてそれを長方形の正方形と比較してください。ほぼ等しい場合、点は長方形の中にあります。多少の計算誤差があるため、正確な等式は問題外です。
長方形に BoundBox を使用できます。ポイントが境界ボックスの内側にある場合は、長方形と衝突するかどうかを確認するか、方向付きの境界ボックスを使用できます。
これは最も簡単な方法であり、複雑なデータ構造を使用する必要はありません