В данной работе описывается простой и эффективный алгоритм, реализующий замкнутый набор булевых операций {объединение, пересечение, разность, симметрическая разность} над множествами гранично заданных многоугольников (boundary represented polygons) на плоскости. Замкнутость набора операций подразумевает корректную обработку многоугольников с самокасаниями (или кратными вершинами), т.е. результирующие многоугольники, полученные с помощью предлагаемого алгоритма, удовлетворяют предъявляемым требованиям к входным данным алгоритма. Асимптотическая оценка времени выполнения алгоритма не превышает O(n log*n + k + z log n), где n - общее число вершин многоугольников-операндов, k - число точек пересечения их рёбер, z - общее число контуров многоугольников-операндов. Таким образом, предложенный алгоритм по эффективности не уступает большинству алгоритмов, известных на сегодняшний день.
- Новости
- Институт
- Выборы директора
- Основная информация
- А.П. Ершов
- История
- Структура института
- Сотрудники
- Ученый совет
- Диссертационный совет
- Сведения об образовательной организации
- Профком ИСИ
- Адрес
- Телефонный справочник, PDF
- ИСИ СО РАН в прессе
- Международное сотрудничество
- Годовые отчеты
- Фотоархив ИСИ
- Видеоархив ИСИ
- Полезные ссылки
- Реквизиты
- Вакансии
- Документы
- Обучение
- Проекты
- Публикации
- О публикациях
- Список публикаций
- Препринты
- Авторефераты
- Сборники статей
- Книги сотрудников ИСИ
- Учебные и методические пособия
- Зарубежные публикации
- Методика определения импакт-фактора научного журнала
- Научно-популярные статьи сотрудников ИСИ в прессе
- ГОСТ Р 7.0.11-2011 - Диссертация и автореферат диссертации
- Как правильно оформлять список литературы
- Рекомендации по подготовке и оформлению статей
- Экспертизы публикаций
- Издания ИСИ
- Конференции
- Библиотека