Trapezoidal Decomposition

This is one of the simplest Cell Decomposition methods.

With this technique, we divide the robot’s free space into a set of simpler regions and then form a graph where the nodes of the regions and the edges indicate which regions are adjacent to each other.

This figure shows a common approach to constructing such a decomposition for a two-dimensional configuration space. We sort the obstacle vertices based on their x-coordinates, and proceed from left to right, dividing the free space up into regions as we go.

This procedure ends up dividing the two-dimensional free space into a collection of trapezoidal or triangular regions. We can then form a graph where the nodes are these trapezoidal regions of free space and the edges indicate which of these regions are adjacent to each other. Path planning is then carried out by finding out which cell contains the start location and which the goal and then planning a path through the graph between these two nodes.