SHORTEST DIAGONAL TRIANGULATION OF CONVEX LAYERS

摘要

One problem in the field of computational geometry is therntriangulation of convex layers. The rotating caliper algorithmrnis an alternative to the constrained Delaunay triangulationrnmethod. We present an improved triangulation algorithm,rnwhich gives a mesh quality close to that of the ConstrainedrnDelaunay but substantially faster. Each layer willrnbe connected to the neighboring layer by edges and fromrnthe two vertices constituting an edge the proposed algorithmrnwill select the shortest diagonal to its next neighborsrnin the polygonal chain on the other side, i.e. from the outerrnlayer to the inner layer or vice versa. We discuss qualityrnissues regarding the rotating caliper method and some improvementsrnto it, as well as how a Constrained Delaunayrncan be efficiently implemented for convex layers.