标签: triangular

如果我有一个矩阵的上三角形部分,在对角线上方偏移,存储为线性数组,那么如何(i,j)从数组的线性索引中提取矩阵元素的索引？

例如,线性阵列[a0, a1, a2, a3, a4, a5, a6, a7, a8, a9是矩阵的存储

0  a0  a1  a2  a3
0   0  a4  a5  a6
0   0   0  a7  a8
0   0   0   0  a9
0   0   0   0   0

并且我们想要知道数组中的(i,j)索引,该索引对应于线性矩阵中的偏移,而没有递归.

例如,合适的结果k2ij(int k, int n) -> (int, int)将满足

k2ij(k=0, n=5) = (0, 1)
k2ij(k=1, n=5) = (0, 2)
k2ij(k=2, n=5) = (0, 3)
k2ij(k=3, n=5) = (0, 4)
k2ij(k=4, n=5) = (1, 2)
k2ij(k=5, n=5) = (1, 3) …

介绍

作为一个更大的程序(与渲染体积图形相关)的一部分,我有一个小而棘手的子问题,其中任意(但有限)三角形2D网格需要以特定方式进行标记.我刚刚写了一个解决方案(见下文),它对我当时的测试网格来说已经足够好了,尽管我意识到这种方法对于人们可以想到的每个可能的网格都可能不会很好.现在我终于遇到了一个网格,目前的解决方案根本不能很好地执行 - 看起来我应该想出一种完全不同的方法.不幸的是,我似乎无法重置我的思路,这就是为什么我以为我会问这里.

问题

请看下面的图片.(颜色不是问题的一部分;我只是添加它们来改进(？)可视化.而且变化的边缘宽度是一个完全不相关的工件.)

对于每个三角形(例如,橙色ABC和绿色ABD),三个边缘中的每一个都需要被给予两个标签中的一个,例如"0"或"1".只有两个要求:

1. 并非三角形的所有边都可以具有相同的标签.换句话说,对于每个三角形,必须有两个"0"和一个"1",或两个"1"和一个"0".
2. 如果边缘由两个三角形共享,则它们必须具有相同的标签.换句话说,如果图像中的边缘AB对于三角形ABC标记为"0",则对于ABD也必须标记为"0".

网格是真正的2D网格,它是有限的:即,它不包裹,并且它具有明确定义的外边界.显然,在边界上很容易满足要求 - 但内部变得更加困难.

直观地说,看起来至少应该存在一个解决方案,即使我无法证明它.(通常有几个 - 其中任何一个都足够了.)

当前解决方案

我目前的解决方案是一个非常强力的解决方案(此处仅为完整性而提供 - 可以跳过此部分):

• 保持四组三角形 - 每个可能的计数(0..3)一个剩余的标记.在开始时,每个三角形都在集合中,其中三个边缘仍然被标记.
• 只要存在具有非标记边的三角形:
  找到仍然存在三角形的最小非零数量的未分配边.换句话说:在任何给定时间,我们都会尽量减少标签已部分完成的三角形数量.剩余的边数将是1到3之间的任何值.然后,只需选择一个这样的三角形,剩下要分配的特定边数.对于此三角形,请执行以下操作:
  • 查看是否已经通过标记其他三角形来标记任何剩余边缘.如果是,请按上述要求#2暗示的标签进行分配.
  • 如果这导致死胡同(即,当前三角形不能满足要求#1),那么从一开始就重新开始整个过程.
  • 分配任何剩余边缘如下:
    • 如果到目前为止没有标记边,则随机分配第一个边.
    • 当已经分配了一个边缘时,分配第二个边缘以使其具有相反的标签.
    • 分配两条边时:如果它们具有相同的标签,则指定第三条标签具有相反的标签(显然); 如果两者有不同的标签,则随机分配第三个标签.
  • 更新未分配边数的不同计数的三角形集.
• 如果我们到达这里,那么我们有一个解决方案 - 万岁!

通常这种方法发现只是一对夫妇的迭代内的解决方案,但最近我遇到了该算法趋于结束后,才一两个网上千重试......这显然表明,有可能的网格,它永远不会结束.

现在,我希望有一个确定性的算法,保证总能找到解决方案.计算复杂性不是一个大问题,因为网格不是很大,并且标签基本上只需要在加载新网格时完成,这不会一直发生 - 所以一个算法(例如)指数复杂性应该没问题,只要它有效.(但当然:效率越高越好.)

感谢您阅读此内容.现在,任何帮助将不胜感激!

编辑:基于建议的解决方案的结果

不幸的是,我无法让Dialecticus建议的方法起作用.也许我没弄错......无论如何,考虑以下网格,起点由绿点表示: 让我们放大一点...... 现在,让我们开始算法.在第一步之后,标签看起来像这样(红色="星号路径",蓝色="环形路径"): 到现在为止还挺好.第二步之后: 第三个: ......第四名: 但是现在我们遇到了问题!让我们再做一轮 - 但请注意以洋红色绘制的三角形: 根据我目前的实现,洋红三角的所有边缘都在环形路径上,所以它们应该是蓝色的 - 这实际上是一个反例.现在也许我以某种方式弄错了......但无论如何,最接近起始节点的两条边显然不能是红色; 如果第三个标记为红色,那么似乎解决方案不再符合这个想法.

顺便说一下,这是使用的数据.每行代表一条边,列的解释如下:

1. 第一个节点的索引
2. 第二个节点的索引
3. 第一个节点的x坐标
4. 第一个节点的y坐标
5. 第二个节点的x …

我正在尝试实现一些基本的线性代数运算,其中一个操作是三角形(上部和/或下部)矩阵的反演.有一个简单而稳定的算法吗？

谢谢.

假设我有一个像这样的矢量:

A = [101:105]

这是真的:

[ 101, 102, 103, 104, 105 ]

我只想使用矢量/矩阵函数和运算符来生成矩阵:

101 102 103 104 105
102 103 104 105 0
103 104 105 0   0
104 105 0   0   0
105 0   0   0   0

或以下矩阵:

101 102 103 104 105
0   101 102 103 104
0   0   101 102 103
0   0   0   101 102
0   0   0   0   101

任何人的想法？

(我在MATLAB中非常新手,但我一直背负着这些东西...)

我需要通过不将所有零存储在内存中来有效地存储下三角矩阵,所以我已经考虑过这种方式:首先我为每一行分配内存,然后为每一行分配i + 1个字节,所以我永远不会不得不担心零,但在第一次分配时出现问题.我究竟做错了什么？这是我的代码,编译器在读取矩阵的维度后,在第8行退出程序.

#include <stdio.h>
#include <stdlib.h>

int main ()
{
  int i, j, **mat1, dim;

  scanf("%d",&dim);
  *mat1 = (int**)calloc(dim, sizeof(int*));

  for(i = 0; i<dim; i++)
    mat1[i] = (int*)calloc(i+1, sizeof(int));

  for(i = 0; i < dim; i++)
    for(j = 0; j < i+1; j++)
       scanf("%d", &mat1[i][j]);

  for(i=0; i<dim; i++)
    for(j=0; j<(i+1); j++)
       printf("%d%c", mat1[i][j], j != (dim-1) ? ' ' : '\n');

  return 0;
}

编辑

好吧,在你按照你帮助我的方式修改代码之后,我必须阅读一个上三角和下三角矩阵并显示他们的产品.这个问题是我没有将零存储在内存中,所以如果我使用传统的3-for算法,它会显示一些垃圾值.如果我用0初始化每个矩阵的其余部分,动态分配内存是没用的,因为我也会存储零,所以我没有做任何改进存储的效率.我想我必须在某处修改代码,或者可能是间隔,但无论如何我修改程序仍然输出(对于3x3矩阵)右上角的2个垃圾值.我怎么能这样做？

#include <stdio.h>
#include <stdlib.h>
int main ()
{
int i,j,k,**mat1,**mat2,**prod,dim;


printf("Give dimension: \n"); …

如果我想解决一个完整的上三角系统,我可以打电话linsolve(A,b,'UT').但是稀疏矩阵目前不支持此功能.我怎么能克服这个？

我主要用于对称和三角矩阵的犰狳.我希望在内存存储方面保持高效.然而,似乎除了创建一个新的垫子并填充零(用于三角形)或用重复(用于对称)矩阵的下/上部分之外没有其他方法.

使用Armadillo是否有更有效的方式使用三角形/对称矩阵？

谢谢,安托万

我想生成x和y具有均匀分布，并通过限制[xmin,xmax]和[ymin,ymax]

点 (x,y) 应该在三角形内。

我该如何解决这样的问题？

我需要生成下三角矩阵索引(行和列对).当对称矩阵变大(超过50K行)时,当前实现是低效的(内存方式).有没有更好的办法？

rows <- 2e+01
id <- which(lower.tri(matrix(, rows, rows)) == TRUE, arr.ind=T)
head(id)

#      row col
# [1,]   2   1
# [2,]   3   1
# [3,]   4   1
# [4,]   5   1
# [5,]   6   1
# [6,]   7   1

考虑一个表示节点编号的正则矩阵，如图所示：

我想列出图中表示的所有三角形。这将导致以下二维列表：[[0,1,4],[1,5,4],[1,2,5],[2,6,5],...,[11,15,14]]

假设矩阵的维度是 ( NrX Nc) （在这种情况下为 (4X4) ），我可以使用以下代码实现此结果：

def MakeFaces(Nr,Nc):
    Nfaces=(Nr-1)*(Nc-1)*2
    Faces=np.zeros((Nfaces,3),dtype=np.int32)
    for r in range(Nr-1):
        for c in range(Nc-1):
            fi=(r*(Nc-1)+c)*2
            l1=r*Nc+c
            l2=l1+1
            l3=l1+Nc
            l4=l3+1
            Faces[fi]=[l1,l2,l3]
            Faces[fi+1]=[l2,l4,l3]
    return Faces

但是，双循环操作使这种方法非常缓慢。有没有办法以聪明的方式使用 numpy 来更快地做到这一点？