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

Question

[delkov]

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

Интересует литература по:
1) "геометрическим алгоритмам" (например алгоритм, позволяющий найти минимальную окружность описывающую массив точек).
2) проективной геометрии (где линал/квантернионы).
Например, для написания рейтрейсера.

Answer 1

[Vlad_Fedorenko]

Можете начать отсюда
algolist.manual.ru/maths/geom

Comments

[Олег Бош]

Поддерживаю. Раньше пользовался этим сайтом. Вот ещё один сборник алгоритмов alglib.sources.ru

Книгу пользовал:
Вычислительная геометрия и компьютерная графика на C++ Ласло М.
там математика не такая сложная (имхо).

Answer 2

[Сергей Протько]

2) Погуглите чего на тему "Машинная графика". Есть курсы лекций на эту тему.
1) тут точно не скажу, но очень напоминает задачки на кластеризацию. Мол находим в массиве точек центр, самую удаленную точку от него и это будет радиус окружности.

Answer 3

[Михаил Потанин]

Голованов Н. Н. "Геометрическое моделирование"
Бобенко А. И., Сурис Ю. Б. "Дискретная дифференциальная геометрия. Интегрируемая структура"

Готовьтесь к сложной математике

Answer 4

[Александр]

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

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

Comments

[delkov]

Спасибо! конкретно даный алгоритм, мне сейчас не интересен, хотелось бы именно скоп знаний.

Answer 5

[Андрюха]

https://www.edx.org/course/computer-graphics-uc-sa...
https://www.edx.org/course/computational-geometry-...
ocw.mit.edu/courses/mechanical-engineering/2-158j-...