A polygonal C-space obstacle

A simple algorithm for computing ${\cal C}_{obs}$ exists in the case of a 2D world that contains a convex polygonal obstacle ${\cal O}$ and a convex polygonal robot ${\cal A}$ [657]. This is often called the star algorithm. For this problem, ${\cal C}_{obs}$ is also a convex polygon. Recall that nonconvex obstacles and robots can be modeled as the union of convex parts. The concepts discussed below can also be applied in the nonconvex case by considering ${\cal C}_{obs}$ as the union of convex components, each of which corresponds to a convex component of ${\cal A}$ colliding with a convex component of ${\cal O}$.

The method is based on sorting normals to the edges of the polygons on the basis of angles. The key observation is that every edge of ${\cal C}_{obs}$ is a translated edge from either ${\cal A}$ or ${\cal O}$. In fact, every edge from ${\cal O}$ and ${\cal A}$ is used exactly once in the construction of ${\cal C}_{obs}$. The only problem is to determine the ordering of these edges of ${\cal C}_{obs}$. Let $\alpha_1$, $\alpha_2$, $\ldots$, $\alpha_n$ denote the angles of the inward edge normals in counterclockwise order around ${\cal A}$. Let $\beta_1$, $\beta_2$, $\ldots$, $\beta_n$ denote the outward edge normals to ${\cal O}$. After sorting both sets of angles in circular order around ${\mathbb{S}}^1$, ${\cal C}_{obs}$ can be constructed incrementally by using the edges that correspond to the sorted normals, in the order in which they are encountered.

Figure 4.13: A triangular robot and a rectangular obstacle.

Figure 4.14: (a) Slide the robot around the obstacle while keeping them both in contact. (b) The edges traced out by the origin of ${\cal A}$ form ${\cal C}_{obs}$.

Figure 4.15: (a) Take the inward edge normals of ${\cal A}$ and the outward edge normals of ${\cal O}$. (b) Sort the edge normals around ${\mathbb{S}}^1$. This gives the order of edges in ${\cal C}_{obs}$.

Example 4..14 (A Triangular Robot and Rectangular Obstacle)   To gain an understanding of the method, consider the case of a triangular robot and a rectangular obstacle, as shown in Figure 4.13. The black dot on ${\cal A}$ denotes the origin of its body frame. Consider sliding the robot around the obstacle in such a way that they are always in contact, as shown in Figure 4.14a. This corresponds to the traversal of all of the configurations in $\partial {\cal C}_{obs}$ (the boundary of ${\cal C}_{obs}$). The origin of ${\cal A}$ traces out the edges of ${\cal C}_{obs}$, as shown in Figure 4.14b. There are seven edges, and each edge corresponds to either an edge of ${\cal A}$ or an edge of ${\cal O}$. The directions of the normals are defined as shown in Figure 4.15a. When sorted as shown in Figure 4.15b, the edges of ${\cal C}_{obs}$ can be incrementally constructed. $\blacksquare$

The running time of the algorithm is $O(n + m)$, in which $n$ is the number of edges defining ${\cal A}$, and $m$ is the number of edges defining ${\cal O}$. Note that the angles can be sorted in linear time because they already appear in counterclockwise order around ${\cal A}$ and ${\cal O}$; they only need to be merged. If two edges are collinear, then they can be placed end-to-end as a single edge of ${\cal C}_{obs}$.