5

ポイントが軸に沿った長方形の内側にあるかどうかを検出するための最も最適化された方法を探しています。

最も簡単なソリューションには、パフォーマンスに悪い4つのブランチ（if）が必要です。

4

5 に答える 5

8

セグメントが与えられると[x0, x1]、ポイントxはセグメントの内側にあります(x0 - x) * (x1 - x) <= 0。

2次元の場合、2回実行する必要があるため、2つの条件が必要です。

于 2012-12-03T14:23:30.037 に答える
5

XMin-X、X-XMax、YMin-Y、Y-YMaxの値をBITWISE-ANDすることを検討し、結果の符号ビットを使用します。

intsとfloatの両方で動作します。

于 2012-12-03T14:48:14.647 に答える
2

何があっても4つのテストが必要になると思いますが、ポイントが長方形の内側または外側にある可能性が高いかどうかがわかっている場合は、これらの4つのテストが最悪の場合にのみ実行されることを確認できます。

ポイントが内側にある可能性が高い場合は、次のことができます

if ((x>Xmax) || (x<Xmin) || (y>Ymax) || (y<Ymin)) {
 // point not in rectangle
}

それ以外の場合は、反対の操作を行います。

if ((x<=Xmax) && (x>=Xmin) && (y<=Ymax) && (y>=Ymin)) {
 // point in rectangle
}

本当にもっと良いものがあるかどうか興味があります...（長方形のエッジが2の累乗またはそのようなファンキーなものに整列しているように、どこにあるかについて何らかの仮定を立てることができない限り）

于 2012-12-03T14:10:40.357 に答える
1

多くのアーキテクチャは、ブランチレス絶対値操作をサポートしています。そうでない場合は、乗算によってシミュレートするか、符号付きの値を左にシフトして、特定の「実装に依存する」動作を信頼することができます。

また、IntelおよびARMアーキテクチャでは、操作をブランチレスにすることができる可能性があります。

((x0<x) && (x<x1))&((y0<y) && (y<y1))

その理由は、範囲チェックがシーケンスに最適化されることが多いためです。

mov ebx, 1       // not needed on arm
sub eax, imm0    
sub eax, imm1    // this will cause a carry only when both conditions are met
cmovc eax, ebx   // movcs reg, #1    on ARM

ビット単位および（x）式と（y）式の間もブランチレスです。

編集元のアイデアは次のとおりです。

与えられたテスト範囲：a <= x <= b、最初に中間点を定義します。次に、両側を|（x-mid）|でテストできます。<A; 係数Bを掛けて、Aの累乗を2にします...（x-mid）* B <2 ^ nおよび2乗
（（x-mid）* B）^ 2 <2 ^ 2n

この値には、最下位2nビットに設定されたビットのみがあります（条件が満たされた場合）。範囲yとORについても同じようにします。この場合、係数Cは、（y-midy）^2が同じ2^2nにスケーリングするように選択する必要があります。

 return (((x-mid)*B)*(((x-mid)*B) | ((y-mid)*C)*((y-mid)*C))) >> (n*2);

戻り値は、AABBの内側のx、yの場合は0、外側のx、yの場合はゼロ以外です。（ここでの演算はまたはです。（a && b）＆（c && d）の補集合に関心があるため、（！（a && b））|（！（c＆dd））;

于 2012-12-03T14:26:59.227 に答える
0

可能な値の範囲と必要な解像度について、またどの基準を最適化するかについて、あなたが知っていることを教えてください。

解決策は、座標のペアを検索するブール値の2D配列（実行できる場合）を事前に計算することです。1つの乗算（またはシフト）、1つの加算（アドレス計算用）、および1つのメモリ読み取りのコストがかかります。

またはブール値の2つの1D配列。コスト2の追加、2つのメモリ読み取りと1つのAND、はるかに小さいテーブル。

于 2012-12-03T14:43:12.127 に答える