Part 7: Cell Decomposition

When/Why decompose?

Following these tutorials, we have seen that we can cover concave fields with obstacles. Then, it is a valid question to ask why the decomposition process is important for some fields.

We will use a L-shaped field as example.

• C++
• Python

F2CCells cells(F2CCell(F2CLinearRing({
    F2CPoint(  0,  0),
    F2CPoint( 90,  0),
    F2CPoint( 90, 20),
    F2CPoint( 20, 20),
    F2CPoint( 20, 90),
    F2CPoint(  0, 90),
    F2CPoint(  0,  0)})));

cells = f2c.Cells(f2c.Cell(f2c.LinearRing(f2c.VectorPoint([
    f2c.Point(  0,  0),
    f2c.Point( 90,  0),
    f2c.Point( 90, 20),
    f2c.Point( 20, 20),
    f2c.Point( 20, 90),
    f2c.Point(  0, 90),
    f2c.Point(  0,  0)]))));

We can be tempted to apply our usual workflow:

• C++
• Python

F2CRobot robot (1.0, 1.0);
double r_w = robot.getCovWidth();

f2c::hg::ConstHL const_hl;
f2c::sg::BruteForce bf;
f2c::obj::NSwathModified obj;

F2CCells no_hl_wo_decomp = const_hl.generateHeadlands(cells, 3.0 * r_w);
F2CSwathsByCells swaths_wo_decomp = bf.generateBestSwaths(obj, r_w, no_hl_wo_decomp);

robot = f2c.Robot(1.0, 1.0);
r_w = robot.getCovWidth();

const_hl = f2c.HG_Const_gen()
bf = f2c.SG_BruteForce();
obj = f2c.OBJ_NSwathModified();

no_hl_wo_decomp = const_hl.generateHeadlands(cells, 3.0 * r_w);
swaths_wo_decomp = bf.generateBestSwaths(obj, r_w, no_hl_wo_decomp);

This workflow returns a solution made by 84 swaths.

On the other hand, if we decompose first and then apply the same workflow:

• C++
• Python

f2c::decomp::TrapezoidalDecomp decomp;
decomp.setSplitAngle(0.5*M_PI);
F2CCells decomp_cell = decomp.decompose(cells);

F2CCells no_hl_decomp = const_hl.generateHeadlands(decomp_cell, 3.0 * r_w);
F2CSwathsByCells swaths_decomp = bf.generateBestSwaths(obj, r_w, no_hl_decomp);

decomp = f2c.DECOMP_TrapezoidalDecomp();
decomp.setSplitAngle(0.5*math.pi);
decomp_cell = decomp.decompose(cells);

no_hl_decomp = const_hl.generateHeadlands(decomp_cell, 3.0 * r_w);
swaths_decomp = bf.generateBestSwaths(obj, r_w, no_hl_decomp);

We get only 26 swaths!! That’s a huge improvement. Bigger field would benefit even more of this approach.

Decomposition and Route planner

The decomposition workflow doesn’t work directly with the route planner, because the middle headland ring of each decomposed cell are not connected between them.

To solve this, we create the middle headland ring first, decompose the inner part of that ring, and then carve a corridor where the decomposed cells border each other.

Running the headland generator a second time would connect the cells too, but it shrinks every border, taking a second headland off the outer boundary that already has one. CorridorHL only cuts where two cells meet, so the swaths reach the outer headland.

• C++
• Python

F2CCells mid_hl = const_hl.generateHeadlands(cells, 1.5 * r_w);
F2CCells decomp_mid_hl = decomp.decompose(mid_hl);
f2c::hg::CorridorHL corridor_hl;
F2CCells no_hl = corridor_hl.generateHeadlands(decomp_mid_hl, 1.5 * r_w);
F2CSwathsByCells swaths = bf.generateBestSwaths(obj, r_w, no_hl);

f2c::rp::RoutePlannerBase route_planner;
F2CRoute route = route_planner.genRoute(mid_hl, swaths);

mid_hl = const_hl.generateHeadlands(cells, 1.5 * r_w);
decomp_mid_hl = decomp.decompose(mid_hl);
corridor_hl = f2c.HG_Corridor_gen();
no_hl = corridor_hl.generateHeadlands(decomp_mid_hl, 1.5 * r_w);
swaths = bf.generateBestSwaths(obj, r_w, no_hl);

route_planner = f2c.RP_RoutePlannerBase();
route = route_planner.genRoute(mid_hl, swaths);