Действительно не имеете? :) Есть вариант, предложенный Шевчуком (J. R. Shewchuk, статья). Если эта статья вам покажется привлекательной для реализации, то помните о том, что сопроцессор иногда считает в 10-байтной арифметике и это сделает алгоритм некорректным. Здесь я его описываю и комментирую, возможно, так будет проще: запись лекции.
Вообще, конечно, не хочу спойлеров, но я через две недели буду читать лекцию в cs-клубе как раз на эту тему: http://compsciclub.ru/courses/csseminar/2016-autumn/
Я готовлю для этой лекции python-notebook, он, конечно, сырой пока, но основные идеи уловить, думаю, можно: https://github.com/mcquay239/cg-lectures/blob/master/convex_hull.ipynb
Будет-будет ;) Проекция с параболоида — это звучит слишком торжественно для простого отбрасывания координаты z. Серединные перпендикуляры можно не пересекать — вершины ДВ будут центрами описанных окружностей треугольников Делоне (они, конечно, являются пересечениями соответствующих серединных перпендикуляров, я лишь обращаю внимание на то, что двойственность там действительно халявная). Ну и самый большой бонус — такая диаграмма будет работать в пространстве любой размерности.
Короткий ответ — от корней можно и нужно избавиться тождественными преобразованиями (в вашем случае это сделать довольно просто). Если чуть длиннее, то первые два фильтра, описанные в статье (floating-point и interval arithmetic), спокойно переживут корень. Однако уже из рациональных чисел корень не извлечь. Есть библиотека LEDA для работы с алгебраическими числами, она используется, например, в straight skeleton (для определения радиуса вписанной окружности, в отличие от описанной, невозможно избавиться от корней). Её, теоретически, можно использовать вместо gmp. Но, повторюсь, для вашей задачи достаточно gmp.
Проблемы с точностью вычислений решаются так: https://habrahabr.ru/post/138168/
Вообще, я удивился, увидев у вас реализацию Форчуна: вы же писали выпуклую оболочку, а диаграмма Вороного линейно сводима к выпуклой оболочке через триангуляцию Делоне. Кажется, было бы проще использовать именно выпуклую оболочку :)
Хмм, я пока не очень понял, что в этой резолюции ставит под угрозу свободу интернета. Многие пункты мне очень нравятся, например прозрачность тарифов на роуминг.
Кроме того, обсуждения проекта было открытым, но как-то слабо заинтересовало людей.
Также я не очень понимаю, почему Гугл не является членом этой организации (насколько я понял, по уставу он мог бы).
2. Алгоритм Чена (O(N log H)) — статический алгоритм на плоскости, то есть все вершины обрабатываются скопом.
Но еще раз: это все неважно для построения триангуляции Делоне с помощью выпуклых оболочек, так как все точки в любой момент времени всегда будут вершинами выпуклой оболочки.
2a. Часто в динамических и инкрементальных алгоритмах берут именно среднюю сложность, так как сложность в худшем случае сильно хуже :) Для триангуляции Делоне есть статические алгоритмы, работающие гарантированно за O(N log N). Например, построение триангуляции с использованием заметающей прямой.
Мне кажется, что для повышения уровня образования намного полезнее читать, чем писать :)
Только не воспринимайте, пожалуйста, то, что я здесь пишу, как попытку заставить вас перестать писать. Например, из комментариев к вашей статье я сам узнал кое-что новое.
Я не хотел вас обидеть: есть статья, есть критика, в чем проблема?
Нынешняя объективная реальность такова, что если вы начинаете говорить об алгоритме, то вы должны представлять, что такое вычислительная сложность, именно на это я вам и указал, со всем уважением.
Опять переход в 3D. Большинство эффективных алгоритмов триангуляции Делоне на плоскости работают в плоскости. См. комментарий выше.
1. Комментарий про N log H относился к выпуклым оболочкам вообще. Понятно, что точки, спроецированные на параболоид (да и вообще на любую выпуклую поверхность), будут вершинами выпуклой оболочки.
2. Стоп. Каких промежуточных оболочек? У меня ощущение, что вы пытаетесь построить инкрементальный алгоритм триангуляции Делоне через выпуклые оболочки. Зачем? Инкрементальный алгоритм построения выпуклой оболочки работает так: на каждом шаге у нас есть корректная триангуляция Делоне и структура для локализации очередной точки в триангуляции, позволяющая найти треугольник, содержащий точку за O(log N). Дальше серия флипов, равная, в конечном счете, степени свежедобавленной вершины. Ниже вы приводите интересный пример облома инкременальной триангуляции. И действительно, таких примеров море. Фокус в том, что первый шаг любого инкрементального алгоритма — рандомная перестановка начальных данных. Таким образом, вероятность получения именно такого порядка на конкретно ваших данных равна 1/N!.. В среднем для всех перестановок число флипов будет O(1).
У гугла есть сервис для поиска статей: scholar.google.com. Большинство статей, опубликованных в руководстве пользователя CGAL, ищутся сразу.
А зачем вы читали исходники для convex hull, если в CGAL сразу дана реализация инкрементальной триангуляции? Если вы хотите реализовать самостоятельно статический алгоритм, то проще всего построить выпуклую оболочку точек в четырехмерном пространстве QuickHull'ом. Простой для понимания и для реализации алгоритм, используется повсеместно в статических случаях.
Не стоит делать то, что уже хорошо сделано другими, как мне кажется. Посмотрите сюда. Там же, при желании, вы найдете и ссылки на соответствующие статьи.
Я готовлю для этой лекции python-notebook, он, конечно, сырой пока, но основные идеи уловить, думаю, можно: https://github.com/mcquay239/cg-lectures/blob/master/convex_hull.ipynb
Вообще, я удивился, увидев у вас реализацию Форчуна: вы же писали выпуклую оболочку, а диаграмма Вороного линейно сводима к выпуклой оболочке через триангуляцию Делоне. Кажется, было бы проще использовать именно выпуклую оболочку :)
Кроме того, обсуждения проекта было открытым, но как-то слабо заинтересовало людей.
Также я не очень понимаю, почему Гугл не является членом этой организации (насколько я понял, по уставу он мог бы).
Но еще раз: это все неважно для построения триангуляции Делоне с помощью выпуклых оболочек, так как все точки в любой момент времени всегда будут вершинами выпуклой оболочки.
2a. Часто в динамических и инкрементальных алгоритмах берут именно среднюю сложность, так как сложность в худшем случае сильно хуже :) Для триангуляции Делоне есть статические алгоритмы, работающие гарантированно за O(N log N). Например, построение триангуляции с использованием заметающей прямой.
Только не воспринимайте, пожалуйста, то, что я здесь пишу, как попытку заставить вас перестать писать. Например, из комментариев к вашей статье я сам узнал кое-что новое.
Нынешняя объективная реальность такова, что если вы начинаете говорить об алгоритме, то вы должны представлять, что такое вычислительная сложность, именно на это я вам и указал, со всем уважением.
Опять переход в 3D. Большинство эффективных алгоритмов триангуляции Делоне на плоскости работают в плоскости. См. комментарий выше.
2. Стоп. Каких промежуточных оболочек? У меня ощущение, что вы пытаетесь построить инкрементальный алгоритм триангуляции Делоне через выпуклые оболочки. Зачем? Инкрементальный алгоритм построения выпуклой оболочки работает так: на каждом шаге у нас есть корректная триангуляция Делоне и структура для локализации очередной точки в триангуляции, позволяющая найти треугольник, содержащий точку за O(log N). Дальше серия флипов, равная, в конечном счете, степени свежедобавленной вершины. Ниже вы приводите интересный пример облома инкременальной триангуляции. И действительно, таких примеров море. Фокус в том, что первый шаг любого инкрементального алгоритма — рандомная перестановка начальных данных. Таким образом, вероятность получения именно такого порядка на конкретно ваших данных равна 1/N!.. В среднем для всех перестановок число флипов будет O(1).
А зачем вы читали исходники для convex hull, если в CGAL сразу дана реализация инкрементальной триангуляции? Если вы хотите реализовать самостоятельно статический алгоритм, то проще всего построить выпуклую оболочку точек в четырехмерном пространстве QuickHull'ом. Простой для понимания и для реализации алгоритм, используется повсеместно в статических случаях.