polygonDecomposition

Decompose polygon into nonoverlapping polygons

Since R2025a

collapse all in page

    Syntax

    polySet = polygonDecomposition(poly)
    [polySet,solnInfo] = polygonDecomposition(poly)
    [___,solnInfo] = polygonDecomposition(poly,options)

    Description

    polySet = polygonDecomposition(poly) decomposes a polygon into a set of nonoverlapping polygons whose union is equivalent to the original polygon using the boustrophedon decomposition algorithm. The output polygons have convex edges or vertical left and right edges, enabling you to sweep the entirety of the original polygon in a single pass using a vertical sweeping pattern.

    example

    [polySet,solnInfo] = polygonDecomposition(poly) returns decomposition solution information, such as the vertices and whether or not those vertices are in the holes of the original polygon.

    [___,solnInfo] = polygonDecomposition(poly,options) additionally specifies decomposition algorithm options, and returns any combination of output arguments from previous syntaxes. To return a connectivity graph of the nonoverlapping polygons from the decomposition as a field in the solnInfo output argument, the ReturnConnectivity property of options must be true or 1.

    example

    Examples

    collapse all

    Open Live Script

    Load polygon vertices and use the vertices to create a polyshape object.

    load("exampleSimplePolygonVertices.mat","verticesX","verticesY")
p = polyshape(verticesX,verticesY);

    Perform polygon decomposition with the default algorithm and options.

    polySet = polygonDecomposition(p);

    Plot the original polygon and the decomposed polygon side by side.

    tiledlayout(1,2,TileSpacing="loose")
nexttile
plot(p)
title(["Original Polygon","Containing Concave Hole"])
nexttile
plot(polySet)
title(["Nonoverlapping","Decomposed Polygons"])

    Figure contains 2 axes objects. Axes object 1 with title Original Polygon Containing Concave Hole contains an object of type polygon. Axes object 2 with title Nonoverlapping Decomposed Polygons contains 5 objects of type polygon.

    Open Live Script

    Load a polyshape and plot it. 

    load("exampleComplexPolyshape.mat","p")
plot(p)
title("Original Polygon")

    Figure contains an axes object. The axes object with title Original Polygon contains an object of type polygon.

    Decompose the polygon using each reconnection method.

    bOpts1 = boustrophedonOptions(ReconnectionMethod="nearest");
[polySet1,info1] = polygonDecomposition(p,bOpts1);
bOpts2 = boustrophedonOptions(ReconnectionMethod="none");
[polySet2,info2] = polygonDecomposition(p,bOpts2);
bOpts3 = boustrophedonOptions(ReconnectionMethod="all");
[polySet3,info3] = polygonDecomposition(p,bOpts3);

    Show the polygon decomposition with a connectivity graph overlay for each reconnection method.

    plot(polySet1)
hold on
exampleHelperShowGraphConnectionsOnPolyset(polySet1,info1.Connectivity,0.5);
title("Polygon Decomposition with Connection Graph");
subtitle("ReconnectionMethod=''nearest''")
hold off

    Figure contains an axes object. The axes object with title Polygon Decomposition with Connection Graph contains 10 objects of type polygon, graphplot.

    plot(polySet2)
hold on
exampleHelperShowGraphConnectionsOnPolyset(polySet2,info2.Connectivity,0.5);
title("Polygon Decomposition with Connection Graph");
subtitle("ReconnectionMethod=''none''");
hold off

    Figure contains an axes object. The axes object with title Polygon Decomposition with Connection Graph contains 10 objects of type polygon, graphplot.

    plot(polySet3)
hold on
exampleHelperShowGraphConnectionsOnPolyset(polySet3,info3.Connectivity,0.5);
title("Polygon Decomposition with Connection Graph");
subtitle("ReconnectionMethod=''all''");
hold off

    Figure contains an axes object. The axes object with title Polygon Decomposition with Connection Graph contains 10 objects of type polygon, graphplot.

    This is the helper function for plotting the polygon decomposition and overlaying the connectivity graph.

    function gHandle = exampleHelperShowGraphConnectionsOnPolyset(polySet,connectionGraph,lineWidth)

    % Get the current axes
    ax = gca;
    ax.ColorOrderIndex = 1; % Reset the color order index

    % Overlay the connectivity graph
    gHandle = show(connectionGraph);
    gHandle.EdgeAlpha = 0.75;
    gHandle.LineWidth = lineWidth; % Set the line width for the graph edges

    % Calculate and plot the centroids
    [cx,cy] = centroid(polySet);

    % Set the xy-positions of the connectivity graph to the centroids of 
    % the polygons
    gHandle.XData = cx';
    gHandle.YData = cy';
end

    This example uses:

    Open Live Script

    The polygonDecomposition function enables you to plan UAV coverage paths while accounting for areas that you do not need to include in coverage paths.

    First, load the polygon as a polyshape representing the region to survey, and decompose the polygon into nonoverlapping convex polygons.

    load("exampleCoveragePlanningPolyshape.mat","p")
polySet = polygonDecomposition(p);

    Extract vertices from each decomposed polygons, and store them in a cell array.

    polygonVertices = cell(numel(polySet),1);
for i = 1:numel(polySet)
    polygonVertices{i} = polySet(i).Vertices;
end

    Create a uavCoverageSpace object with the decomposed polygon vertices, and visualize the coverage space.

    space = uavCoverageSpace(Polygons=polygonVertices);
ax = show(space,FontSize=1,LineWidth=0.25);
title("UAV Coverage Space");
axis padded

    Figure contains an axes object. The axes object with title UAV Coverage Space contains 10 objects of type polygon, text.

    space.UnitWidth = 0.4; % Sensor footprint width

    Create a uavCoveragePlanner object. Specify the takeoff and landing positions, and then plan the coverage path.

    planner = uavCoveragePlanner(space);
takeoff = [0 0 0];
landing = [0 -4 0];
path = plan(planner,takeoff,landing);

    Visualize the planned path on the coverage space.

    hold on
ax.ColorOrderIndex=1;
h1 = scatter(takeoff(1),takeoff(2),"filled");
h2 = scatter(landing(1),landing(2),"filled");

    Plot the planned coverage path.

    ax.ColorOrderIndex=4;
plot(path(:,1),path(:,2),LineWidth=1.25)
legend([h1 h2],"Takeoff","Landing",Location="southeast")
title("Coverage Path")
hold off

    Figure contains an axes object. The axes object with title Coverage Path contains 13 objects of type polygon, text, scatter, line. These objects represent Takeoff, Landing.

    Input Arguments

    collapse all

    Polygon to decompose, specified as a polyshape object.

    Example: polyshape([0 0 1 1],[1 0 0 1]) creates a solid square defined by the four points (0,1), (0,0), (1,0), and (1,1).

    Decomposition algorithm options, specified as a boustrophedonOptions object. By default, polygonDecomposition uses a boustrophedonOptions object with the ReturnConnectivity property set to false and other properties set to their default values.

    Example: boustrophedonOptions(ReconnectionMethod="nearest")

    Output Arguments

    collapse all

    Decomposed nonoverlapping polygons, returned as an N-element array of polyshape objects. N is the total number of polygons generated from decomposing poly.

    Decomposition solution information, returned as a structure with these fields:

    • Vertices — Vertices of the decomposed polygons, returned as an M-by-2 matrix. Each row is the xy-coordinate of a vertex, and M is the total number of vertices from the decomposed polygons.

    • VertexOnHole — Status of the decomposed polygon vertices, returned as an M-element column vector of logical values. Each element corresponds to a vertex in the Vertices field. For example, if the value of VertexOnHole(2) is 1, then the vertex at Vertices(2) defines a hole or nontraversable area.

    • Connectivity — Connectivity graph between the decomposed nonoverlapping polygons, returned as a navGraph object. To generate Connectivity, you must specify the options argument as a boustrophedonOptions object with the ReturnConnectivity property set to true or 1.

    References

    [1] Choset, Howie. "Coverage of Known Spaces: The Boustrophedon Cellular Decomposition." Autonomous Robots 9, no.3 (2000): 247–53. https://doi.org/10.1023/A:1008958800904.

    Extended Capabilities

    expand all

    C/C++ Code Generation
    Generate C and C++ code using MATLAB® Coder™.

    Version History

    Introduced in R2025a

    See Also

    |