Последние несколько недель я работал над реализацией алгоритма Форчуна на C++. Этот алгоритм берёт множество 2D-точек и строит из них диаграмму Вороного. Если вы не знаете, что такое диаграмма Вороного, то взгляните на рисунок: Для каждой входной точки, которая называется «местом»…
Приветствую, уважаемые читатели данной статьи! В статье я дам описание имплементации алгоритма Форчуна (англ. Fortune's algorithm) для построения диаграммы Вороного (англ. Voronoi diagram) с использованием нативных сбалансированных двоичных деревьев поиска (для уникальных элементов) (англ. BST, binary search tree), предусмотренных стандартом C++, — ассоциативных упорядоченных контейнеров std::map и std::set. Читать дальше →
Рассматривается новый алгоритм коррекции геометрических искажений, вносимых объективом "рыбий глаз" в изображения и видео. Этот алгоритм позволяет осуществлять более точную коррекцию дисторсии при меньших потерях информации на краях изображений и видеокадров по сравнению с широко распространенным методом Brown-Conrady.Алгоритм разработан при реализации одного из проектов компании Оксаджайл (Oxagile) Читать далее
Недавно, на хабрахабре была опубликована статья, целиком и полностью посвященная диаграммам Вороного. В статье автор подробно описывает алгоритм Форчуна, применяемый для построения Диаграммы Вороного за O(n*log(n)). Стоит отметить, что описание этого алгоритма не раз появлялось в…