Алгоритмы 2D графики

Основы математики

Положение точки $\mathbf{p}=\{p_x,\,p_y\}$ на плоскости описываем структурой {x: число, y: число }.
Вектор $\mathbf{a}=\mathbf{p}_2-\mathbf{p}_1$ направлен из точки $\mathbf{p}_1$ в точку $\mathbf{p}_2$ и соединяет их. Длина вектора равна: $$ |\mathbf{a}| = \sqrt{a^2_x+a^2_y}. $$ Два вектора перпендикулярны, если их скалярное произведение равно нулю: $$ \mathbf{a}\mathbf{b} = a_x b_x+a_x b_x = 0. $$ В частности, к вектору $\mathbf{a}=\{a_x,a_y\}$ будет перпендикулярен вектор с компонентами $\{a_y, -a_x\}$.
Косинус угла между двумя векторами равен: $$ \cos\alpha = \frac{\mathbf{a}\mathbf{b}}{|\mathbf{a}|\, |\mathbf{b}|}. $$ Отрезок характерезуется двумя точками -- положением начала $\mathbf{p}_1$ и конца $\mathbf{p}_2$. Произвольную точку $\mathbf{p}$ отрезка удобно задавать в параметрическом виде: $$ \mathbf{p} = \mathbf{p}_1 + (\mathbf{p}_2-\mathbf{p}_1)\,t \equiv \mathbf{p}_1\,(1-t) + \mathbf{p}_2 \,t, $$ где параметр $t$ пробегает значения от 0 до 1. Если $t=0$, то $\mathbf{p}=\mathbf{p}_1$, а при $t=1$ - имеем $\mathbf{p}=\mathbf{p}_2$.

Описанные ниже алгоритмы реализованы в библиотеке класса G2D (модуль g2d.js), функции которого являются статическими. Примеры использования этих алгоритмов можно изменять, хватаясь мышкой за точки. Реализации примеров см. в исходниках этого документа.

Угол между двумя прямыми

Пусть необходимо найти угол между двумя отрезками, начинающимися из одной точки. Один из способов получения угла между вектором p={x,y} и осью x -- это функция ang=Math.atan2(y,x). Возвращаемый ею угол будет в интервале $[-\pi,\pi]$. При этом ang > 0, если компонента y > 0 (так как ось y на канвасе направлена вниз, это соответствует направлению вектора вниз относительно горизонтали). Справа соответствующие углы (в градусах !) приведены рядом с концами отрезков.

Для вычисления угла между двумя векторами удобнее воспользоваться стандартной формулой $\cos\alpha = \mathbf{a}\mathbf{b}/|\mathbf{a}|\,|\mathbf{b}|$. Этот угол (в радианах) реализован функциями G2D.angle(a, b) и G2D.angleSign(a, b). Во втором случае угол имеет знак +, если b находится на канвасе по часовой стрелке от a и -, если против. По модулю, естественно, всегда получается положительны минимальный угол, даваемый функцией G2D.angle(a, b).
На канвасе справа угол переведен из радиан в градусы.

Функция G2D.getMedianVec(p1, p0, p2) даёт единичный вектор вдоль медианы треугольника p1, p0, p2 для угла из точки p0 (на канвасе он используется для получения положения текста отображения угла между отрезками).

Пересечение отрезков

Пусть один отрезок задан точками b1 и e1, а второй - точками b2 и e2. Отрезки пересекаются, если существует решение уравнения $$\mathbf{b}_1+(\mathbf{e}_1-\mathbf{b}_1)\,t_1 = \mathbf{b}_2+(\mathbf{e}_2-\mathbf{b}_2)\,t_2,$$ расписанного в компонентах (система двух уравнений). При этом параметры $t_1$ и $t_2$ должны находиться в интервале $[0,1]$. Функция G2D.intersectSegments(b1, e1, b2, e2, point) возвращает true, если отрезки пересекаются и в структуре point будет находится точка пересечения.

Отдельно стоит обрабатывать систуацию, когда отрезки не пересекаются, а имеют общие краевые точки. Учитывая возможные проблемы с округлением, для сравнения равенства точек стоит использовать функцию G2D.equiv1(a, b), которая сравнивает координаты точек с точностью до одной десятичной цифры после запятой, в отличие от функции G2D.equiv(a, b), которая требует полного совпадения.

Расстояние от точки до отрезка

Расстояние от точки $\mathbf{p}_0$ до отрезка $\mathbf{p}_1$ - $\mathbf{p}_2$ находится из следующих соображений. Пусть $\mathbf{p}$ - точка пересечения отрезка нормалью, опущенной из $\mathbf{p}_0$ на отрезок (слева - зелёная точка, а нормаль - пунктир). Тогда $\mathbf{p} = \mathbf{p}_1+(\mathbf{p}_2-\mathbf{p}_1)\,t$, где $0 < t < 1$. Так как $\mathbf{p}-\mathbf{p}_0$ (вектор вдоль нормали) перпендикулярен $\mathbf{p}_2-\mathbf{p}_1$ (вектор вдоль прямой), то $(\mathbf{p}-\mathbf{p}_0)(\mathbf{p}_2-\mathbf{p}_1)=0$, откуда находим: $$ t = \frac{(\mathbf{p}_0-\mathbf{p}_1)(\mathbf{p}_2-\mathbf{p}_1)}{(\mathbf{p}_2-\mathbf{p}_1)^2}. $$ Если $t \le 0$ или $t \ge 1$, точкой "нормали" будет один из концов отрезка. Эта формула реализована в функции G2D.fromPointToSegment(p0, p1, p2).

Выпуклость и самопересечение полигона

Полигон будет выпуклым, если все его углы одного знака. Проведем через ребро $(\mathbf{p}_i,\mathbf{p}_{i-1})$ прямую. Следующая точка $\mathbf{p}_{i+1}$ будет лежать слева или справа от этой прямой относительно направляющего вектора $\mathbf{k}=\mathbf{p}_i-\mathbf{p}_{i-1}$. Нормаль к вектору $\mathbf{k}=\{k_x,k_y\}$ равна $\mathbf{n}=\{k_y,\,-k_x\}$. С одной стороны от прямой означает, что скалярное произведение $\mathbf{n}\,(\mathbf{p}_{i+1}-\mathbf{p}_i)$ для всех вершин полигона одного знака.

Самопересечение полигона происходит, когда у него пересекаются хотя бы два отрезка. Отрезки $(\mathbf{p}_{i+1},\mathbf{p}_{i})$ и $(\mathbf{p}_{j+1},\mathbf{p}_{j})$ пересекаются, если концы одного находятся по разные стороны от прямой, проходящей через второй отрезок. Индексы $i,j$ выбираются так, чтобы протестировать все пары не смежных рёбер полигона.

Проверка выпуклости полигона проводится функцией G2D.fromPointToSegment(pnts), где pnts -- массив точек, задающих полигон (последняя точка замыкается ребром с первой). На канвасе полигон станет желтым, если окажется не выпуклым.

Проверка самопересечения полигона проводится функцией G2D.polygonGood(pnts), которая возвращает true, если полигон не имеет самопересечений. На канвасе полигон станет красным, если окажется самопересекающимся.

Точка в полигоне

Проведём из точки $\mathbf{p}$ векторы к каждой вершине полигона $\mathbf{p}_i$. Проведём из точки $\mathbf{p}$ векторы к каждой вершине полигона $\mathbf{p}_i$. Если точка находится внутри полигона, то сумма углов между этими векторами (с учётом их знаков) будет равна $2\pi$, иначе - нулю.

Функция G2D.pointInPolygon(p,pnts) возвращает true, если точка p находится внутри полигона, задаваемого массивом pnts. В противном случае возвращается false.

Функция G2D.pointToPolygon(p,pnts) возвращает ближайшую на полигоне точку к точке p. Эта функция, вместе с предыдущей, позволяет выяснить, помещается ли окружность внутрь полигона. Справа, если это происходит, окружность меняет свой цвет на синий.

Функция G2D.polygonRect(pnts) возвращает прямоугольник {x,y,w,h}, ограничивающий полигон. Для ускорения проверки попадает ли точка в полигон, стоит сначала проверять, попадает ли она в охватывающий прямоугольник.

Библиотека g2d.js

Графические функции

Векторные функции

Базовые алгоритмы

Работа с кластерами

Работа с полигонами

Математические функции ms.js