点の集合s (x,y 座標の集合) と、点の集合lを結ぶ線分で構成されるパスが与えられたとき、 sから点のサブセットを見つけるために使用できる効率的なアルゴリズムを説明してください。パスlの指定された距離d内。
これの実用的なアプリケーションは、都市間のロードトリップ パスに沿った 10 マイル以内のレストランのリストを見つけることです。
たとえば、次の図では、緑色のポイントが検索結果に含まれます。
ソリューションは C# で優先されますが、SQL ベースのアプローチにはボーナス ポイントが与えられる可能性があります :-)
これも少し前に考えたことがあります。私は、効率的は誤解を招くと思います。各ポイントのすべての線分をテストするだけで十分です。距離を計算するのは非常に安価です。ポイントが多い場合は、レベルセット方式でどのポイントを選ぶか戦略を練ることも考えられます。すなわち
それはおそらく完全ではないかもしれませんが、高速で、遠く離れたポイントをチェックすることを避け、まったく問題ありません。
「左の道路」と「右の道路」を定義します。元のパスの線分ごとに、セグメントの「左」にd単位、「右」に1d単位の線分を作成します。
左の道路と右の道路の端を接続してポリゴンを作成します。
標準のアルゴリズムを適用して、ポリゴンの内側にある関心のあるポイントを決定します。
少なくとも一部の作業を SQL で行いたい場合は、パスの境界ボックスを計算してから、場所が境界ボックス内にあるという条件をクエリに組み込むことができます。返された行だけに対して他のアルゴリズムの 1 つを実行します。
これにより、少なくともパスごとにデータベース全体をダウンロードする必要がなくなります。
質問を正しく理解しているかどうかはよくわかりませんが、ダイクストラのアルゴリズムは当てはまりませんか? ソースノードからの最短パスを見つけ、最大距離に達した後に中断して、sからのどのポイントがすでに見つかっているかを確認できます。ただし、SQLでどれだけうまく機能するかはわかりません。
これに対する唯一の解決策は、次の行に沿ったものです。
for each point
for each line
is distance to line within constraints
制約内にあるポイントが見つかると、内側のループを早期に終了できます。内側と外側のループは転置できることに注意してください。
問題は、ポイントが制約内にあるかどうかを判断することになります。mbeckish は、線の垂線に沿って押し出すことによって長方形を形成する単純な長方形テストを使用することを提案していますが、これは端点に近いがこの長方形の外側にあるポイントでは失敗します。線の方向に沿って四角形を押し出すことも失敗します。これは、端近くのポイントが実際には円テストのポイントを使用する必要があるためです。
|-------------
| * /
| --
| /
| /
| |
| |
|/
| |--------| <- the line segment
* は拡張された長方形の内側にありますが、より厳密なテストとなる丸みを帯びたエンド キャップの外側にあります。
ここで、距離テストは「カラスが飛ぶように」テストではなく、たとえば、道路のみを使用して道路から x マイル以内のポイントを接続するグラフ検索である可能性があります。
--------------------------------------------------- < the road
|
| * <- target
...|..............|................................ < check distance
| |
|--------------| <- roads to target
上の図では、ターゲットは検索エリア内にありますが、利用可能な道路に沿ってターゲットに到達するには、許容距離を超えてしまいます。
どのような方法でテストを実装する場合でも、基本的な loop in a loop アルゴリズムが必要になります。
制約が「カラスが飛ぶように」制約である場合の制約を確認する方法:
幾何学的: まず、点 P から直線までの距離を決定します。次に、点が制約内にある場合、点 P を線分に投影します。線分は次のように定義されます。
L = P1 + (P2-P1).n
ここで、P1 と P2 は終点で、n はパラメトリック変数です。投影された P の n の値が 0 <= n <= 1 の範囲にある場合、ポイントは P1 と P2 の間にあります。最後に、P1 と P2 を中心とする円の円テストでポイントを実行します。
変換: P1 が原点に変換され、P2 が (|P1-P2|, 0) に変換されるように、線分ごとに変換行列を作成します。次に、各変換をすべての点に適用し、長方形 (0, -constraint) - (|P1-P2|, 制約) 内の各点をテストします。この方法は、SIMD または GPU を使用して高度に最適化できます。
グラフィカルに: 丸みを帯びたエンド キャップと拘束距離に比例した幅を持つペンを使用して、線分をビットマップに描画します。次に、テスト ポイントごとに、そのポイントに対応するビットマップ内のピクセルを確認します。これは正確ではありません (ただし、ビットマップが大きいほど正確な結果が得られますが、より多くのメモリが必要になります) が、ビットマップが作成されると非常に高速です。
制約がグラフに沿ったルートによって定義される場合、より複雑になります。始点が各線分の終わりであり、終点が潜在的なターゲットである幅優先検索を調べる必要があります。線分の長さに沿って接合点がある場合、線分を接合点のない線分に分割します。
1.) ジオメトリ データ型 (緯度/経度の座標を使用して定義されている場合は地理) を使用して、ポイントを SQL Server 2008 テーブルに格納します (0,0) と ( 40,20):
DECLARE @Points table (
id int,
position geometry
);
DECLARE @i int = 0, @x int, @y int;
WHILE (@i < 100)
BEGIN
INSERT INTO @Points VALUES
(@i, geometry::Point(RAND() * 40, RAND() * 20, 0))
SET @i = @i + 1;
END
2.) ポイントと同じデータ型と SRID を使用して、ラインをラインストリングとして定義します。
DECLARE @line geometry = 'LINESTRING(0 10, 10 15, 20 8, 40 10)';
3.) ポイント テーブルに対する SELECT クエリの述語で STDistance() メソッドを使用します。たとえば、ラインの 5 単位内にあるすべてのポイントを選択するには、次のようにします。
SELECT * FROM @Points
WHERE @line.STDistance(position) < 5;
さらに、SQL Server の空間メソッドは再配布可能な dll (Microsoft.SqlServer.Types.dll - SQL Server 機能パックの一部http://www.microsoft.com/downloads/en/details.aspx? FamilyID=ceb4346f-657f-4d28-83f5-aae0c5c83d52 )、この同じアプローチを C# または SQL Server で直接使用できます。
難しい宿題ですか？
おそらく、幅優先の経路探索アルゴリズムを調べることから始めるのが良いかもしれません-おそらく、フラッドフィルアプローチのようなものがこれに役立つでしょうか?
編集：宿題のように見えるだけなら、もっと役立つかもしれません...
最初に、線とその中にある可能性のある点を含む長方形を定義することを検討します。これにより、線の近くにない多数の点を取り除くことができるようになります。
ポイントごとに、そのポイントの半径内のポイントのリストを表す正方形を作成できます。これも、検索する要素の数を減らす方法です。
残念ながら、点のリストが円の内側にあるか円の外側にあるかを決定する賢い方法を認識するのに十分なジオメトリを知りません。基本的な三角法を使用してそれらと円の中心との間の距離を計算するだけではありません-私は確かに1つあります。前述の単純な細分化またはその変形を使用することで、検索する必要がある可能性のあるポイントの数を事前に減らすことができることがわかるはずです。
また、検索するすべてのポイントを 1 つのリストに保持し、最初の円でヒットしたポイントを削除すると、その後の形状を測定できます。私はこれの総当たりバージョンを使用して、位置データに基づいて簡単な郵便番号距離チェックを行いました.
この幾何学的なアプローチは、多くの繰り返し検索を行っていない状況ではおそらくより良いでしょう。行に多くのポントがある場合は、ポントをネットワークに編成して、標準的なパスファインディングを使用できるようにすることができます。どちらがより効率的かを確認するためにプロトタイプを作成する価値はありますが、データを表す適切なネットワークを作成する場合は、検索方法がより柔軟になると期待しています。
正確な方法は私を免れますが、ベクトル数学と三角法によってこれを達成できるはずです。
線分ごとに、線分を基準にしてポイントをワールド座標からローカル座標に変換するために必要な値を計算します（したがって、計算を実行する点は、線分がx軸である座標系を基準にします）。
各ポイントについて、次のチェックを実行します。
1-ポイントがいずれかのエンドポイントの距離内にある場合、それを含める必要があることがわかります。これは、各端点とターゲットポイント間の単純な距離^ 2 <=（x2 --x1）^ 2 +（y2 --y1）^2の計算によって実現されます。
2-変換を介してターゲットポイントを実行します。変換後、x> =0かつx<=（線分の長さ）かつ|y|の場合 <=距離の場合、ターゲットポイントを含める必要があります。そうでない場合は、除外する必要があります。
私のベクトル計算は少し錆びているので、申し訳ありませんがより良いコード/例を提供することはできません！しかし、おそらく私の投稿は、他の誰かにそれを行うための適切な方法を書き出すように促すでしょう。
四分木を使用してスペースをセグメントに分割し、パスに近いセグメント内のポイントのみを分割できますか?
一般的な計算ツールを考えると、最適なアルゴリズムは、明らかに興味のないポイントを除外し、すべての線分から残りの各ポイントまでの距離を見つけるいくつかのバリエーションになります。(提案された多角形の解法は間違っています。関心のある領域は、その多角形とl上の各点の周りの半径dの円との結合です。実際には、各点からすべての線分までの距離を単純に見つけるよりも効率的ではありません。)
どのフィルターが最適かは、データの性質によって異なります。たとえば、サンプル ダイアグラムでは、lの境界ボックス (およびd ) でのフィルター処理が非常に役立ちます。
興味深いフィルターは次のようになります: lを定義する点pが与えられ、半径rの円を取得します。ここで、rはpとdによって部分的に定義される 2 つのセグメントの最大長です。この円内のポイントのみが、これら 2 つのセグメントに十分近く、ソリューション セットに含めることができるため、これらの 2 つの線分の距離の計算をスキップできるかどうかをすぐに判断できます。(一部の線分が非常に長い場合、これは効率が低下しますが、長い場合、それらの線分は簡単に小さなチャンクに分割できます。)
この 2 つのクラスがあなたの質問に答えてくれると思います。Heron の Formulaを使用して GetArea() 関数を作成しました。セグメント ポイントが常に最初に IsPointWithinDistanceToLineSegment に渡され、TestPoint が常に 3 番目に渡されるようにします。
編集: X と Y に整数のみを許可する Point を愚かに使用しました。X と Y として double または float を取る別のクラスでこれを修正する必要があります...
public class Geometry
{
public static double GetDistanceBetweenTwoPoints(Point SegmentStart, Point SegmentEnd)
{
return Math.Sqrt(Math.Pow(SegmentEnd.X - SegmentStart.X, 2) + Math.Pow(SegmentEnd.Y - SegmentStart.Y, 2));
}
public static bool IsPointWithinDistanceToLineSegment(Point SegmentStart, Point SegmentEnd, Point TestPoint, double TestDistance)
{
if (GetDistanceBetweenTwoPoints(SegmentStart,SegmentEnd) <= TestDistance || GetDistanceBetweenTwoPoints(SegmentEnd,TestPoint) <= TestDistance)
{
return true;
}
var T = new Triangle(SegmentStart, SegmentEnd, TestPoint);
var BaseLength = GetDistanceBetweenTwoPoints(SegmentStart, SegmentEnd);
var Area = T.GetArea();
var TriangleHeight = 2* Area / BaseLength;
return T.AB >= T.BC && T.AB >= T.AC && TriangleHeight <= TestDistance;
}
}
public class Triangle
{
public Triangle(Point a, Point b, Point c)
{
this.a = a;
this.b = b;
this.c = c;
}
public Point a
{
get;
set;
}
public Point b
{
get;
set;
}
public Point c
{
get;
set;
}
//Lengths of Sides
public double AB
{
get
{
return Geometry.GetDistanceBetweenTwoPoints(a, b);
}
}
public double AC
{
get
{
return Geometry.GetDistanceBetweenTwoPoints(a, c);
}
}
public double BC
{
get
{
return Geometry.GetDistanceBetweenTwoPoints(b, c);
}
}
public double GetArea()
{
var Term1 = Math.Pow((Math.Pow(AB, 2) + Math.Pow(AC, 2) + Math.Pow(BC, 2)), 2);
var Term2 = 2 * (Math.Pow(AB, 4) + Math.Pow(AC, 4) + Math.Pow(BC, 4));
var result = .25 * Math.Sqrt(Term1 - Term2);
return result;
}
}
これについて誰も A* アルゴリズムについて言及していないことに驚いています。完璧にフィットするようです。ここで何が欠けていますか？あなたがそれに慣れていない場合は、グーグルで検索すると、=)が見つかります。（はい、それはゲームの世界から来ています...）