ИСТИНА

The article considers the problem of constructing a Voronoi Diagram (VD) of a polygonal figure - a polygon with polygonal holes. A planar sweeping algorithm is proposed for constructing the VD of the interior of a polygonal figure with n vertices, which has complexity O(n logn). Two factors provide a reduction in the amount of calculations and an increase in robustness compared to known solutions. This is the direct construction of only the inner part of the VD, as well as the use of the pairwise incidence property of linear segments formed by the sides of a polygonal figure. The proposed algorithm has been implemented and practically tested for polygonal figures of dimension 100 000 in studies on the analysis and recognition of handwriting. Computational experiments illustrate the robustness and efficiency of the proposed method.