четверг, 14 июля 2011 г.

Нахождение точки пересечения двух отрезков

Рассмотрим алгоритм нахождения точки пересечения двух векторов. Для этого нам понадобится параметрическое уравнение отрезка.
Пусть имеется некоторый отрезок P0P1, уравнение данного отрезка будет иметь вид:
где Р0 и Р1 – начальная и конечная точки отрезка;
u = P1-P0 – вектор, показывающий направление и длину отрезка;
s – координата точки на отрезке (или прямой, содержащей данный отрезок).
При  0 <= s <= 1 мы имеем множество точек, лежащих между точками Р0 и Р1, в противном случае (s < 0 или s > 1) – мы получим все точки, лежащие на прямой, содержащей данный отрезок, но за его границами («левее» и «правее»).
Рассмотрим теперь 2 отрезка, заданных параметрическими уравнениями:
Данные отрезки будут параллельны, если
где c – некоторое число.
Вспомним теперь понятие перпендикулярного скалярного произведения – модификации скалярного произведения, в котором первый вектор заменен его левой нормалью. Важным свойством данного произведения будет его равенство нулю в случае параллельности перемножаемых векторов (вытекает из свойств обычного скалярного произведения векторов), т.е.:
Это все была необходимая вводная информация. Перейдем теперь непосредственно к нахождению точки I пересечения отрезков P(s) и Q(t).
Иллюстрация к нахождению точки пересечения двух отрезков

Проведем вектор w, соединяющий начала отрезков P(s) и Q(t) (т.е. через точки P0 и Q0):

Условием пересечения отрезков P(s) и Q(t) будет перпендикулярность векторов P(s1)-Q0 и левой нормали вектора v  (см. рисунок), т.е. равенство их скалярного произведения нулю:
где
Тогда, подставив в выражение скалярного произведения векторов данные координаты векторов, получим:

Раскрыв скобки и перегруппировав, получим:

отсюда
Выражение в числителе полученной дроби – есть перпендикулярное скалярное произведение векторов v  и w, а выражение в знаменателе – перпендикулярное скалярное произведение векторов v  и u, взятое со знаком «минус». Тогда:
Аналогично найдем значение параметра t1 для отрезка Q(t):
 Таким образом, мы нашли значения параметров s1 и t1. Координаты самой точки пересечения можно найти, подставив значения одного из параметров в соответствующее уравнение отрезка. Например:
 Но полученная таким образом точка может лежать как в границах заданных отрезков, так и за их пределами, и нам необходимо определить лежит ли данная точка в границах отрезков, или нет. Для этого нужно, чтобы выполнялись следующие условия:
 Вот и вся теория необходимая нам для данной операции. Данную статью Вы можете скачать в формате pdf здесь (более читабельна).
Краткое описание алгоритма было взято отсюда. Я его только перевел и подробно расписал.

пятница, 1 июля 2011 г.

Мой первый проект на GitHub

Давно хотел создать какой-нибудь общедоступный проект, ну и начал с самого мне необходимого – математической библиотеки, доступной здесь. Сейчас в ней только один класс, обеспечивающий работу с матрицами – теми самыми, что Вы могли встретить в курсе высшей математики в институте.
Для создания объекта-матрицы вызываем конструктор, который создает нулевую матрицу (т.е. матрицу, у которой все элементы равны нулю):
var newMatrix:MatrixMath = new MatrixMath(numRows, numCols);
где numRows – число строк, а numCols – число столбцов матрицы.
Для заполнения коэффициентов матрицы случайными числами вызываем следующий метод:
newMatrix.random(min, max);
где min и max – границы диапазона случайных чисел, которые будут заполнять матрицу.
Для задания значения конкретного элемента матрицы используйте метод:
newMatrix.setElement(row, col, value);
где row – номер строки, col – номер столбца (внимание, row и col отсчитываются от нуля), value – задаваемое значение элемента.
Есть также пара методов для задания значений всех элементов матрицы из массивов:
setMatrixFromRows(rowsVector:Vector.<Vector.<Number>>) – как видно, в качестве аргумента принимает двумерный массив элементов (число строк и столбцов матрицы рассчитывается исходя из размеров данного массива);
setMatrixFromVector(matrixVector:Vector.<Number>, numRows:uint, numCols:uint) – в качестве аргумента принимает одномерный массив, а также число строк и столбцов матрицы.
Для чтения значений элементов матрицы есть метод
getElement(row:uint, col:uint)
Основным применением данного класса является решение систем линейных уравнений. В моей реализации данного класса эту задачу можно выполнить тремя способами:
1) это решение уравнений с помощью метода Крамера. Данный метод решения наиболее ресурсоемкий и использовать его для систем более, чем с 8 неизвестными – крайне не рекомендуется (программа «повиснет»). Был реализован чисто «из спортивного интереса». Пример использования:
// Создаем матрицу, состоящую из коэффициентов при неизвестных 
// и заполняем ее случайными значениями
var testMatr1:MatrixMath = new MatrixMath(3, 3);
testMatr1.random(0, 100);
trace("A:");
// Трассируем содержимое матрицы
testMatr1.traceMatrix();
// Создаем матрицу, состоящую из свободных членов уравнений
var testMatr2:MatrixMath = new MatrixMath(3, 1);
testMatr2.random(0, 50);
trace("B:");
testMatr2.traceMatrix();
trace("Cramer Solution:");
// Создаем матрицу-столбец, содержащую решение системы уравнений
var testMatr:MatrixMath = MatrixMath.CramerSolution(testMatr1, testMatr2);
// Выводим на экран ее содержимое
trace(testMatr.m);

2) решение системы с помощью метода Гаусса:
var testMatr1:MatrixMath = new MatrixMath(3, 3);
testMatr1.random(0, 100);
trace("A:");
testMatr1.traceMatrix();
var testMatr2:MatrixMath = new MatrixMath(3, 1);
testMatr2.random(0, 50);
trace("B:");
testMatr2.traceMatrix();
trace("Gauss Solution");
// Создаем матрицу-столбец, содержащую решение системы уравнений
testMatr = MatrixMath.GaussSolution(testMatr1, testMatr2);
trace(testMatr.m);

Видим, что решение системы уравнений в первом и втором случае отличается всего лишь одной строкой, в чем же разница? Она заключается в точности вычислений. Метод Крамера очень медленный, но дает более точные результаты, т.к. при нахождении значений неизвестных в нем осуществляется лишь одна операция деления. Но метод Гаусса гораздо-гораздо быстрее и дает ответ, отличающийся лишь на миллионные доли, что является приемлемым.

3) Решение с помощью LUP-разложения позволяет быстро решать множество систем уравнений, отличающихся лишь значениями свободных членов. Данный способ отличается от метода Гаусса тем, что позволяет «запоминать» последовательность операций, необходимых для решения системы уравнений. Пример использования:
trace("LUP Solution");
var testMatr1:MatrixMath = new MatrixMath(3, 3);
testMatr1.random(0, 100);
trace("A:");
testMatr1.traceMatrix();
// Создаем т.н. матрицу перестановок, в которой хранится 
// информация о необходимых действиях
var permutationMatr:MatrixMath = new MatrixMath(testMatr1.rows, 1);
// Внимание, метод LUPDecomposition изменяет значения элементов 
// в матрицах testMatr1 и permutationMatr, поэтому, 
// если Вам необходимо сохранить исходные значения 
// элементов матриц, то используйте метод clone:
var cloneMatr:MatrixMath = testMatr1.clone();
// Выполняем необходимые преобразования матриц
MatrixMath.LUPDecomposition(cloneMatr, permutationMatr);
// Создаем матрицу, состоящую из свободных членов уравнений
var testMatr2:MatrixMath = new MatrixMath(3, 1);
testMatr2.random(0, 50);
trace("B:");
testMatr2.traceMatrix();
// Создаем матрицу-столбец, содержащую решение системы уравнений
testMatr = MatrixMath.LUPSolution(cloneMatr, testMatr1, testMatr2);
// Выводим на экран решение
trace(testMatr.m);
// Давайте теперь решим другую систему уравнений, 
// отличающуюся только значениями свободных членов
// Зададим новые значения свободных членов уравнений:
testMatr2.random(0, 100);
// Снова решаем систему уравнений, 
// используя уже преобразованные матрицы
testMatr = MatrixMath.LUPSolution(cloneMatr, testMatr1, testMatr2);
trace(testMatr.m);

Кроме методов для решения систем уравнений в данном классе реализован функционал по основным операциям над матрицами: сложение, вычитание, умножение матриц, умножение матрицы на число, транспонирование, нахождение обратной матрицы, вычисление определителя (двумя способами: с помощью метода Гаусса и с помощью рекурсии. Второй метод гораздо медленнее и более ресурсоемкий, но немного точнее), а также другие вспомогательные методы.
Названия методов в классе говорят сами за себя, плюс в коде есть комментарии (приношу извинения за свой корявый английский в них).

На сегодня – все. Надеюсь, что следующая статья будет посвящена продолжению темы векторов :)