Computing the boundary of ${\cal C}_{obs}$

So far, the method quickly identifies each edge that contributes to ${\cal C}_{obs}$. It can also construct a solid representation of ${\cal C}_{obs}$ in terms of half-planes. This requires defining $n+m$ linear equations (assuming there are no collinear edges).

Figure 4.16: Two different types of contact, each of which generates a different kind of ${\cal C}_{obs}$ edge [280,657].

There are two different ways in which an edge of ${\cal C}_{obs}$ is generated, as shown in Figure 4.16 [282,657]. Type EV contact refers to the case in which an edge of ${\cal A}$ is in contact with a vertex of ${\cal O}$. Type EV contacts contribute to $n$ edges of ${\cal C}_{obs}$, once for each edge of ${\cal A}$. Type VE contact refers to the case in which a vertex of ${\cal A}$ is in contact with an edge of ${\cal O}$. This contributes to $m$ edges of ${\cal C}_{obs}$. The relationships between the edge normals are also shown in Figure 4.16. For Type EV, the inward edge normal points between the outward edge normals of the obstacle edges that share the contact vertex. Likewise for Type VE, the outward edge normal of ${\cal O}$ points between the inward edge normals of ${\cal A}$.

Using the ordering shown in Figure 4.15b, Type EV contacts occur precisely when an edge normal of ${\cal A}$ is encountered, and Type VE contacts occur when an edge normal of ${\cal O}$ is encountered. The task is to determine the line equation for each occurrence. Consider the case of a Type EV contact; the Type VE contact can be handled in a similar manner. In addition to the constraint on the directions of the edge normals, the contact vertex of ${\cal O}$ must lie on the contact edge of ${\cal A}$. Recall that convex obstacles were constructed by the intersection of half-planes. Each edge of ${\cal C}_{obs}$ can be defined in terms of a supporting half-plane; hence, it is only necessary to determine whether the vertex of ${\cal O}$ lies on the line through the contact edge of ${\cal A}$. This condition occurs precisely as $n$ and $v$ are perpendicular, as shown in Figure 4.17, and yields the constraint $n \cdot v = 0$.

Figure 4.17: Contact occurs when $n$ and $v$ are perpendicular.

Note that the normal vector $n$ does not depend on the configuration of ${\cal A}$ because the robot cannot rotate. The vector $v$, however, depends on the translation $q = (x_t,y_t)$ of the point $p$. Therefore, it is more appropriate to write the condition as $n \cdot v(x_t,y_t) =0$. The transformation equations are linear for translation; hence, $n \cdot v(x_t,y_t) =0$ is the equation of a line in ${\cal C}$. For example, if the coordinates of $p$ are $(1,2)$ for ${\cal A}(0,0)$, then the expression for $p$ at configuration $(x_t,y_t)$ is $(1 + x_t, 2 + y_t)$. Let $f(x_t,y_t) = n \cdot v(x_t,y_t)$. Let $H = \{ (x_t,y_t) \in {\cal C}\;\vert\; f(x_t,y_t) \leq 0 \}$. Observe that any configurations not in $H$ must lie in ${\cal C}_{free}$. The half-plane $H$ is used to define one edge of ${\cal C}_{obs}$. The obstacle region ${\cal C}_{obs}$ can be completely characterized by intersecting the resulting half-planes for each of the Type EV and Type VE contacts. This yields a convex polygon in ${\cal C}$ that has $n+m$ sides, as expected.

Figure 4.18: Consider constructing the obstacle region for this example.

Figure 4.19: The various contact conditions are shown in the order as the edge normals appear around ${\mathbb{S}}^1$ (using inward normals for ${\cal A}$ and outward normals for ${\cal O}$).

Example 4..15 (The Boundary of ${\cal C}_{obs}$)   Consider building a geometric model of ${\cal C}_{obs}$ for the robot and obstacle shown in Figure 4.18. Suppose that the orientation of ${\cal A}$ is fixed as shown, and ${\cal C}= {\mathbb{R}}^2$. In this case, ${\cal C}_{obs}$ will be a convex polygon with seven sides. The contact conditions that occur are shown in Figure 4.19. The ordering as the normals appear around ${\mathbb{S}}^1$ (using inward edge normals for ${\cal A}$ and outward edge normals for ${\cal O}$). The ${\cal C}_{obs}$ edges and their corresponding contact types are shown in Figure 4.19. $\blacksquare$