0

まず、この質問は特定の言語に関連していません-私はHaxeを使用して複数のプラットフォームをターゲットにしています-したがって、擬似コードで十分です。

これが私の問題です：私はこの形式でスパース行列の記述を持っています：

edges = 
[
1,1,2,1,3,1,4,1,
2,2,3,2,
3,3,4,3,5,3,
4,4,5,4,6,4,
5,5,6,5,7,5,25,5,27,5,28,5,29,5,30,5
];

これは、エッジの関連付けについて説明しています。

  • ポイント1はポイント1、2、3、4にリンクされています
  • ポイント2はポイント2と3にリンクされています
  • ポイント3はポイント3、4、5にリンクされています
  • ポイント4はポイント4、5、6にリンクされています
  • ポイント5は、ポイント5、6、7、25、27、28、29、および30にリンクされています

これを3Dでレンダリングする必要があります。そのためには、データを「ギャップ」なしでインデックスバッファに「圧縮」する必要があります。上記の例で言うと、私は取得する必要があります：

newEdges = 
[ 
1,2, 1, 3, 1, 4,
2,3,
3,4, 3,5,
4,5, 4,6,
5,6, 5,7, 5,8, 5,9, 5,10, 5,11, 5,12
]

したがって、それ自体をリンクしているエッジ（エッジ1-1、2-2、3-3など）を削除する必要があります（簡単）。

ポイントの順序は重要ではないため（エッジ1-2 =エッジ2-1）、重複するエッジも削除します（簡単です）。

ここで注意が必要なのは、「ギャップ」を取り除くことです。7が最高の連続値で、25が直後の値であるため、25は8になり、27は9になり、28は10になります。

今のところ、すべての値をXY座標としてプロットするBitmapDataを使用しています。次に、このビットマップの空でない垂直ストライプ（1ピクセル幅の長方形）を隣り合わせに再帰的にコピーして、一時的なビットマップに入れます。次に、横縞についても同じことを行い、最後にビットマップをスキャンして、ピクセルのX値とY値をエッジのIDとして保存します。

そしてそれは動作します！（少なくともそうです:)）しかし、オーバーヘッドはひどく、入力マトリックスによっては、ビットマップを生成できない可能性があります（たとえば、フラッシュは最大4092ピクセルに制限されていますが、JSは生成しませんcopyPixelsを非常によくサポートします）。

したがって、問題は、ビットマップや言語固有のメソッドを使用せずに、この「ギャップの削除」をどのように行うかということです。

これが十分に明白であることを願って、あなたの注意に感謝します。

ニコラス

4

2 に答える 2

1

E[m+1][m+1]に対応する2次元隣接行列とします。ここedgesで、点インデックスの範囲は[0..m]です。

で訪問したポイントのソートf[n]された配列とします。配列を作成することにより、[0..m]の範囲の非隣接ポイントインデックスと[0..n-1]の隣接ポイントインデックスの間のマッピングを作成しています。nedgesf[n]

次のように、新しい隣接行列Gを作成します。

for i = 0..(n-1)
    for j = 0..(n-1)    // or, j = (i+1)..(n-1) for upper triangular portion
        G[i][j] = E[f[i]][f[j]]
    end
end

これには、O（m ^ 2）時間ではなくO（n ^ 2）時間しかかかりません。

編集：ifステートメントを削除しました。EとGの両方がすべて0に初期化されている場合、それは不要です。

于 2012-10-22T16:07:03.063 に答える
1

行列はスパースであるため、ソートされたリストデータ構造を使用して、エッジリストからスパース構造を構築することをお勧めします。行ごとに、エッジを追加する動的に並べ替えられたリスト（昇順）を作成する必要があります。たとえば、エッジの場合、並べ替えられたリストに(1,2)列を挿入します。行あたりのエントリ数が少ない場合（数百）は、ソートされたリストで線形検索を使用してから、大きい要素をリストの最後に移動するのが最適です。行あたりのエントリ数が多い場合は、二分法を使用して正しい位置を見つけることができます。私は、有限要素法で発生するスパース行列に対してこのアプローチを日常的に使用しています。私の経験では、これが最速のアプローチであり、2sorted_lists{1}簡単に並列化できます！（スレッド間で行範囲を分割）

ソートされたリストを実装するMATLABコードの例を次に示します。

function list = sorted_list_insert(list, col)

% special case for empty list
if isempty(list)
    list = col;
    return;
end

% search for col position in the row
% can be done with bisection,
% but linear search is much faster for small number of entries per row
it = 1;
while it<length(list) && list(it)<col
    it = it+1;
end

% duplicate entry - do not add
if list(it)==col
    return;
end

% insert col in proper position, move other elements in the list
list = [list(1:it) col list(it+1:end)];
end

このソートされたリストに行のすべてのエントリを追加することの複雑さはですO(number of entries per row ^ 2)。

次に行う必要があるのは、エッジリストを調べて列を追加し、行の並べ替えられたリストを修正することです（sorted_lists{row}）。以下でedgesは、は2D配列であると想定されています。ここedges(1,i)で、は列、edges(2,i)は行です。

% find maximum row id
max_row = number of rows in the matrix

% initialize sorted list structures for all rows - max_row empty lists
sorted_lists = cell(max_row, 1);

% create sorted rows
nedges = total number of edges
for it=1:nedges
    row = edges(2,it);
    col = edges(1,it);
    sorted_lists{row} = sorted_list_insert(sorted_lists{row}, col);
end

上記のステップの複雑さはですO(number of rows * number of entries per row ^ 2)。

最後に、ギャップを取り除くことです。ソートされたリストでは、ソートされたリスト内のの位置を見つけることで簡単に実行できcolます。また、オフセットを追加する必要があります。データから、マトリックスの上部三角部分を処理しているように見えます（エッジのノードの順序は重要ではないと言いました）。したがって、オフセットは単純に行番号です（MATLABでは1からの番号付けがあるため、MATLABでは-1）

% the positions of col in every row (plus offset)
% are the new col id with removed gaps
for it=1:nedges
    offset = edges(2,it)-1;
    edges(1,it) = offset + find(sorted_lists{edges(2,it)}==edges(1,it));
end

edges上記のコードで処理した後の外観は次のとおりです。

edges =

Columns 1 through 13

 1     2     3     4     2     3     3     4     5     4     5     6     5
 1     1     1     1     2     2     3     3     3     4     4     4     5

Columns 14 through 20

 6     7     8     9    10    11    12
 5     5     5     5     5     5     5

この手順は、ソートされたエッジとソートされていないエッジに対して正常に機能します。それはそれを仮定するだけですcol >= row。簡単に達成できること。(i,i)対角エッジの削除を簡単に追加することもできます。

于 2012-10-23T08:11:37.410 に答える