Structured Orthogonal Near-Boundary Voronoi Mesh Layers for Planar Domains

摘要

We consider the problem of constructing a purely Voronoi mesh where the union of uncut Voronoi cells approximates the planar computational domain with piecewise-smooth boundary. Smooth boundary fragments are approximated by the Voronoi edges and Voronoi vertices are placed near summits of sharp boundary corners. We suggest a self-organization meshing algorithm which covers the boundary of domain by an almost-structured band of non-simplicial Delaunay cells. This band consists of quadrangles on the smooth boundary segment and convex polygons around sharp corners. The dual Voronoi mesh is a double-layered orthogonal structure where the central line of the layer approximates the boundary. The overall Voronoi mesh has a hybrid structure and consists of high quality convex polygons in the core of the domain and orthogonal layered structure near boundaries. We introduce refinement schemes for the Voronoi boundary layers, in particular near sharp corners and discuss problems related to the generalization of the suggested algorithm in 3d.