3

ピクセルにラスタライズされたエッジを含む 2D データがあります。軸に沿っていない2D 三角形にあるすべてのエッジ ピクセルを返す効率的なデータ構造を実装したいと考えています。

スパース データの空間クエリ

この画像は問題の視覚化を示しており、白はラスター化されたエッジを示し、赤はクエリの三角形を視覚化しています。結果は、境界上または赤い三角形の内側にあるすべての白いピクセルになります。

  • 画像をさらに見ると、まばらなブールデータがあることに気付きます。つまり、黒のピクセルを 0 で、白のピクセルを 1 で表すと、データ内の 1 の数が 0 の数よりもはるかに少ないことを意味します。したがって、赤い三角形をラスタライズし、その内部の各ポイントが白か黒かを確認することは、最も効率的な方法ではありません。

  • データのまばらさに加えて。白いピクセルはエッジに由来するため、互いに結合する性質があります。ただし、他のラインとのジャンクションでは、2 つ以上の隣接ラインがあります。ジャンクションにあるピクセルは 1 回だけ返されます。

  • データはリアルタイムで処理する必要がありますが、GPU の支援はありません。さまざまな三角形のコンテンツに対して複数のクエリがあり、各クエリの後、データ構造からポイントが削除される場合があります。ただし、データ構造を最初に埋めた後は、新しいポイントは挿入されません。

  • ラスター化されたエッジが到着した時点で、クエリ三角形は既知です。

  • データ エッジよりも多くのクエリ トライアングルがあります。

多くの空間データ構造が利用可能です。しかし、私の問題にはどれが最適なのか疑問に思っています。この問題を解決するために高度に最適化されたデータ構造を実装したいと考えています。これはプロジェクトのコア要素になるからです。したがって、データ構造の混在や省略も大歓迎です!

  • R ツリーは、四角形ベースのクエリをサポートしているため、これまでこの問題に対して私が見つけた最良のデータ構造のようです。クエリ三角形の AABB 内のすべての白いピクセルをチェックし、返された各ピクセルがクエリ四角形内にあるかどうかをチェックします。

    ただし、エッジベースのデータは簡単に四角形にグループ化できないため、R ツリーがどの程度うまく機能するかはわかりません。

    構造が満たされるとすぐに作成されるクエリ三角形に関する情報を使用して、R ツリーの構造を事前に構築することが理にかなっているのかどうかもわかりません (前述のように、クエリ三角形は既に知られています)。データが到着したとき）。

  • 問題を逆にすることも有効な解決策のようです.2次元間隔ツリーを使用して、白いピクセルごとにそれを含むすべての三角形のリストを取得します. その後、それらすべての結果セット内に既に格納されており、クエリが到着するとすぐに返されます。ただし、これがどのように実行されるかはわかりません。三角形の数はエッジの数よりも多く、それでも白いピクセルの数よりは少ないです (エッジはほとんどが 20 ～ 50 ピクセルに分割されるため)。

  • 白いピクセルが隣接ピクセルとして最も頻繁に白いピクセルを持っていることを利用するデータ構造は、最も効率的であるように思われます。しかし、今までそのようなことについて何も見つけることができませんでした。

4

2 に答える 2

1

クエリ三角形を n*3 行に分解します。テスト中のすべての点について、それがすべての線のどちら側にあるかを推定できます。残りはブール論理です。

編集:ポイントはラスタライズされているため、スキャンラインが特定のクエリ三角形に出入りするスキャンライン上のポイントを事前計算できます (= 上の 3n 行の 1 つを横切り && は、参加する他の 2 行の「内側」にありますその特定の三角形)

更新: 別のトピック (ポイントが 3D の三角形内にあるかどうかを確認するにはどうすればよいですか? )によってトリガーされます。の上"。私は怠け者なので、L字型のフォームを使用します。私見の他の非凸形状も同様に処理できます。線は X 軸と Y 軸に平行ですが、これも怠惰です。

/*

Y
| +-+
| | |
| | +-+
| |   |
| +---+
|
0------ X
the line pieces:
Horizontal:
(x0,y0) - (x2,y0)
(x1,y1) - (x2,y1)
(x0,y2) - (x1,y2)
Vertical:
(x0,y0) - (x0,y2)
(x1,y1) - (x1,y2)
(x2,y0) - (x2,y1)

The lines:
(x==x0)
(x==x1)
(x==x2)
(y==y0)
(y==y1)
(x==y2)

Combine them:
**/

#define x0 2
#define x1 4
#define x2 6

#define y0 2
#define y1 4
#define y2 6

#include <stdio.h>

int inside(int x, int y)
{   

switch(  (x<x0 ?0:1)
    +(x<x1 ?0:2)
    +(x<x2 ?0:4)
    +(y<y0 ?0:8)
    +(y<y1 ?0:16)
    +(y<y2 ?0:32) ) {

case 1+8:
case 1+2+8:
case 1+8+16:
    return 1;
default: return 0;
    }
}

int main(void)
{
int xx,yy,res;
while (1) {
     res = scanf("%d %d", &xx, &yy);
     if (res < 2) continue;
     res = inside(xx, yy);
     printf("(%d,%d) := %d\n", xx, yy,res);
    }
return 0;
}
于 2011-11-30T15:44:46.397 に答える
0

いくつかの計算幾何学的アルゴリズムがあり、それらを併用すると良い結果が得られると思います。

  1. すべての三角形のエッジを含む平面のサブディビジョンを計算します。(これは、三角形のエッジのすべての交点を計算するよりも少し複雑です。) 各面について、その面を含む三角形のリストを作成します。これは確かに最悪の場合の 3 次ですが、それは三角形が大きく重なっている場合のみです (それを 2 次に圧縮する方法があると思わずにはいられません)。

  2. サブディビジョン内の各ピクセルを見つけます (つまり、どの面に属しているかを調べます)。各エッジの最初の 1 つは O(log n) のコストがかかりますが、その後の局所性があれば、計算を平均で O(1) のようなものに短縮する方法があるかもしれません。(たとえば、台形メソッドを使用し、最後の点を含む台形のリストを格納する場合、現在の点を含む台形が見つかるまでリストを上に移動し、下に戻ることができます。ヒントを C++ に与えることを比較してください。挿入ポイントの近くに反復子を渡すことによる STL セットの挿入。)

于 2011-11-30T23:56:28.193 に答える