By this author

Constructing the internal Voronoi diagram of a polygonal figure using the sweep method

Issue number 4 from 17.09.2025

В статье рассматривается задача построения внутренней диаграммы Вороного многоугольной фигуры – многоугольника с многоугольными дырами. Предлагается метод, основанный на парадигме плоского заметания. Прямое построение только внутренней части диаграммы Вороного позволяет уменьшить объем вычислений и повысить робастность по сравнению с известными решениями. Другим фактором снижения вычислительной сложности является использование свойства попарной инцидентности линейных отрезков, образованных сторонами многоугольной фигуры. Для учета этих особенностей предлагается строить структуру данных статус заметающей прямой в виде упорядоченного множества зон ответственности сайтов. Структура реализуется в виде комбинации сбалансированного дерева и двунаправленного списка. Вычислительные эксперименты иллюстрируют численную надежность и эффективность предложенного метода.

16 0