Вычислительная геометрия сложна, но интересна. И это совсем не то же, что школьная геометрия на тетради в клетку. Здесь свои задачи, проблемы и методы.

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

Очевидно, нужно найти расстояние между центрами и сравнить его с суммой радиусов:

Ха-ха:

Итак, первая отличительная черта задач вычислительной геометрии — необходимость обдумывать множество особых случаев. Подчёркиваю, множество. Я порисовал в блокноте и насчитал 6-7 «принципиально разных» вариантов расположения двух окружностей на плоскости относительно друг друга. В зависимости от задачи это число может быть больше. И это, заметьте, во всего лишь двухмерном пространстве.

Вторая отличительная черта, которую хотелось бы отметить, это совершенно иные методы решения привычных задач. Например, определение площади треугольника. Никаких тут синусов и высот: можно запутаться ещё до написания кода. Формула Герона или векторное произведение реализуются гораздо проще и обеспечивают большую точность. Есть и более общий метод определения площади простого многоугольника. Кстати, я помнил совершенно другое доказательство этой формулы. I’m fucking love maths!

Кстати, насчёт точности. Поскольку компьютер оперирует числами с ограниченной точностью, возможны такие конфузы, что два числа, которые по всем законам должны быть равными, получились не равными. Поэтому в решениях вещественные числа сравнивают не  так:

А так:

Для олимпиадных задач хватало eps=10^-6.

Ну и последнее, но не менее интересное в вычислительной геометрии — это множество задач и алгоритмов, которых нет и не может быть в «конкретной» геометрии. Например, определение принадлежности точки плоскости/отрезку/окружности/др. или нахождение выпуклой оболочки.

В общем, читать, читать и читать.

P.S. Палец вверх за иллюстрации от руки.