Русская Википедия:Вычислительная геометрия
Вычислительная геометрия — раздел информатики, в котором рассматриваются алгоритмы для решения геометрических задач.
В ней рассматриваются такие задачи как триангуляция, построение выпуклой оболочки, определение принадлежности одного объекта другому, поиск их пересечения и т. п. Оперируют с такими геометрическими объектами как: точка, отрезок, многоугольник, окружность…
Вычислительная геометрия используется в распознавании образов, машинной графике, инженерном проектировании и т. д.
Векторная алгебра
Часто используются для численных манипуляций координаты точки и вектора.
Здесь рассмотрим случай обычной декартовой системы координат.
Длина вектора <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> — количество точек пересечения.
См. также
Литература
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
Шаблон:Нет сносок Шаблон:Rewrite
