Я хочу решить проблемы геометрии в конкурсах онлайн-программирования. Но всякий раз, когда я их читаю, я просто нахожу слишком сложным. Пожалуйста, предложите несколько книг и ресурсов, которые я могу изучить в вычислительной геометрии.
Где изучать вычислительную геометрию?
Ответ 1
Классическая работа: Вычислительная геометрия в C.
И также: http://www.cs.uu.nl/geobook/.
Ответ 2
Чтобы быстро решить основные задачи геометрии, чтобы они работали в течение времени конкурса, вам нужно убедиться, что у вас есть сильное понимание алгоритмов написания.
На этой странице есть несколько полезных советов о том, как стать лучше. Он настроен как двухмесячный курс чтения.
Ответ 3
Вы можете попробовать архив проблем на TopCoder.
Но сначала вы должны зарегистрироваться.
На фильтре выберите:
Категория: Геометрия
Раздел II Уровень: Уровень один или Уровень 2.
Почти все проблемы имеют описание решений.
Они довольно просты в сравнении, вы выбираете случайную геометрическую проблему из какого-либо архива конкурса.
На странице вы также можете найти множество руководств, включая геометрические.
Ответ 4
Я рекомендую две книги (среди прочих):
- Руководство по разработке алгоритмов Стивена С. Шиена - обсуждает алгоритмы в целом, но имеет много полезной информации о вычислительной геометрии
- Вычислительная геометрия: алгоритмы и приложения
Ответ 5
Если вы хотите очистить свои основы, это хорошая отправная точка - https://www.hackerearth.com/notes/computational-geometry-i-1/. В статье также есть некоторые проблемы с практикой.
Вы также должны прочитать эту статью - http://www.toptal.com/python/computational-geometry-in-python-from-theory-to-implementation, которая охватывает некоторые расширенные концепции.
Ответ 6
Вот две отличные книги, я использовал их как учебники в университете:
-
JD Foley, A van Dam et al. Введение в компьютерную графику. Addison-Wesley, 1994, ISBN 0-201-60921-5.
-
Д Хирн и М. П. Бейкер. Компьютерная графика с Open GL (3-е издание). Prentice-Hall, 2004, ISBN 0-13-120238-3.
Ответ 7
Вы должны знать выпуклый корпус и точку в полигоне. Часто пользователи TopCoder создают многоразовую библиотеку для приложений геометрии, так как тот же код используется много раз.
Запустите учебник lbackstrom для начала. Computional Geometry by Berg, Cheong, van Kreveld, Overmars [edit: уже упоминалось Bart] может быть больше, чем вам нужно.
Ответ 8
И, конечно же, есть вычислительная геометрия - введение Препарата и Шамоса. Я владею им и рекомендую для ознакомления с принципами. Хотя на самом деле это не словарь кода.