Привязка закругления

Привязочное округление — это метод аппроксимации положений сегментов линии путем создания сетки и размещения каждой точки в центре ячейки (пикселя) сетки. Метод сохраняет некоторые топологические свойства расположения отрезков.

К недостаткам относятся потенциальная интерполяция дополнительных вершин в сегментах линий (линии становятся полилиниями ), произвольная близость точки к неинцидентному ребру и произвольное количество пересечений между входными сегментами линий. Трехмерный случай хуже: многогранное подразделение сложности n становится сложностью O (n ⁴).

Существуют более совершенные алгоритмы, позволяющие справиться с некоторыми из этих проблем, например, итеративное округление с привязкой гарантирует «большое» расстояние между точками и неинцидентными краями. ^{[ 1 ]}

Алгоритм

Характеристики

Каноничность:
Эффективность; Существует ряд эффективных реализаций.

И наоборот, есть нежелательные свойства:

Неидемпотентность : повторные применения могут вызвать произвольный сдвиг точек.

Ссылки

^ Чаба Д. Тот; Джозеф О'Рурк; Джейкоб Э. Гудман (13 апреля 2004 г.). Справочник по дискретной и вычислительной геометрии, второе издание . ЦРК Пресс. стр. 552–. ISBN 978-1-4200-3531-5 .

Библиография

ЖЖ Гибас; Д.Х. Маримонт (1998). «Динамическое округление механизмов». Межд. Дж. Компьютер. Геом. Приложение . 8 (2): 157–176. дои : 10.1142/S0218195998000096 .

Внешние ссылки

Эффективное мгновенное округление с помощью целочисленной арифметики , Бинай К. Бхаттачарья и Джефф Сембер

Эта алгоритмам или структурам данных, статья, посвященная является незавершенной . Вы можете помочь Википедии, расширив ее .

[Toth_2004-1] Чаба Д. Тот; Джозеф О'Рурк; Джейкоб Э. Гудман (13 апреля 2004 г.). Справочник по дискретной и вычислительной геометрии, второе издание . ЦРК Пресс. стр. 552–. ISBN 978-1-4200-3531-5 .

[ 1 ]