Janan lisäys rajoitettuun kolmiointiin

The two-dimensional path-planning problem involves determining the shortest path between two points on a plane while adhering to a set of polygonal constraints. In this thesis, we show how the path-planning problem in dynamically updated environments gives rise to a need for an edge-flipping based line-segment insertion procedure for constrained Delaunay triangulations, and present an efficient algorithm for the problem. The algorithm operates on convex vertices situated along the boundary of the channel of triangles that intersect with the edge that is to be inserted. We show that such vertices can be removed from the channel using a finite series of edge-flip operations, and that the repeated application of the vertex removal procedure results in the insertion of the requested edge in the triangulation. Furthermore, we present a working sample implementation of the resulting algorithm