Что почитать про геометрию в программировании?

Доброго времени суток, уважаемые!

Интересует литература по:
1) "геометрическим алгоритмам" (например алгоритм, позволяющий найти минимальную окружность описывающую массив точек).
2) проективной геометрии (где линал/квантернионы).
Например, для написания рейтрейсера.
  • Вопрос задан
  • 1096 просмотров
Пригласить эксперта
Ответы на вопрос 5
@Vlad_Fedorenko
Можете начать отсюда
algolist.manual.ru/maths/geom
Ответ написан
Fesor
@Fesor
Full-stack developer (Symfony, Angular)
2) Погуглите чего на тему "Машинная графика". Есть курсы лекций на эту тему.
1) тут точно не скажу, но очень напоминает задачки на кластеризацию. Мол находим в массиве точек центр, самую удаленную точку от него и это будет радиус окружности.
Ответ написан
@potan
Голованов Н. Н. "Геометрическое моделирование"
Бобенко А. И., Сурис Ю. Б. "Дискретная дифференциальная геометрия. Интегрируемая структура"

Готовьтесь к сложной математике
Ответ написан
@fireSparrow
Конкретно по первому вопросу:
1. Перебираем все возможные тройки точек.
2. Каждая тройка - это треугольник. Для него находим центр и радиус описанной окружности (конкретно для этой подзадачи алгоритм легко выгугливается).
3. Проверяем - находятся ли все остальные точки внутри этого треугольника, и является ли эта окружность меньше, чем ранее найденные.

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы