Трехмерное вращение

Трехмерное изменение масштаба.

Рассмотрим частичное изменение масштаба. Оно реализуется следующим образом:

S(Sx,Sy,Sz) =

т. е. [ x,y,z, 1] *S(Sx,Sy,Sz)= [ Sx*x,Sy*y,Sz*z, 1].

Общее изменение масштаба получается за счет 4-го диагонального элемента, т. е.

[ x y z 1] *

= [ x y z S ] = [ x* y* z* 1] = [ ].

Такой же результат можно получить при равных коэффициентах частичных изменений масштабов. В этом случае матрица преобразования такова:

S =

Трехмерный сдвиг

Недиагональные элементы матрицы 3´3 осуществляют сдвиг в трех измерениях, т. е.

[ x y z 1] *

=[ x+yd+hz, bx+y+iz, cx+fy+z, 1].

Трехмерное вращение

Двухмерный поворот, рассмотренный ранее, является в то же время трехмерным поворотом вокруг оси Z. В трехмерном пространстве поворот вокруг оси Z описывается матрицей

Rz ()=

Матрица поворота вокруг оси X имеет вид

Rx ()=

Матрица поворота вокруг оси Y имеет вид

Ry ()=

Результатом произвольной последовательности поворотов вокруг осей x, y, z является матрица

A =

Подматрицу 3´3 называют ортогональной, так как ее столбцы являются взаимно ортогональными единичными векторами.

Матрицы поворота сохраняют длину и углы, а матрицы масштабирования и сдвига нет.

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

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

Содержание

[убрать]

· 1 Метод трассировки луча

o 1.1 Учёт числа пересечений

o 1.2 Учёт числа оборотов

· 2 Метод суммирования углов

· 3 Алгоритмы c предобработкой

o 3.1 Выпуклые и звёздные многоугольники

o 3.2 Произвольный многоугольник

· 4 Примечания

· 5 Литература

· 6 Ссылки

Метод трассировки луча[править | править исходный текст]

Учёт числа пересечений[править | править исходный текст]

Методы работают по-разному для многоугольников с самопересекающейся границей. Слева: even-odd rule. Справа: nonzero winding rule.

Один из стандартных методов определения принадлежности точки произвольному простому многоугольнику заключается в следующем. Выпустим луч из данной точки в произвольном направлении (например в положительном направлении горизонтальной оси), и посчитаем сколько раз луч пересекает рёбра многоугольника. Для этого достаточно пройтись в цикле по рёбрам многоугольника и определить, пересекает ли луч каждое ребро. Если число пересечений нечётно, то объявляется, что точка лежит внутри многоугольника, если чётно — то снаружи. Это основано на том простом наблюдении, что при движении по лучу с каждым пересечением границы точка попеременно оказывается то внутри, то снаружи многоугольника. Алгоритм известен под такими названиями, как crossing number (count) algorithm или even-odd rule.

В алгоритме возникает затруднение в вырожденном случае, когда луч пересекает вершину многоугольника. Один из приёмов для его преодоления заключается в том, чтобы считать, что такие вершины многоугольника лежат на бесконечно малую величину выше (или ниже) прямой луча, и стало быть пересечения на самом деле и нет.^[1] Таким образом, пересечение луча с ребром засчитывается, если один из концов ребра лежит строго ниже луча, а другой конец — выше или лежит на луче.

Алгоритм работает за время O(N) для N -угольника.

Учёт числа оборотов[править | править исходный текст]

Кривая делает два оборота вокруг данной точки.

Рассмотрим число оборотов, которое делает ориентированная граница многоугольника вокруг данной точки P. В алгебраической топологии это число называется winding number. ^[2] Оно может быть вычислено следующим образом. Как и раньше, выпустим луч из P в произвольном направлении и рассмотрим рёбра, которые он пересекает. Каждому пересечению присвоим число +1 или -1, в зависимости от того, как ребро пересекает луч — по часовой (слева направо) или против часовой стрелки (справа налево). Эти два случая можно различить по знаку скалярного произведения между направляющим вектором ребра и нормалью к направляющему вектору луча.^[3] Сумма полученных величин и есть winding number. Сумма будет положительной или отрицательной, в зависимости от ориентации границы. Если она не равна нулю, то будем считать, что точка лежит внутри многоугольника, иначе — снаружи.

Такой алгоритм известен под названием nonzero winding rule. ^[3]

Для простых многоугольников этот метод работает так же, как и метод, основанный на подсчёте числа пересечений. Разница между ними проявляется при рассмотрении многоугольников с самопересекающейся границей.

Метод суммирования углов[править | править исходный текст]

Можно определить, что точка P находится внутри многоугольника c вершинами V ₀, V ₁,..., V_n = V ₀, вычислив сумму:

,

где — угол (в радианах и со знаком) между лучами PV_{i - 1} и PV_i, т.е.:

Можно доказать, что эта сумма есть не что иное, как winding number точки P относительно границы многоугольника, с точностью до константного множителя . Поэтому можно считать, что точка лежит снаружи многоугольника, если сумма равна нулю (или достаточно близка к нему, если используется приближённая арифметика). Однако данный метод весьма непрактичен, так как требует вычисления дорогостоящих операций для каждого ребра (обратных тригонометрических функций, квадратных корней, деления), и был даже назван «худшим в мире алгоритмом» для данной задачи.^[1]

К. Вейлером был предложен практичный вариант этого метода, избегающий дорогостоящих операций и приближенных вычислений.^[4] Было показано, что сумму углов можно вычислить, используя лишь операцию классификации точки многоугольника по квадрантам относительно точки P. Алгоритм Вейлера и некоторые улучшения к нему описываются в ^[5].

Алгоритм Уайлера — Атертона (Вейлера — Азертона, Weiler–Atherton) используется в компьютерной графике для клиппинга (нахождения области пересечения) отсекаемого многоугольника по отсекающему многоугольнику, также называемому окном. Отсекаемый и отсекающий многоугольники могут быть невыпуклыми. Алгоритм применим только для плоских фигур.

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

Алгоритм может быть модифицирован для объединения двух многоугольников.

Алгоритм[править | править исходный текст]

· Из координат вершин многоугольников A и B составляются два списка.

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

· В оба списка добавляются точки пересечения многоугольников; между совпадающими точками в разных списках устанавливаются двусторонние связи.

· Если ни одного пересечения не найдено, возникает одна из следующих ситуаций:

· A внутри B — вернуть A при отсечении, B при объединении.

· B внутри A — вернуть B при отсечении, A при объединении.

· A и B не пересекаются — вернуть пустое множество при отсечении, A&B при объединении.

· Составляется список точек пересечения, в которых граница многоугольника A при обходе входит в многоугольник B. Следуя из каждой такой точки по часовой стрелке вдоль границ обоих многоугольников A и B, можно найти множество областей пересечения. В случае, когда A и B выпуклы, многоугольник пересечения только один. Таким же образом можно найти и объединение многоугольников, в этом случае обход нужно начинать с выходных точек.

Проективное преобразование — это преобразование проективной плоскости, переводящее прямые в прямые.

Содержание

[убрать]

· 1 Определение

· 2 Свойства

· 3 Инволюция

· 4 Коллинеация

· 5 Перспектива

· 6 Гомология

· 7 Литература

· 8 См. также

Определение[править | править исходный текст]

Проективное преобразование — это взаимно-однозначное отображение проективного пространства на себя, сохраняющее отношение порядка частично упорядоченного множества всех подпространств.

Проективное преобразование прямой — биективное преобразование прямой, переводящее гармоническую четверку точек в гармоническую четверку точек.

Проективное преобразование плоскости — это взаимно-однозначное отображение проективной плоскости на себя, при котором для любой прямой образ также является прямой.

Свойства[править | править исходный текст]

· Проективное преобразование сохраняет двойное отношение.

· Проективное преобразование является взаимно однозначным отображением множества точек проективной плоскости, а также является взаимно однозначным отображением множества лучей пучка с центром P.

· Отображение, обратное проективному, является проективным отображением. Композиция проективных отображений является проективным. То есть множество проективных отображений образует группу.

· Центральное проектирование — частный случай проективного преобразования.

· Аффинное преобразование является частным случаем проективного.

· Каждая прямая плоскости при проективном преобразовании плоскости отображается проективно на некоторую прямую. Каждый пучок лучей плоскости проективно отображается на пучок лучей.

· Проективное преобразование плоскости определяется заданием четырёх пар соответствующих по отображению точек, причем никакие три точки из четверки образов или прообразов не лежат на одной прямой. При нетождественном отображении число неподвижных точек не более трех.

· Каждое проективное преобразование плоскости является обратимым линейным преобразованием соответствующего ей трёхмерного пространства. В однородных координатах оно представляется уравнениями:

причем .

Инволюция[править | править исходный текст]

Проективное преобразование называется инволюцией, если для любой точки P верно, что .

Если — инволюция, то .

Если проективное преобразование прямой имеет хотя бы одну такую точку P, что , то — инволюция.

Если нетождественная инволюция проективной прямой имеет неподвижные точки, то их число равно либо двум, либо нулю. Инволюция, имеющая 2 неподвижные точки, называется гиперболической. Инволюция, не имеющая неподвижных точек, называется эллиптической.

Инволюция определяется заданием двух пар соответствующих точек.

Коллинеация[править | править исходный текст]

Коллинеацией называется проективное преобразование, переводящее точки в точки, прямые в прямые и сохраняющее отношение инцидентности точек и прямых, а также двойное отношение любой четверки коллинеарных точек точек. Коллинеации образуют группу. Требование сохранения двойного отношения четверки коллинеарных точек избыточно, но это сложно доказывается. Коллинеации рассматривают вместе с корреляциями, проективными преобразованиями, переводящими точки в прямые, а прямые в точки.

Перспектива[править | править исходный текст]

Пусть на проективной плоскости имеются 2 различные прямые и не принадлежащая им точка S. Преобразование проективной плоскости называется перспективой, если и для любюй точки точки коллинеарны.

Перспективное отображение биективно, сохраняет точку пересечения прямых и сохраняет двойное отношение четверки точек.

Гомология[править | править исходный текст]

Гомологией называется нетождественная коллинеация, для которой существует поточечно неподвижная прямая p, называемая осью гомологии.

Для всякой гомологии существует неподвижная точка P (центр гомологии), обладающая тем свойством, что всякая инцидентная ей прямая неподвижна. Кроме центра P и точек оси p гомология неподвижных точек не имеет. Если , то гомология называется параболической, иначе — гиперболической.

При гомологии плоскости точка и её образ лежат на одной прямой с центром гомологии, а прямая и её образ пересекаются на оси гомологии.

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

Инволюционная гомология имеет константу гомологии равную −1.

Дата добавления: 2015-12-08