| Курс
|
Курс 1
Глава Z
Простые геометрические задачи. Задача о принадлежности точки (1)
Задача о принадлежности точки (2)
Задача о принадлежности точки (3). Построение выпуклой оболочки
В занятии G1 мы обсудили алгоритм, отвечающий на вопрос, лежит ли данная точка Aвнутри данного простого многоугольника B1B2...BN? Этот алгоритм работал за время O(N). Долго это, или нет, - зависит от конкретной задачи, т.е. от того, чему равно число N, и от того, как часто нужно решать названный вопрос.
В этот раз мы обсудим такую ситуацию: нам очень часто нужно решать вопрос о принадлежности точки, при этом точка A меняется, а многоугольник остается неизменным. Мы даже усложним немного задачу: порядок следования вершин многоугольника неизвестен. Оказывается, что в такой постановке, по крайней мере, для вполне разумных частных случаев, задача имеет решение, которое состоит из 2 частей.
*
Предварительная обработка. Данные, связанные с многоугольником, записываются в более удобном
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
