|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ЦЭМИ РАН |
||
ПОСТРОЕНИЕ ВНУТРЕННЕЙ ДИАГРАММЫ ВОРОНОГО МНОГОУГОЛЬНОЙ ФИГУРЫ МЕТОДОМ ЗАМЕТАНИЯстатья
Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАКСтатья опубликована в журнале из списка Web of Science и/или Scopus
- Авторы: Местецкий Л.М., Коптелов Д.А.
- Журнал: Программирование
- Номер: 4
- Год издания: 2024
- Первая страница: 13
- Последняя страница: 26
- DOI: 10.31857/S0132347424040026
- Аннотация: В статье рассматривается задача построения внутренней диаграммы Вороного многоугольной фигуры – многоугольника с многоугольными дырами. Предлагается метод, основанный на парадигме плоского заметания. Прямое построение только внутренней части диаграммы Вороного позволяет уменьшить объем вычислений и повысить робастность по сравнению с известными решениями. Другим фактором снижения вычислительной сложности является использование свойства попарной инцидентности линейных отрезков, образованных сторонами многоугольной фигуры. Для учета этих особенностей предлагается строить структуру данных статус заметающей прямой в виде упорядоченного множества зон ответственности сайтов. Структура реализуется в виде комбинации сбалансированного дерева и двунаправленного списка. Вычислительные эксперименты иллюстрируют численную надежность и эффективность предложенного метода.
- Добавил в систему: Местецкий Леонид Моисеевич