计算网格的顶点距离

huangapple go评论70阅读模式
英文:

Calculate vertex distances of a mesh

问题

我正在使用Numpy数组来表示一个三角网格。

我有两个矩阵:coordinates 是一个 3 x n 矩阵,connectivity 是一个 n x n 矩阵,其中使用 0 和 1 来存储顶点的连接。

现在我想计算一个名为 distances 的 n x n 矩阵,用于存储顶点之间的距离。只有在 connectivity[i,j] == 1 的位置才需要计算,其他位置不需要。

在Python中,最优雅的计算方法是什么?

例如,我有一个包含4个顶点的网格,如下所示:

然后

import numpy as np

coordinates = np.array(
    [
        [-1, -1, 0],    # A
        [1, -1, 0],     # B
        [1, 1, 0],      # C
        [-1, 1, 0]      # D
    ], 
    dtype=np.float32
)

connectivity = np.array(
    [
        [0, 1, 1, 1],    # A-B, A-C, A-D
        [1, 0, 1, 0],    # B-A, B-C
        [1, 1, 0, 1],    # C-A, C-B, C-D
        [1, 0, 1, 0],    # D-A, D-C
    ],
    dtype=np.int32
)

# 对于这个示例,预期的 `distances` 如下所示
distances = np.array(
    [
        [0, 2, 2.828, 2],   # A-B, A-C, A-D
        [2, 0, 2, 0],       # B-A, B-C
        [2.828, 2, 0, 2],   # C-A, C-B, C-D
        [2, 0, 2, 0],       # D-A, D-C
    ],
    dtype=np.float32
)
英文:

I am using Numpy arrays to express a triangular mesh.

I have two matrices: coordinates is a 3 x n matrix, and connectivity is an n x n matrix that uses 0s and 1s to store vertex connectivity.

Now I want to calculate a n x n matrix named distances that stores vertex distances. Only the positions where connectivity[i,j] == 1 are calculated. Anywhere else are not.

What is the most elegant way to calculate this in Python?

For example, I have a mesh of 4 vertices like this:

计算网格的顶点距离

Then

import numpy as np

coordinates = np.array(
    [
        [-1, -1, 0],    # A
        [1, -1, 0],     # B
        [1, 1, 0],      # C
        [-1, 1, 0]      # D
    ], 
    dtype=np.float32
)

connectivity = np.array(
    [
        [0, 1, 1, 1],    # A-B, A-C, A-D
        [1, 0, 1, 0],    # B-A, B-C
        [1, 1, 0, 1],    # C-A, C-B, C-D
        [1, 0, 1, 0],    # D-A, D-C
    ],
    dtype=np.int32
)

# For this example, expected `distances` is like this
distances = np.array(
    [
        [0, 2, 2.828, 2],   # A-B, A-C, A-D
        [2, 0, 2, 0],       # B-A, B-C
        [2.828, 2, 0, 2],   # C-A, C-B, C-D
        [2, 0, 2, 0],       # D-A, D-C
    ],
    dtype=np.float32
)

答案1

得分: 1

以下是使用np.tile来高效生成所有距离对的解决方案,然后再通过连接矩阵进行掩码处理。

思路是生成两个包含平铺顶点坐标的矩阵,模式如下:

ABCD 
ABCD
ABCD
ABCD

AAAA
BBBB
CCCC
DDDD

这两个矩阵的差异然后给出了所有的组合。如果你只想要实际连接的条目,那么你可以简单地将这些矩阵与连接矩阵相乘。

mat = np.tile(coordinates, (4, 1, 1)) * connectivity[..., None]
mat_t = np.transpose(mat, axes=(1, 0, 2))

distances = np.sqrt(((mat - mat_t) ** 2).sum(axis=2))

这会给你预期的结果:

array([[0.      , 2.      , 2.828427, 2.      ],
       [2.      , 0.      , 2.      , 0.      ],
       [2.828427, 2.      , 0.      , 2.      ],
       [2.      , 0.      , 2.      , 0.      ]], dtype=float32)

另外,假设你是从三角形索引数组生成连接矩阵,你也可以使用它来生成距离,然后以类似的方式生成矩阵,就像生成连接矩阵一样。

英文:

Here is a solution using np.tile to efficiently generate all pairs of distances, which are then masked out by the connectivity matrix.

The idea is to generate two matrices containing the tiled vertex coordinates, in the following pattern:

ABCD 
ABCD
ABCD
ABCD

and

AAAA
BBBB
CCCC
DDDD

The difference of those two matrices then gives you all combinations. If you only want the entries that actually are connected, then you can simply multiply these matrices by the connectivity matrix.

mat = np.tile(coordinates, (4,1,1)) * connectivity[..., None]
mat_t = np.transpose(mat, axes=(1,0,2))

distances = np.sqrt(((mat - mat_t)**2).sum(axis=2))

Which gives you the expected result:

array([[0.      , 2.      , 2.828427, 2.      ],
       [2.      , 0.      , 2.      , 0.      ],
       [2.828427, 2.      , 0.      , 2.      ],
       [2.      , 0.      , 2.      , 0.      ]], dtype=float32)

Alternatively, assuming you generated the connectivity matrix from a triangle index array, you could use it to generate the distances, and then generate the matrix in a similar fashion as you generate the connectivity matrix.

答案2

得分: 1

使用scipy.spatial.distance.cdist计算坐标之间的距离,并在最后使用connectivity数组进行确保:

from scipy.spatial.distance import cdist

dist = cdist(coordinates, coordinates, 'euclidean') * connectivity
print(dist)

[[0.         2.         2.82842712 2.        ]
 [2.         0.         2.         0.        ]
 [2.82842712 2.         0.         2.        ]
 [2.         0.         2.         0.        ]]
英文:

Compute distance between coordinates with scipy.spatial.distance.cdist
and ensure it with connectivity array at the end:

from scipy.spatial.distance import cdist

dist = cdist(coordinates, coordinates, 'euclidean') * connectivity
print(dist) 

[[0.         2.         2.82842712 2.        ]
 [2.         0.         2.         0.        ]
 [2.82842712 2.         0.         2.        ]
 [2.         0.         2.         0.        ]]

huangapple
  • 本文由 发表于 2023年3月1日 15:02:11
  • 转载请务必保留本文链接:https://go.coder-hub.com/75600460.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定