Main Content

coverageDecomposition

Decompose concave polygon into convex polygons

Since R2023a

collapse all in page

    Syntax

    polygons = coverageDecomposition(concavePolygon)
    polygons = coverageDecomposition(concavePolygon,IntersectionTol=tolerance)

    Description

    The coverageDecomposition function decomposes coverage regions into subregions using vertex-edge decomposition[1]. This enables you to plan more efficient coverage paths using optimized planning options for each subregion to have minimum turns and then connect the plans together.

    polygons = coverageDecomposition(concavePolygon) decomposes the concave polygon concavePolygon into convex polygon areas polygons based on minimum-width criteria[1].

    example

    polygons = coverageDecomposition(concavePolygon,IntersectionTol=tolerance) tests the vertex edge decompositions with slopes that are between the tolerance tolerance, which respect to the polygon edges.

    Examples

    collapse all

    Open Live Script

    This example shows how to plan a coverage path for a region in local coordinates and compares the results of using the exhaustive solver with the results of using the minimum traversal solver.

    Define the vertices for a coverage space.

    area = [5 8.75; 5 27.5; 17.5 22.5; 25 31.25; 35 31.25; 30 20; 15 6.25];

    Because vertices define a concave polygon and the coverage planner requires convex polygons, decompose the polygon into convex polygons. Then create a coverage space with the polygons from decomposition.

    polygons = coverageDecomposition(area);
cs = uavCoverageSpace(Polygons=polygons);

    Define the takeoff and landing positions at [0 0 0] and [32.25 37.25 0], respectively. Then show the coverage space and plot the takeoff and landing positions.

    takeoff = [0 0 0];
landing = [32.25 37.25 0];
show(cs);
exampleHelperPlotTakeoffLandingLegend(takeoff,landing)

    Figure contains an axes object. The axes object contains 6 objects of type polygon, text, scatter. These objects represent Polygon 1, Polygon 2, Takeoff, Landing.

    Create a coverage planner with the exhaustive solver algorithm and another coverage planner with a minimum traversal solver algorithm. Because Polygon 2 is closer to the takeoff position, set the visiting sequence of the solver parameters such that we traverse Polygon 2 first.

    cpeExh = uavCoveragePlanner(cs,Solver="Exhaustive");
cpMin = uavCoveragePlanner(cs,Solver="MinTraversal");
cpeExh.SolverParameters.VisitingSequence = [2 1];
cpMin.SolverParameters.VisitingSequence = [2 1];

    Plan with both solver algorithms using the same takeoff and landing positions.

    [wptsExh,solnExh] = plan(cpeExh,takeoff,landing);
[wptsMin,solnMin] = plan(cpMin,takeoff,landing);

    Show the planned path for both the exhaustive and the minimum traversal algorithms.

    figure
show(cs);
title("Exhaustive Solver Algorithm")
exampleHelperPlotTakeoffLandingLegend(takeoff,landing,wptsExh)

    Figure contains an axes object. The axes object with title Exhaustive Solver Algorithm contains 7 objects of type polygon, text, scatter, line. These objects represent Polygon 1, Polygon 2, Takeoff, Landing, Path.

    figure
show(cs);
title("Minimum Traversal Solver Algorithm")
exampleHelperPlotTakeoffLandingLegend(takeoff,landing,wptsMin)

    Figure contains an axes object. The axes object with title Minimum Traversal Solver Algorithm contains 7 objects of type polygon, text, scatter, line. These objects represent Polygon 1, Polygon 2, Takeoff, Landing, Path.

    Export the waypoints from the minimum traversal solver to a .waypoints file with the reference frame set to north-east-down.

    exportWaypointsPlan(cpMin,solnMin,"coveragepath.waypoints",ReferenceFrame="NED")

    Input Arguments

    collapse all

    Concave polygon to decompose, specified as an N-by-2 matrix.

    Example: [0 0; 0 1; 1 1; 1 0]

    Data Types: double

    Intersection tolerance, specified nonnegative numeric scalar. The coverageDecomposition function uses the intersection tolerance to test if the vertex-edge decompositions are valid. For example, when the coverageDecomposition function decomposes a polygon into two polygons, those two polygons now have edges that intersect each other. The slopes of these intersecting edges must be within this tolerance. This is useful when polygons are slightly off alignment.

    Example: [0 0; 0 1; 1 1; 1 0]

    Data Types: single | double

    Output Arguments

    collapse all

    Convex polygons, returned as a N-element cell array of M-by-2 matrices. N is the total number of polygons, and M is the total number of vertices that define each polygon.

    The format of the vertices is local xy-coordinates in the form [x y], in meters.

    Example: {[0 0; 0 1; 1 1; 1 0],[1 1; 2 2; 3 1]}

    References

    [1] Li, Yan, Hai Chen, Meng Joo Er, and Xinmin Wang. “Coverage Path Planning for UAVs Based on Enhanced Exact Cellular Decomposition Method.” Mechatronics 21, no. 5 (August 2011): 876–85. https://doi.org/10.1016/j.mechatronics.2010.10.009.

    Extended Capabilities

    Version History

    Introduced in R2023a

    expand all

    See Also

    |

    Topics