tailieunhanh - Effective Computational Geometry for Curves & Surfaces - Boissonnat & Teillaud Part 4

Tham khảo tài liệu 'effective computational geometry for curves & surfaces - boissonnat & teillaud part 4', kỹ thuật - công nghệ, cơ khí - chế tạo máy phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | 1 Arrangements 65 a b c Fig. . A spherical arrangement a its full trapezoidal decomposition b and its partial trapezoidal decomposition c for the case of a single robot with a limited field of view of ip radians called a -searcher based on the arrangement of curves that represent the visibility constraints induced by the environment and the searchers field of view. Each obstacle edge defines a critical curve that is the locus of all points that see it at an angle namely a pair of circular arcs. The algorithm for a single robot can also be generalized for multiple searches albeit at a loss of completeness . See 179 for further details and on-line examples. Shortest Path with Clearance Wein et al. 336 devise a new structure for finding the shortest path for a point robot moving in the plane among polygonal obstacles between a source and a goal configuration while trying to guarantee that the clearance between the robot and the obstacles is at least c. The main idea is to inflate each obstacle by a radius c see also Sect. and compute the visibility diagram of the dilated obstacles. A visibility edge is a bitangent to rounded corners of the dilated obstacle. When one encounters a region where it is impossible to guarantee a distance of at least c from the obstacles which is characterized by an overlap between the dilated obstacles the Voronoi diagram of the original obstacles is computed and combined into the visibility diagram representing a path with maximal clearance in this region. The combined diagram therefore contains line segments circular arcs and parabolic It is constructed using the conic-arc traits of Cgal s arrangement package. 27The Voronoi diagram of polygons is a collection of line segments and parabolic arcs a parabolic arc is the locus of points equidistant from a polygon vertex and an edge of another polygon. 66 E. Fogel D. Halperin L. Kettner M. Teillaud R. Wein N. Wolpert Further Reading and Open problems In this chapter we .