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，依此类推。

现在我使用的是 BitmapData，在其中我将所有值绘制为 XY 坐标。然后我递归地将这个位图的非空垂直条纹（1像素宽的矩形）复制到一个临时位图中。然后我对水平条纹做同样的事情，最后扫描我的位图并将像素的 X 和 Y 值存储为边缘的 ID。

并且它有效！（至少它似乎是:)）但是开销很糟糕，并且取决于输入矩阵，我可能无法生成位图（例如，flash 限制为最大 4092 像素，JS 不很好地支持copyPixels）。

所以问题是你将如何在没有位图和语言特定方法的情况下进行这种“间隙消除”？

希望这足够明确，感谢您的关注。

尼古拉斯

4

2 回答 2

1

由于您的矩阵是稀疏的，我建议您使用排序列表数据结构从边缘列表构建稀疏结构。对于每一行，您需要创建一个动态排序列表（升序），向其中添加边。例如，对于边，(1,2)您将2在排序列表中插入列sorted_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，因为它具有基于 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 回答
1

让E[m+1][m+1]是对应于 的二维邻接矩阵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(n^2) 而不是 O(m^2) 时间。

编辑：删除if声明。如果 E 和 G 都初始化为全 0，则没有必要。

于 2012-10-22T16:07:03.063 回答