Understanding ridge vertices returned by `scipy.spatial.Voronoi` in 3D

Question

I don't understand the return format of the ridge vertices for the function scipy.spatial.Voronoi. When using this function in 2D, the vertices are in pairs for one ridge, which is the format I expect, but in 3D, the number of vertices in ridges tends to have more than 2 points.

Why would a ridge need more than 2 points?

With some post-processing, can I simplify the format into 2 points per ridge?

Examples

(The int in vor.ridge_vertices refer to a point index in vor.vertices)

import numpy as np
from scipy.spatial import Voronoi

# for 2D
points = np.array([[0, 0], [0, 1], [0, 2],
                   [1, 0], [1, 1], [1, 2],
                   [2, 0], [2, 1], [2, 2]])

vor = Voronoi(points)

# vor.vertices :
# [[0.5 0.5]
#  [0.5 1.5]
#  [1.5 0.5]
#  [1.5 1.5]]
#
# vor.ridge_vertices : (only pairs of vertices)
# [[-1, 0],
#  [-1, 0],
#  [-1, 1],
#  [-1, 1],
#  [0, 1],
#  [-1, 3],
#  [-1, 2],
#  [2, 3],
#  [-1, 3],
#  [-1, 2],
#  [1, 3],
#  [0, 2]]

import numpy as np
from scipy.spatial import Voronoi

# for 3D
points = np.array([[0, 0, 0], [0, 0, 1], [0, 0, 2],
                   [0, 1, 0], [0, 1, 1], [0, 1, 2],
                   [0, 2, 0], [0, 2, 1], [0, 2, 2],
                   [1, 0, 0], [1, 0, 1], [1, 0, 2],
                   [1, 1, 0], [1, 1, 1], [1, 1, 2],
                   [1, 2, 0], [1, 2, 1], [1, 2, 2]])

vor = Voronoi(points)

# vor.vertices :
# [[0.5 1.5 0.5]
#  [0.5 0.5 0.5]
#  [0.5 0.5 1.5]
#  [0.5 1.5 1.5]]
#
# vor.ridge_vertices : (3-4 vertices per ridge)
# [[3, 0, -1],
#  [0, -1, 1],
#  [1, 0, 3, 2],
#  [2, 1, -1],
#  [2, 3, -1],
#  [3, -1, 0],
#  [-1, 1, 0],
#  [-1, 3, 0],
#  [-1, 1, 0],
#  [-1, 2, 3],
#  [-1, 1, 2],
#  [-1, 1, 2],
#  [-1, 2, 3]]

Context:

I want to skeletonize an 3D object using voronoi ridge vertices. To do so, I mesh my object to select points of the surface, give them to the function scipy.spatial.Voronoi and use the ridge vertices inside the object as my skeleton.

As a work around, I'm currently using the regions to guess the ridge vertices, but it's prone to bugs and slow. Learning how to correctly use the returned ridge vertices should fix this.

The reason I want to use voronoi skeletonization is because it seemed like the easiest to implement. I know about skimage.morphology.skeletonize_3d, but it tends to lose smaller details (not sensible enough) and there is no parameters to play with.

I'm struggling to understand "the number of points in vertices tends to have more than 2 points". Vertice is a single point, the same dimensionality as input data. Can you provide a specific example of what makes this confusion? — Marat, Aug 29 '21 at 17:19
@Marat Yes sorry I mixed up vertices and ridges. I want to understand why a ridge should have more than 2 vertices/points. I added an example `ridge_vertices`. — Takyon, Aug 29 '21 at 17:43

score 3 · Accepted Answer · answered Aug 29 '21 at 20:08

In 2D, regions are separated by a single line segment, thus always 2 points per ridge. In 3D and up, regions separation "plane segments" are typically triangular, but they can have 4+ edges, too.

For sceletonization purposes, one approach would be to show the outline of the separation region, skipping virtual (-1) points. So, [3, 0, -1] would translate to one line between points 3 and 0. [1, 0, 3, 2] will generate segments 1-0, 0-3, 3-2, 2-1. As an additional improvement, ridges with 4+ points can be further split into trianges, so in case of [1, 0, 3, 2] another segment would be 0-2 or 1-3.

I am still not sure if I got the question right, let me know if I didn't

This does explain why ridges have more than 2 vertices, I only saw them as line segment and not plane segment. I'll definitely have to rethink my approach. Thank you very much. — Takyon, Aug 29 '21 at 20:27

Understanding ridge vertices returned by `scipy.spatial.Voronoi` in 3D

Examples

Context:

1 Answers1