#### Computing the boundary of So far, the method quickly identifies each edge that contributes to . It can also construct a solid representation of in terms of half-planes. This requires defining linear equations (assuming there are no collinear edges). There are two different ways in which an edge of is generated, as shown in Figure 4.16 [282,657]. Type EV contact refers to the case in which an edge of is in contact with a vertex of . Type EV contacts contribute to edges of , once for each edge of . Type VE contact refers to the case in which a vertex of is in contact with an edge of . This contributes to edges of . 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 points between the inward edge normals of .

Using the ordering shown in Figure 4.15b, Type EV contacts occur precisely when an edge normal of is encountered, and Type VE contacts occur when an edge normal of 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 must lie on the contact edge of . Recall that convex obstacles were constructed by the intersection of half-planes. Each edge of can be defined in terms of a supporting half-plane; hence, it is only necessary to determine whether the vertex of lies on the line through the contact edge of . This condition occurs precisely as and are perpendicular, as shown in Figure 4.17, and yields the constraint . Note that the normal vector does not depend on the configuration of because the robot cannot rotate. The vector , however, depends on the translation of the point . Therefore, it is more appropriate to write the condition as . The transformation equations are linear for translation; hence, is the equation of a line in . For example, if the coordinates of are for , then the expression for at configuration is . Let . Let . Observe that any configurations not in must lie in . The half-plane is used to define one edge of . The obstacle region 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 that has sides, as expected.  Example 4..15 (The Boundary of )   Consider building a geometric model of for the robot and obstacle shown in Figure 4.18. Suppose that the orientation of is fixed as shown, and . In this case, 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 (using inward edge normals for and outward edge normals for ). The edges and their corresponding contact types are shown in Figure 4.19. Steven M LaValle 2012-04-20