Вычислительная геометрия

Вычислительная геометрия — раздел дискретной математики, в котором рассматриваются алгоритмы для решения геометрических задач.

В ней рассматриваются такие задачи как триангуляция, построение выпуклой оболочки, определение принадлежности одного объекта другому, поиск их пересечения и т. п. Оперируют с такими геометрическими объектами как: точка, отрезок, многоугольник, окружность…

Вычислительная геометрия используется в распознавании образов, машинной графике, инженерном проектировании и т. д.

Векторная алгебра

Часто используются для численных манипуляций координаты точки и вектора.

Здесь рассмотрим случай обычной декартовой системы координат.

Длина вектора <math>\overrightarrow{a}=(x,y,z)</math> обозначается <math>|\overrightarrow{a}|=\sqrt{x^2+y^2+z^2}</math>.

Для двух векторов <math>\overrightarrow{a}=(x_1,y_1,z_1)</math> и <math>\overrightarrow{b}=(x_2,y_2,z_2)</math> их сложение определяется как <math>\overrightarrow{a}+\overrightarrow{b}=(x_1+x_2,y_1+y_2,z_1+z_2)</math>.

Умножение вектора <math>\overrightarrow{a}=(x,y,z)</math> на скаляр k определяется как <math>\overrightarrow{b}=k\overrightarrow{a}=(k x, k y, kz)</math>. При этом длина вектора меняется в <math>|k|</math> раз. Если k < 0, то направление вектора меняется на противоположное.

Скалярное произведение векторов <math>\overrightarrow{a}=(x_1,y_1,z_1)</math> и <math>\overrightarrow{b}=(x_2,y_2,z_2)</math> равно <math>x_1x_2+y_1y_2+z_1z_2</math>.

Векторное произведение векторов <math>\overrightarrow{a}=(x_1,y_1)</math> и <math>\overrightarrow{b}=(x_2,y_2)</math> равно <math>\left\{y_1 z_2 - z_1 y_2,~ z_1 x_2 - x_1 z_2,~ x_1 y_2 - y_1 x_2 \right\}</math>. Это единственная операция, где уменьшение размерности пространства не сводится к простому отбрасыванию третьей координаты (замене её нулём). Обычно для двумерных векторов значением векторного произведения берут третью координату соответствующих трёхмерных векторов: <math>x_1y_2-x_2y_1</math>.

Виды многоугольников (полигонов)

Многоугольник — замкнутая кривая на плоскости, состоящая из отрезков прямых линий. Отрезки называются сторонами многоугольника, а их концы — вершинами многоугольника.

Многоугольник называется простым, если он не пересекается сам с собой.

Многоугольник называется выпуклым, если все его внутренние углы меньше или равны 180 градусам.

Цепочка вершин называется монотонной, если любая вертикальная линия пересекает её не более одного раза. Многоугольник, составленный из двух таких цепочек называется монотонным.

Алгоритмы

• Алгоритм сканирования Грэхема — трудоёмкость <math>O(n \log n)</math>.
• Алгоритм быстрой оболочки — трудоёмкость <math>O(n^2)</math>, <math>O(n log n)</math> — в среднем.
• Алгоритм Киркпатрика — построение выпуклой оболочки набора точек на плоскости методом «разделяй и властвуй» через мосты. Трудоёмкость <math>O(n \log n)</math>.
• Алгоритм заворачивания подарков (Джарвиса) — трудоёмкость <math>O(n h)</math>, <math>h</math> — количество точек в выпуклой оболочке.
• Алгоритм Чана — трудоёмкость <math>O(n\log h)</math>, <math>h</math> — количество точек в выпуклой оболочке.
• Алгоритм точки в многоугольнике — проверка принадлежности данной точки простому многоугольнику <math>O(n)</math>.
• Метод луча — принадлежность точки простому многоугольнику <math>O(n)</math>.
• Пересечение отрезков — (алгоритм Бентли-Оттманна) поиск всех точек пересечения отрезков на плоскости <math>O((n + k) \log n)</math>, <math>k</math> — количество точек пересечения.

См. также

• Алгоритмы вычислительной геометрии
• Задача о 18 точках
• Вычислительная топология

Литература

• Препарата Ф., Шеймос М. Вычислительная геометрия: Введение = Computational Geometry An introduction. — М.: Мир, 1989. — 478 с.
• Ласло М. Вычислительная геометрия и компьютерная графика на C++. — М.: БИНОМ, 1997. — 304 с.
• Скворцов А.В. Триангуляция Делоне и её применение. — Томск: Издательство Томского университета, 2002. — 128 с.
• Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн, Клифорд. Глава 33. Вычислительная геометрия // Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-e издание. — М.: «Вильямс», 2005. — С. 1047 — 1084. — ISBN 5-8459-0857-4.
• Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf. Computational Geometry: Algorithms and Applications. — Springer, 2000. — 368 с.
• David M. Mount. Computional Geometry. — University of Maryland, 2002. — 122 с.
• Elmar Langetepe, Gabriel Zachmann. Geometric Data Structures for Computer Graphics. — A K Peters, 2006. — 362 с. — ISBN 1568812353.
• Hormoz Pirzadeh. Computational Geometry with the Rotating Calipers. — McGill University, 1999. — 118 с.
• Jacob E. Goodman, Joseph O'Rourke. Handbook of Discrete and Computational Geometry. — CRC Press LLC, 1997. — 956 с.
• Jianer Chen. Computational Geometry: Methods and Applications. — Texas A&M University, 1996. — 228 с.
• Joseph O'Rourke. Computational Geometry in C. — Cambridge University Press, 1998. — 362 с.

Отрывок, характеризующий Вычислительная геометрия

Прочтя письмо, Наташа села к письменному столу, чтобы написать ответ: «Chere princesse», [Дорогая княжна,] быстро, механически написала она и остановилась. «Что ж дальше могла написать она после всего того, что было вчера? Да, да, всё это было, и теперь уж всё другое», думала она, сидя над начатым письмом. «Надо отказать ему? Неужели надо? Это ужасно!»… И чтоб не думать этих страшных мыслей, она пошла к Соне и с ней вместе стала разбирать узоры.
После обеда Наташа ушла в свою комнату, и опять взяла письмо княжны Марьи. – «Неужели всё уже кончено? подумала она. Неужели так скоро всё это случилось и уничтожило всё прежнее»! Она во всей прежней силе вспоминала свою любовь к князю Андрею и вместе с тем чувствовала, что любила Курагина. Она живо представляла себя женою князя Андрея, представляла себе столько раз повторенную ее воображением картину счастия с ним и вместе с тем, разгораясь от волнения, представляла себе все подробности своего вчерашнего свидания с Анатолем.
«Отчего же бы это не могло быть вместе? иногда, в совершенном затмении, думала она. Тогда только я бы была совсем счастлива, а теперь я должна выбрать и ни без одного из обоих я не могу быть счастлива. Одно, думала она, сказать то, что было князю Андрею или скрыть – одинаково невозможно. А с этим ничего не испорчено. Но неужели расстаться навсегда с этим счастьем любви князя Андрея, которым я жила так долго?»
– Барышня, – шопотом с таинственным видом сказала девушка, входя в комнату. – Мне один человек велел передать. Девушка подала письмо. – Только ради Христа, – говорила еще девушка, когда Наташа, не думая, механическим движением сломала печать и читала любовное письмо Анатоля, из которого она, не понимая ни слова, понимала только одно – что это письмо было от него, от того человека, которого она любит. «Да она любит, иначе разве могло бы случиться то, что случилось? Разве могло бы быть в ее руке любовное письмо от него?»
Трясущимися руками Наташа держала это страстное, любовное письмо, сочиненное для Анатоля Долоховым, и, читая его, находила в нем отголоски всего того, что ей казалось, она сама чувствовала.
«Со вчерашнего вечера участь моя решена: быть любимым вами или умереть. Мне нет другого выхода», – начиналось письмо. Потом он писал, что знает про то, что родные ее не отдадут ее ему, Анатолю, что на это есть тайные причины, которые он ей одной может открыть, но что ежели она его любит, то ей стоит сказать это слово да , и никакие силы людские не помешают их блаженству. Любовь победит всё. Он похитит и увезет ее на край света.
«Да, да, я люблю его!» думала Наташа, перечитывая в двадцатый раз письмо и отыскивая какой то особенный глубокий смысл в каждом его слове.
В этот вечер Марья Дмитриевна ехала к Архаровым и предложила барышням ехать с нею. Наташа под предлогом головной боли осталась дома.


Вернувшись поздно вечером, Соня вошла в комнату Наташи и, к удивлению своему, нашла ее не раздетою, спящею на диване. На столе подле нее лежало открытое письмо Анатоля. Соня взяла письмо и стала читать его.
Она читала и взглядывала на спящую Наташу, на лице ее отыскивая объяснения того, что она читала, и не находила его. Лицо было тихое, кроткое и счастливое. Схватившись за грудь, чтобы не задохнуться, Соня, бледная и дрожащая от страха и волнения, села на кресло и залилась слезами.
«Как я не видала ничего? Как могло это зайти так далеко? Неужели она разлюбила князя Андрея? И как могла она допустить до этого Курагина? Он обманщик и злодей, это ясно. Что будет с Nicolas, с милым, благородным Nicolas, когда он узнает про это? Так вот что значило ее взволнованное, решительное и неестественное лицо третьего дня, и вчера, и нынче, думала Соня; но не может быть, чтобы она любила его! Вероятно, не зная от кого, она распечатала это письмо. Вероятно, она оскорблена. Она не может этого сделать!»
Соня утерла слезы и подошла к Наташе, опять вглядываясь в ее лицо.
– Наташа! – сказала она чуть слышно.
Наташа проснулась и увидала Соню.
– А, вернулась?
И с решительностью и нежностью, которая бывает в минуты пробуждения, она обняла подругу, но заметив смущение на лице Сони, лицо Наташи выразило смущение и подозрительность.
– Соня, ты прочла письмо? – сказала она.
– Да, – тихо сказала Соня.
Наташа восторженно улыбнулась.
– Нет, Соня, я не могу больше! – сказала она. – Я не могу больше скрывать от тебя. Ты знаешь, мы любим друг друга!… Соня, голубчик, он пишет… Соня…
Соня, как бы не веря своим ушам, смотрела во все глаза на Наташу.
– А Болконский? – сказала она.
– Ах, Соня, ах коли бы ты могла знать, как я счастлива! – сказала Наташа. – Ты не знаешь, что такое любовь…
– Но, Наташа, неужели то всё кончено?
Наташа большими, открытыми глазами смотрела на Соню, как будто не понимая ее вопроса.
– Что ж, ты отказываешь князю Андрею? – сказала Соня.
– Ах, ты ничего не понимаешь, ты не говори глупости, ты слушай, – с мгновенной досадой сказала Наташа.
– Нет, я не могу этому верить, – повторила Соня. – Я не понимаю. Как же ты год целый любила одного человека и вдруг… Ведь ты только три раза видела его. Наташа, я тебе не верю, ты шалишь. В три дня забыть всё и так…
– Три дня, – сказала Наташа. – Мне кажется, я сто лет люблю его. Мне кажется, что я никого никогда не любила прежде его. Ты этого не можешь понять. Соня, постой, садись тут. – Наташа обняла и поцеловала ее.