Comments 21
Почему где-то происходит сравнение с eps, которое 1e-11, где-то происходит сравнение с числом 1e-9? Всё есть в стандартной библиотеке: std::numeric_limits<double>::epsilon().
Подобные задачи решаются для целых/рациональных чисел, вообще без эпсилон. Иначе алгоритм будет разваливаться на некоторых входных данных. Это второе.
Подобные задачи решаются для целых/рациональных чисел, вообще без эпсилон.
Почти все алгоритмы можно сделать с целыми числами. Там проблема в раздутии полигона. Если препятствия нужно обходить на некотором расстоянии, то получаются иррациональные координаты.
Ну пусть он будет скругленный. Все-равно, чтобы отступить на нормаль длины 10, если сторона идет под углом 45 градусов к горизонтальной оси, надо будет отступать на 10/sqrt(2) по каждой координате. Сама сторона раздутого многоугольника не пройдет ни через одну рациональную точку. Будь там окружность между этими сторонами, или описанная вокруг нее ломанная из 3-х сегментов, как у меня в коде.
А координаты отрезка откуда берутся? Если это, допустим, касательная между началом пути и скругленным раздутым полигоном?
На самом деле, вы правы. Если раздувать полигоны не окружностью, а квадратом, или восьмиугольником то все координаты будут целые. Ну, будет бот двигаться чуть дальше от наклонных сторон. Бонусом количество вершин будет не удваиваться, а увеличится лишь на 4-8.
Обязательно перепишу так.
неоднократно обсуждался. То, как это делается, можно посмотреть, например, в
книжке Форсайта, Малькольма и Моулера «Машинные методы математических вычислений» издательства МИР аж от 1980 г.
Его построение и построение касательных к выпуклому многоугольнику из точки за логарифм обсуждается во многих курсах и книгах по вычислительной геометрии.
Вы неплохо продвинулись, рекомендую вам познакомится с темой поближе. Там ещё много вкусного!
Обратите внимание на сравнения с eps — так правильно сравнивать вещественные числа, чтобы ошибки округления не ломали алгоритм
Что-то мне ваш подход кажется подозрительным. При написании этого кода:
if (dir1 < eps && dir2 < -eps) { res.first = i; }
Вы с чем изначально хотели сравнивать значения dir1 и dir2, с нулём? То есть, знак проверять?
В реализациях численных алгоритмов так не делается. Реальная ошибка округления может быть много больше или меньше eps, в зависимости от того, какие вычисления и над какими числами проводились. Введение порога «eps» для сравнения с нулём ничем не оправдано и может только усугубить погрешность, если она имеет тот же знак, что и ваша поправка «eps».
Можете расписать подробнее ход ваших рассуждений при написании этого кода?
Да, это сравнения с нулями.
Логика такая: если входные числа не слишком большие, то точка не может лежать сколь угодно близко к прямой — на какой-то минимальный угол она от нее отклоняется. Поэтому, если бы точность была бесконечной, то мы получили бы 0 для точек на прямой, и, допустим, 1e-4 в худшем случае для точки не лежащей на прямой.
Но из-за погрешностей мы можем получить не 0, а 1e-11. А вместо 1e-4, 0.999999e-4. Поэтому, если мы хотим понять, когда значение <=0, нужно сравнивать с чем-то больше 0, достаточно большим, чтобы перекрыть возможную погрешность и достаточно маленьким, чтобы не перекрыть минимальный зазор между идеально точными значениями.
По идее, как мне уже указали, епсилон надо подбирать исследуя входные данные. Но это слишком сложно, да и не возможно в этом случае — фиг его знает, какие на самом деле будут входные данные. Поэтому оно выбирается эмпирически. Еще может быть такой неприятный случай, когда погрешность больше минимального зазора (если входные данные слишком большие). Но тут уже ничего не поможет, кроме вычисления в рациональных числах или длинной арифметики.
www.cs.cmu.edu/~quake/robust.html
Она решит все ваши вопросы с точностью.
В том числе и пропадет нужда в странной логике вида: для точного эпсилона надо исследовать входные данные, но это сложно, поэтому влепим от балды.
А вот очень хорошая лекция по теме точности вычислений в подобных задачах:
cw.fel.cvut.cz/wiki/_media/courses/cg/lectures/01-intro.pdf
Но тут я использую термин не из матанализа с таким же названием. В моем случае касательная к полигону — это прямая, пересекающая его ровно в одной точке, или проходящая через сторону.
Для этого в матане тоже есть термин)
Опорная гиперплоскость
Быстрый поиск касательных и пересечений у выпуклых многоугольников