Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[262]

35.1 (а) Векторное произведение векторов р\ н Р2 - это площадь параллелограмма (с учётом знака). (Ь) Вектора в светлой части плоскости получаются из вектора р поворотом по часовой стрелке, в тёмной - против.

произведением (cross product) р\ хр2 можно понимать площадь параллелограмма (с учётом знака), образованного точками (0, 0), р\, Р2, Pi + Р2 = (х1 + х2, Vi + Уг)• Для вычислений более удобно определение векторного произведения как определителя матрицы

(Вообще говоря, векторное произведение определяется для векторов в трёхмерном пространстве как вектор, перпендикулярный р\ и образующий вместе с этими векторами правую тройку, длина которого равна площади параллелограмма, образованного точками (0, 0), pi, Р2, Pi+P2- Но в этой главе нам достаточно определения векторного произведения на плоскости по формуле Х1У2 - Х2У1)

Если р\ X Р2 положительно, то кратчайший поворот р2 относительно (0, 0), совмещающий его с р\, происходит по часовой стрелке, а если отрицательно, то - против. На рис. 35.1 (Ь) вектора в светлой части плоскости получаются из вектора р поворотом по часовой стрелке, в тёмной - против. Граница этих областей состоит из векторов, векторное произведение которых с р равно нулю. Эти векторы лежат на одной прямой с р.

Напишем формулу, позволяющую определить, в какую сторону надо поворачивать popl вокругрсь чтобы наложить его на рор\ (по часовой стрелке или против). Считая началом координат точку ро, мы получаем два вектора р\ - ро = (х\ - хо, у\ - уо) н р2 - ро = (х2 - хо,у2 - Уо). Их векторное произведение равно

{Pi ~ Ро) X (р2 - Ро) = {Xl ~ Х0)(У2 - Уо) - (Ж2 - Х0){У1 ~ Уо)

Если оно положительно, то вращать надо против часовой стрелки («в положительном направлении», как говорят), если отрицательно - то по часовой стрелке. Направление поворота.

Перейдём ко второму вопросу: в какую сторону мы поворачиваем (в точке pi), двигаясь по ломаной Р0Р1Р2? Легко избежать вычисления угла ZpoPiP2j вновь воспользовавшись векторным произведением. Как видно из рис. 35.2, нам надо выяснить, в каком направлении надо поворачивать вектор popl, чтобы он стал направленным в сторону рор\. Для этого мы вычислим векторное произведение (р2- Ро) X (р\-ро). Если оно отрицательно, торор\ находится против часовой стрелки от poPi, и в точке ро мы поворачиваем


35.2 Векторное произведение помогает определить, в какую сторону мы поворачиваем в точке pi, идя по ломаной роР\р2. Для этого надо выяснить, в какой стороне находится вектор рор\ от вектора popt. (а) Если против часовой стрелки, то мы поворачиваем налево. (Ь) Если по часовой стрелке, то - направо.

налево. Если векторное произведение положительно, мы поворачиваем направо. Наконец, если оно равно нулю, то мы либо идём прямо, либо поворачиваем кругом (точки po,Pi и р2 принадлежат одной прямой).

Пересекаются ли отрезки?

Определять, пересекаются ли отрезки, мы будем в два этапа. Начальный тест (quick rejection) состоит в следующем: если ограничивающие прямоугольники отрезков не имеют общих точек, то и сами отрезки не пересекаются. При этом ограничивающим прямоугольником (bounding box) геометрической фигуры мы будем называть наименьший из прямоугольников со сторонами, параллельными осям координат, которые содержат данную фигуру.

Для отрезка р\р2 таковым будет прямоугольник (pi,p2) с левым нижним углом pi = (£i,yi) и правым верхним углом р2 = (х2,у2) , где х\ = min(xi, х2), у\ = min(yi, у2), х2 = max(xi, х2), у2 = max(yi, у2). Условие пересечения двух прямоугольников, заданных левыми нижними и правыми верхними углами, таково: (pi,p2) и (рз,р4) имеют общие точки тогда и только тогда, когда

(ж2 ж3) Л (ж4 ii) Л (у2 Уз) Л (у4 yi)

(первые два условия соответствуют пересечению ж-проекций, вторые - у-проекциям).

Если на первом этапе не удается установить, что отрезки не пересекаются, мы переходим ко второму этапу и проверяем, пересекается ли каждый из данных отрезков с прямой, содержащей другой отрезок. Отрезок пересекает прямую (straddles a line), если его концы лежат по разные стороны от неё или если один из концов лежит на прямой. Можно проверить, что два отрезка пересекаются тогда и только тогда, когда пересекаются ограничивающие их прямоугольники (начальный тест) и, кроме того, каждый из отрезков пересекается с прямой, содержащей другой отрезок.

Последнее условие проверяется с помощью векторных произведений. Точки рз и р4 лежат по разные стороны от прямой Р1Р2, если векторы рТрз и pTpt имеют различную ориентацию относительно вектора рТр (см- рис.35.3 (а), (Ь)), то есть если знаки векторных произведений (рз - pi) X (р2 - pi) и (р4 - pi) X (р2 - pi) различны. Если одно из этих векторных произведений равно нулю, то одна из точек рз или р4 принадлежит прямой Р1Р2. Два таких случая показаны на рисунках (рис. 35.3 (c),(d)). В обоих случаях отрезки пересекаются, однако возможен и другой случай: хотя отрезки


ВНИМАНИЕ!!! Рисунок, требующий добавлений. В книге есть ошибка, и после её исправления рисунок, называвшийся (е), называется (f), а на его месте надо поместить новый (см. на полях оригинала) Пересекает ли отрезок рзЩ прямую, содержащую отрезок Р1Р2? (а) Если да, то векторные произведения (рз - р\) X (р2 - Р\) и (р4 - р\) X (р2 - Р\) имеют разные знаки. (Ь) Если нет, то эти произведения имеют один и тот же знак, (c)-(d) Граничные случаи, когда одно из векторных произведений равно нулю (и отрезок пересекает прямую), (е) Одно из векторных произведений равно нулю, ограничивающие прямоугольники пересекаются, но отрезки всё-таки не пересекаются (отрезок Р1Р2 не пересекает прямую Р3Р4) (f) Отрезки лежат на одной прямой, но не пересекаются. Каждый из отрезков пересекает прямую, содержащую другой. Но сами отрезки не пересекаются - здесь это не страшно, так как этот случай отброшен на первом этапе.

проходят начальный тест и векторное произведение равно нулю, всё-таки пересечения нет (рис. 35.3 (е)) Поэтому условие «отрезок пересекает прямую» надо проверять для обоих отрезков. Заметим, что начальный тест нельзя опустить: на рис. 35.3 (f) каждый из отрезков пересекает прямую, содержащую другой (лежит на ней - мы считаем это пересечением), но сами отрезки не пересекаются.

Если один из отрезков, например, Р1Р2, равен нулю, то вопрос о том, пересекает ли отрезок рзр! прямую Р1Р2, лишён смысла (прямых много). Тем не менее можно вычислить векторные произведения (р3 - р\) X (р2 - Р\) и (р4 - pi) X (р2 - Pi), которые в данном случае равны нулю. Наш критерий пересечения применим и в этом случае, если условно принять, что рзЩ пересекает прямую р\Р2-

Итак, критерий таков: отрезки Р1Р2 и рзр4 пересекаются тогда и только тогда, когда одновременно выполнены три условия:

(а) пересекаются ограничивающие их прямоугольники;

(Ъ)

[(РЗ - Pi) X (р2 ~ Pi)] • [(р4 - Pi) X (р2 ~ Pi)] О

(с)

[(Pi - Рз) X (р4 - Рз)] • [(Р2 - Рз) X (р4 - Рз)] О

Другие применения векторного произведения.

Векторное произведение понадобится нам ещё не раз. В разделе 35.3 с его помощью мы будем сортировать точки по полярному углу относительно данного центра (см. упр. 35.1-2). В разделе 35.2 при построении красно-чёрного дерева отрезков, упорядоченных по месту их пересечения с данной вертикалью, мы будем использовать формулу с векторным произведением, чтобы определить, какой из двух отрезков пересекает эту вертикаль в более высокой точке.

Упражнения



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13] [стр.14] [стр.15] [стр.16] [стр.17] [стр.18] [стр.19] [стр.20] [стр.21] [стр.22] [стр.23] [стр.24] [стр.25] [стр.26] [стр.27] [стр.28] [стр.29] [стр.30] [стр.31] [стр.32] [стр.33] [стр.34] [стр.35] [стр.36] [стр.37] [стр.38] [стр.39] [стр.40] [стр.41] [стр.42] [стр.43] [стр.44] [стр.45] [стр.46] [стр.47] [стр.48] [стр.49] [стр.50] [стр.51] [стр.52] [стр.53] [стр.54] [стр.55] [стр.56] [стр.57] [стр.58] [стр.59] [стр.60] [стр.61] [стр.62] [стр.63] [стр.64] [стр.65] [стр.66] [стр.67] [стр.68] [стр.69] [стр.70] [стр.71] [стр.72] [стр.73] [стр.74] [стр.75] [стр.76] [стр.77] [стр.78] [стр.79] [стр.80] [стр.81] [стр.82] [стр.83] [стр.84] [стр.85] [стр.86] [стр.87] [стр.88] [стр.89] [стр.90] [стр.91] [стр.92] [стр.93] [стр.94] [стр.95] [стр.96] [стр.97] [стр.98] [стр.99] [стр.100] [стр.101] [стр.102] [стр.103] [стр.104] [стр.105] [стр.106] [стр.107] [стр.108] [стр.109] [стр.110] [стр.111] [стр.112] [стр.113] [стр.114] [стр.115] [стр.116] [стр.117] [стр.118] [стр.119] [стр.120] [стр.121] [стр.122] [стр.123] [стр.124] [стр.125] [стр.126] [стр.127] [стр.128] [стр.129] [стр.130] [стр.131] [стр.132] [стр.133] [стр.134] [стр.135] [стр.136] [стр.137] [стр.138] [стр.139] [стр.140] [стр.141] [стр.142] [стр.143] [стр.144] [стр.145] [стр.146] [стр.147] [стр.148] [стр.149] [стр.150] [стр.151] [стр.152] [стр.153] [стр.154] [стр.155] [стр.156] [стр.157] [стр.158] [стр.159] [стр.160] [стр.161] [стр.162] [стр.163] [стр.164] [стр.165] [стр.166] [стр.167] [стр.168] [стр.169] [стр.170] [стр.171] [стр.172] [стр.173] [стр.174] [стр.175] [стр.176] [стр.177] [стр.178] [стр.179] [стр.180] [стр.181] [стр.182] [стр.183] [стр.184] [стр.185] [стр.186] [стр.187] [стр.188] [стр.189] [стр.190] [стр.191] [стр.192] [стр.193] [стр.194] [стр.195] [стр.196] [стр.197] [стр.198] [стр.199] [стр.200] [стр.201] [стр.202] [стр.203] [стр.204] [стр.205] [стр.206] [стр.207] [стр.208] [стр.209] [стр.210] [стр.211] [стр.212] [стр.213] [стр.214] [стр.215] [стр.216] [стр.217] [стр.218] [стр.219] [стр.220] [стр.221] [стр.222] [стр.223] [стр.224] [стр.225] [стр.226] [стр.227] [стр.228] [стр.229] [стр.230] [стр.231] [стр.232] [стр.233] [стр.234] [стр.235] [стр.236] [стр.237] [стр.238] [стр.239] [стр.240] [стр.241] [стр.242] [стр.243] [стр.244] [стр.245] [стр.246] [стр.247] [стр.248] [стр.249] [стр.250] [стр.251] [стр.252] [стр.253] [стр.254] [стр.255] [стр.256] [стр.257] [стр.258] [стр.259] [стр.260] [стр.261] [стр.262] [стр.263] [стр.264] [стр.265] [стр.266] [стр.267] [стр.268] [стр.269] [стр.270] [стр.271] [стр.272] [стр.273] [стр.274] [стр.275] [стр.276] [стр.277] [стр.278] [стр.279] [стр.280] [стр.281] [стр.282] [стр.283] [стр.284] [стр.285] [стр.286] [стр.287] [стр.288] [стр.289] [стр.290] [стр.291] [стр.292] [стр.293] [стр.294]