о принадлежности точки (1)
Задача о принадлежности точки (2)
Задача о принадлежности точки (3). Построение выпуклой оболочки
Геометрические задачи возникают в программировании весьма часто. Очевидным местом возникновения таких задач является визуализация, т.е. изображение различных объектов на экране. Другие примеры менее очевидны, но не менее важны. Например, нахождение выпуклой оболочки (т.е. наименьшего выпуклого множества, содержащего данные точки) играет существенную роль в задачах поиска оптимального решения.
Задач, которые можно назвать “геометрическими”, существует немало, при этом они могут относиться к существенно разным областям программирования. В этой главе мы будем касаться только тех из них, которые относятся к “чистым алгоритмам”. Это значит, что мы никак не обсуждаем
*
низкоуровневые задачи -- мы пишем все программы на языке Pascal или C и не заботимся о скорости реальной прорисовки изображения на экране;
*
вычислительные задачи -- для них нам пока
