Introduction to B-Spline Fitting for Hierarchical Edge Bundling

In recent years, hierarchical edge bundling has become a popular technique for visualizing large networks and complex systems. One common approach to implementing this method is to use B-spline fitting to approximate the underlying structure of the network. In this article, we will delve into the world of B-splines and explore how they can be used to fit a B-spline curve to a control path.

What are B-Splines?

B-splines (short for “basis spline”) are a type of mathematical function that is widely used in computer graphics, engineering, and scientific computing. They were first introduced by David Cox in 1972 as an alternative to traditional splines. The key idea behind B-splines is to define a set of basis functions, called B-spline basis functions, which can be combined to form more complex shapes.

How are B-Splines Used?

B-splines are typically used to fit curves and surfaces to data points in a high-dimensional space. They have several advantages over traditional splines:

• Flexibility: B-splines can capture more complex shapes than traditional splines.
• Smoothness: B-splines can be made very smooth by using a large number of basis functions.
• Efficiency: B-splines can be computed efficiently using algorithms like the de Boor algorithm.

Fitting a B-Spline Curve to a Control Path

In the context of hierarchical edge bundling, we want to fit a B-spline curve to a control path that represents the underlying structure of the network. The control path is typically represented as a set of 2D points (x, y), where x and y represent the coordinates of nodes in the network.

Defining the Time Variable

One important step when fitting a B-spline curve to a control path is defining the time variable. In traditional splines, the time variable is often assumed to be equal to the index of the data point (i.e., the x-coordinate). However, in this case, we need to use a different approach since the control path is not monotonous in both x and y.

Using B-Splines with bs() Function

In R, the bs() function can be used to specify the basis functions for a B-spline. We can create a time variable using seq(), which generates a sequence of values from 0 to nrow(path). Then, we can use lm() to fit linear models with B-spline basis functions.

Example Code

library(splines)

# Create the control path
path <- data.frame(
    x = c(3, 3.5, 4.6875, 9.625, 5.5625, 19.62109375, 33.6796875, 40.546875, 36.59375, 34.5, 33.5, 33),
    y = c(0, 1, 4, 5, 6, 8, 7, 6, 5, 2, 1, 0)
)

# Add the time variable
path$time <- seq(nrow(path))

# Fit the models
df <- 5
lm_x <- lm(x ~ bs(time, df), path)
lm_y <- lm(y ~ bs(time, df), path)

# Predict the positions and plot them
pred_df <- data.frame(x = 0, y = 0, time = seq(min(path$time), max(path$time), length.out = 100))
plot(predict(lm_x, newdata = pred_df),
     predict(lm_y, newdata = pred_df),
     type = 'l')

Handling Non-Sequential Data

One common issue when fitting B-splines to control paths is handling non-sequential data. In our example code above, we used a fixed time variable that spanned the entire range of x-coordinates in the control path. However, this may not always be the case.

Using plotpath() Function

To handle non-sequential data, we can define a custom function called plotpath(). This function takes the control path and plots the B-spline curve along with the original points.

plotpath <- function(path, col = "red") {
    # Add the time variable with random spacing
    path$time <- sort(runif(nrow(path)))

    # Fit the models
    df <- 5
    lm_x <- lm(x ~ bs(time, df), path)
    lm_y <- lm(y ~ bs(time, df), path)

    # Predict the positions and plot them
    pred_df <- data.frame(x = 0, y = 0, time = seq(min(path$time), max(path$time), length.out = 100))
    lines(predict(lm_x, newdata = pred_df), predict(lm_y, newdata = pred_df), col = col)
}

par(ask = TRUE); # wait until you click on the figure or hit enter to show the next figure
for (i in 1:5) plotpath(path, col = "red")

Conclusion

In this article, we explored how B-splines can be used to fit a curve to a control path. We covered the basics of B-splines, including how they work and why they are useful for modeling complex shapes. We also presented an example code that demonstrates how to use B-splines in R.

By understanding how B-splines work and how to apply them effectively, you can unlock a powerful tool for visualizing large networks and complex systems. Whether you’re working on hierarchical edge bundling or another related project, this knowledge will serve you well.

Last modified on 2023-12-26