Matlab中如何将凸包分割为多个共享边界的 hull 技术咨询

Great question! I’ve worked with convex hull partitioning in MATLAB before, so I can walk you through the relevant algorithms and practical implementations to split a single convex hull into shared-boundary sub-hulls of the same category.

Relevant Algorithms #

Since your original shape is a convex hull, we can leverage its properties to ensure all sub-hulls remain convex and share clean boundaries:

• Constrained Convex Partitioning: The most straightforward approach. Define internal split lines (connecting vertices, edges, or internal points) to divide the hull into smaller convex sub-hulls. Any straight-line split of a convex shape will result in convex sub-hulls, and adjacent sub-hulls will automatically share the split line as a boundary.
• Voronoi-Based Partitioning: If you need sub-hulls centered around specific internal points (e.g., cluster centers), place seed points inside the hull, compute the Voronoi diagram, then clip each Voronoi cell to the original convex hull. The clipped cells will be convex and share boundaries with their neighbors.
• Grid-Based Partitioning: For regular, uniform splits (like dividing the hull into equal rectangles/triangles), overlay a grid on the hull and extract each grid cell that lies within the original shape. This works well for simple, structured partitioning.

MATLAB Implementation Examples #

Let’s dive into code for each method, using practical examples:

1. Constrained Split (Manual Boundary Definition) #

Suppose you have a convex hull and want to split it along a vertical line through its center:

% Define original convex hull (square vertices)
hull_vertices = [0 0; 0 1; 1 1; 1 0];

% Define split line: connects bottom-center to top-center
split_start = [0.5, 0];
split_end = [0.5, 1];

% Construct the two sub-hulls
subhull_left = [hull_vertices(1:2, :); split_end; split_start];
subhull_right = [hull_vertices(3:4, :); split_start; split_end];

% Visualize results
figure;
plot(hull_vertices(:,1), hull_vertices(:,2), 'b-', 'LineWidth', 2);
hold on;
plot(subhull_left(:,1), subhull_left(:,2), 'r--', 'LineWidth', 1.5);
plot(subhull_right(:,1), subhull_right(:,2), 'g--', 'LineWidth', 1.5);
plot([split_start(1), split_end(1)], [split_start(2), split_end(2)], 'ko-', 'MarkerSize', 6);
axis equal;
legend('Original Hull', 'Left Sub-hull', 'Right Sub-hull');

2. Voronoi-Based Partitioning #

If you want to split the hull into sub-hulls around 3 internal seed points:

% Original convex hull (rectangle)
hull_vertices = [0 0; 0 2; 3 2; 3 0];

% Define 3 seed points inside the hull
seeds = [1 1; 2 1; 1.5 1.5];

% Compute Voronoi diagram
[vx, vy] = voronoi(seeds(:,1), seeds(:,2));

% Clip each Voronoi cell to the convex hull
subhulls = cell(size(seeds,1), 1);
hull_closed = [hull_vertices; hull_vertices(1,:)]; % Close the hull polygon

for i = 1:size(seeds,1)
    % Extract finite vertices of the Voronoi cell
    cell_vx = vx(:,i);
    cell_vy = vy(:,i);
    cell_vertices = [cell_vx(~isinf(cell_vx)), cell_vy(~isinf(cell_vy))];
    
    % Clip cell to the original hull using polyxpoly
    [clip_x, clip_y] = polyxpoly(cell_vertices(:,1), cell_vertices(:,2), ...
                                hull_closed(:,1), hull_closed(:,2));
    subhulls{i} = [clip_x, clip_y];
end

% Plot results
figure;
plot(hull_vertices(:,1), hull_vertices(:,2), 'b-', 'LineWidth', 2);
hold on;
colors = ['r', 'g', 'm'];
for i = 1:length(subhulls)
    plot(subhulls{i}(:,1), subhulls{i}(:,2), [colors(i) '--'], 'LineWidth', 1.5);
    plot(seeds(i,1), seeds(i,2), [colors(i) 'o'], 'MarkerSize', 8);
end
axis equal;
legend('Original Hull', 'Sub-hull 1', 'Sub-hull 2', 'Sub-hull 3');

3. Grid-Based Regular Split #

To split the hull into a 2x3 grid of rectangular sub-hulls:

% Original convex hull (rectangle)
hull_vertices = [0 0; 0 4; 6 4; 6 0];

% Grid parameters: 2 rows, 3 columns
num_rows = 2;
num_cols = 3;

% Calculate grid step sizes
x_min = min(hull_vertices(:,1));
x_max = max(hull_vertices(:,1));
y_min = min(hull_vertices(:,2));
y_max = max(hull_vertices(:,2));
x_step = (x_max - x_min)/num_cols;
y_step = (y_max - y_min)/num_rows;

% Generate sub-hulls
subhulls = cell(num_rows*num_cols, 1);
hull_closed = [hull_vertices; hull_vertices(1,:)];
idx = 1;

for i = 0:num_rows-1
    for j = 0:num_cols-1
        % Define grid cell vertices
        cell_vertices = [x_min + j*x_step, y_min + i*y_step;
                         x_min + (j+1)*x_step, y_min + i*y_step;
                         x_min + (j+1)*x_step, y_min + (i+1)*y_step;
                         x_min + j*x_step, y_min + (i+1)*y_step];
        
        % Clip cell to hull (redundant here, but useful for non-rectangular convex hulls)
        [clip_x, clip_y] = polyxpoly(cell_vertices(:,1), cell_vertices(:,2), ...
                                    hull_closed(:,1), hull_closed(:,2));
        subhulls{idx} = [clip_x, clip_y];
        idx = idx + 1;
    end
end

% Plot
figure;
plot(hull_vertices(:,1), hull_vertices(:,2), 'b-', 'LineWidth', 2);
hold on;
colors = ['r', 'g', 'm', 'c', 'y', 'k'];
for i = 1:length(subhulls)
    plot(subhulls{i}(:,1), subhulls{i}(:,2), [colors(i) '--'], 'LineWidth', 1.5);
end
axis equal;
title('Grid-Based Convex Hull Split');

Key Notes #

• Convexity Guarantee: Since the original shape is convex, all splits using these methods will produce convex sub-hulls—no need to re-compute convexity for each sub-hull.
• Shared Boundaries: All adjacent sub-hulls will share exact boundary segments, so there’s no gap or overlap between them.
• Iterative Splitting: For complex splits (more than 2 sub-hulls), you can iteratively apply constrained partitioning: split the original hull into two, then split one of the sub-hulls again, and so on.

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