如何基于Delaunay三角剖分结果构建3D点集的邻接矩阵？

Got it, let's tackle this problem step by step. You've got your 3D points matrix, ran Delaunay triangulation with geometry::delaunayn(), and now need to build an adjacency matrix where each entry indicates if two points are connected (share an edge in any tetrahedron). Here's how to do it:

Background #

First, remember that delaunayn() returns a matrix where each row represents a tetrahedron (since we're working in 3D), with values being the indices of your original points (matching the row order of your input matrix mat). Each tetrahedron has 4 vertices, and every pair of vertices in a tetrahedron shares an edge—those are the adjacent point pairs we need to capture.

Step-by-Step Solution #

Let's use your example code as a starting point, then expand it to generate the adjacency matrix:

1. Your Original Setup (for reference)

set.seed(123) # For reproducibility
values <- rnorm(12, mean = 10, 5) 
mat <- matrix(values, ncol = 3) 
dimnames(mat) <- list(c("asd","qwe","rty","poi"), c("x","y","z")) 
library(geometry) 
delaunaynMat <- delaunayn(mat) 

2. Extract All Adjacent Point Pairs

For each tetrahedron, generate all possible vertex pairs (each pair represents an edge). We'll use combn() to create these pairs, then combine them all into a single list:

# Generate all edge pairs from each tetrahedron
all_edge_pairs <- lapply(1:nrow(delaunaynMat), function(row_idx) {
  # Get the 4 vertex indices for the current tetrahedron
  vertices <- delaunaynMat[row_idx, ]
  # Generate all 2-vertex combinations (edges)
  combn(vertices, 2)
})

# Combine all pairs into a single matrix (columns are pairs)
all_edge_pairs <- do.call(cbind, all_edge_pairs)
# Transpose to get one pair per row
all_edge_pairs <- t(all_edge_pairs)

3. Remove Duplicate Pairs

Since two points might share edges in multiple tetrahedrons, we'll keep only unique pairs to avoid redundant entries in the adjacency matrix:

unique_edge_pairs <- unique(all_edge_pairs)

4. Initialize and Populate the Adjacency Matrix

Create an empty matrix with row/column names matching your original points, then mark all adjacent pairs as 1 (non-adjacent pairs stay 0):

# Get point names and count
point_names <- rownames(mat)
n_points <- nrow(mat)

# Initialize empty adjacency matrix (0 = no connection, 1 = connected)
adj_matrix <- matrix(
  0,
  nrow = n_points,
  ncol = n_points,
  dimnames = list(point_names, point_names)
)

# Mark adjacent pairs (undirected, so both (i,j) and (j,i) get 1)
adj_matrix[cbind(unique_edge_pairs[, 1], unique_edge_pairs[, 2])] <- 1
adj_matrix[cbind(unique_edge_pairs[, 2], unique_edge_pairs[, 1])] <- 1

Example Output #

For your 4-point example, the adjacency matrix will look like this (all points are connected since they form a single tetrahedron):

asd qwe rty poi
asd   0   1   1   1
qwe   1   0   1   1
rty   1   1   0   1
poi   1   1   1   0

Optimization for Large Matrices #

If you're working with a very large dataset (hundreds/thousands of points), the vectorized assignment above (cbind() approach) is much faster than using a loop. Avoid loops here to keep the code efficient.

内容的提问来源于stack exchange，提问作者minoo