Comments 32
Ранее, в опубликованных здесь другими авторами статьях ((1), (2), (3)), уже было приведено описание алгоритма Форчуна и некоторых структур данных, которые используются для его реализации
Вы, к слову, указываете третьей ссылкой на одну из моих статей, но она не посвящена алгоритму Форчуна или его реализации. В статье рассказываю о совершенно ином алгоритме, но с той же асимптотикой — O(n*logN)
Сложности нужных операций для этих контейнеров(std::map, std::set) те же самые, что и для std::priority_queue, но они позволяют удалить не только наибольший/наименьший элемент, но и любой другой (по итератору — за O(1) времени)
А разве удаление и вставка именно в эти контейнеры осуществляется не за O(logN), это ведь самобалансирующиеся деревья?
Говоря о погрешностях вычислений, порекомендую почитать вот эту статью на Хабрахабре:
https://habrahabr.ru/post/266023/
Я, правда, данный метод встречал уже где-то — но ссылку так просто не найду.
Говоря о статье в целом, было бы интересно узнать о том, на сколько хорошо параллелится данный алгоритм(вот 'разделяй и властвуй' о котором писал я, делает это на все 100% отлично). Ну и так далее, если коротко, то было бы интереснее читать о том, о чем еще не писали: о том, что имеет некий сверх интерес.
В целом, статья хорошая, да и труд был большой вложен, за что вам и спасибо :)
Удалил ссылку.
Так и написал, что "те же самые" сложности, то есть везде логарифмические. Однако позволяют удалять элементы и из середины. Причём удаление по итератору — за константное время.
Не вижу вообще точки, где его можно распараллелить. Ни единой. Если конечно не иметь в арсенале операцию сшивки из алгоритма разделяй и властвуй.
И вам спасибо за доброе слово.
Реализую алгоритм "разделяй и властвуй" — сравню по скорости. Пока нет референтной имплементации на руках.
Вообще, я удивился, увидев у вас реализацию Форчуна: вы же писали выпуклую оболочку, а диаграмма Вороного линейно сводима к выпуклой оболочке через триангуляцию Делоне. Кажется, было бы проще использовать именно выпуклую оболочку :)
Как раз только что прочитал вашу статью. Я не уверен, что для плоского случая быстрее будет делать преобразования стартуя с выпуклой оболочки (проекция с D3 параболоида, потом пересекать серединные перпендикуляры и т.п.).
Я готовлю для этой лекции python-notebook, он, конечно, сырой пока, но основные идеи уловить, думаю, можно: https://github.com/mcquay239/cg-lectures/blob/master/convex_hull.ipynb
Подскажите, как будет корень квадратный влиять на эпсилон?
Я настоял на эпсилон именно потому, что не имею возможности сделать такую цепочку из фильтров. Именно корректность существующего подхода хотел бы "улучшить".
В CGAL видел классы алгебраических чисел (на сколько я понимаю, это сочетание символьных вычислений и интервальных). Так вот там были классы с корнями и не более того. Если мне нужны логарифмы, экспоненты и вообще трансцендентные числа, то не помогут мне алгебраические таких классов? Хотя вряд ли в геометрических приложениях такое встречается.
Алгоритм Форчуна на C++ для построения диаграммы Вороного на плоскости