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


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




[263]

35.1-1

Докажите, что при положительном р\ хр2 вектор р\ находится по часовой стрелке от векторар2, а при отрицательном - против. Оба вектора выходят из начала координат (0,0), бер/тся направление поворота в ближайшую сторону.

35.1-2

Напишите алгоритм сортировки, располагающий точки (pi,р2, .,рп)- в порядке обхода против часовой стрелки, если смотреть из заданного полюса ро. (Начать можно с любой точки.) Алгоритм должен использовать векторное произведение для сравнения углов и выполняться за время О (га lgra).

35.1-3

Как за время 0(га21пга) определить, лежат ли какие-то три из данных га точек на одной прямой? 35.1-4

Чтобы узнать, являются ли точки (ро, pi,..., pn-i) вершинами выпуклого многоугольника (подробнее о многоугольниках см. в разделе 16.4), перечисленными в порядке обхода многоугольника, профессор предлагает такой метод: проверить, что множество ZpiPi+ipi+2 г = 0,1,..., га - 1, где г+1 и г + 2 вычисляются по модулю га, не содержит одновременно правых и левых поворотов. Покажите, что этот способ не всегда дают правильный ответ, хотя и выполняется за линейное время. Как изменить его, чтобы получить правильный ответ (также за линейное время)?

35.1-5

Правый горизонтальный луч (right horizontal ray) точки ро = (жо, уо) определяется как множество {рг- = (жг,уг) : ж - г х$иу{ = Уо}, то есть как луч, выходящий из ро вправо параллельно оси абсцисс. Как за время 0(1) определить, пересекаются ли горизонтальный луч точки ро и отрезок р~\р2, сведя задачу к исследованию пересечения двух отрезков?

35.1-6

Чтобы узнать, лежит ли точка ро внутри простого (не обязательно выпуклого) многоугольника Р, можно рассмотреть какой-нибудь луч, выходящий из точки ро, и посчитать, сколько раз он пересекает границу многоугольника: она будет внутренней, если число пересечений нечётно. Используя эту идею, напишите алгоритм, определяющий за время О (га), является ли данная точка ро внутренней для простого га-угольника Р. (Указание. Используйте упражнение 35.1-5. Особого рассмотрения требуют случаи, когда точка ро лежит на границе многоугольника, когда луч проходит через одну из его вершин или содержит участок стороны.)

35.1-7

Покажите, как за время О (га) вычислить площадь простого (не обязательно выпуклого) га-угольника, заданного перечислением вершин в порядке обхода.


Упорядочение отрезков относительно различных вертикальных прямых, (а) Для этой конфигурации а >г с, a >t b, b >t с, a >t с и b >и с; отрезок d не сравним ни с каким из отрезков на рисунке. (Ь) При проходе точки пересечения отношение порядка между отрезками ей/ меняется на противоположное: е >v f, а / >w е. Когда движущаяся прямая z пересекает серую область, отрезки е и / являются соседними с точки зрения соответствующего ей порядка

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

Алгоритм выполняется за время О (га In га), где га - число данных отрезков. При этом проверяется только наличие или отсутствие пересечений; сами пересечения не находятся. (Как показывает упражнение 35.2-1, их отыскание может потребовать времени

Метод движущейся прямой (sweeping line method) состоит в том, что воображаемая вертикальная прямая движется слева направо мимо рассматриваемых геометрических объектов. Идея состоит в том, что от двумерного пространства мы переходим к произведению пространство-время (оба одномерны), считая ось абсцисс осью времени, движущуюся прямую - мгновенным срезом ситуации. При этом линии на плоскости становятся движущимися по прямой точками, и их можно упорядочивать. (Обычно они хранятся с помощью динамической структуры данных.) В задаче о пересечениях отрезков алгоритм просматривает концы всех отрезков слева направо и проверяет, нет ли пересечения на очередном участке оси абсцисс.

Наш алгоритм использует два упрощающих предположения. Мы считаем, что среди рассматриваемых отрезков нет вертикальных и что никакие три отрезка не походят через одну и ту же точку (упр. 35.2-8 требует построить алгоритм, который годится во всех случаях.) Следует отметить, что возня с разнообразными граничными случаями - один из основных источников хлопот и ошибок при программировании задач вычислительной геометрии.

Отношения порядка на отрезках

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

35.2. Есть ли пересекающиеся отрезки?


упорядочиваем отрезки (те, которые её пересекают) по ординате точки пересечения.

Более точно, два отрезка s\ и s2 сравнимы относительно ж (comparable at ж), если вертикальная прямая, с абсциссой ж, пересекается с ними обоими. При этом s\ выше s2 относительно ж (si is above s2 at ж, обозначение s\ >x s2), если отрезки s\ и s2 сравнимы относительно ж и точка пересечения s\ с вертикальной прямой находится выше точки пересечения s2 с этой же прямой. На рисунке 35.4 (а) мы видим, что а >г с, a >t b, b >t с, a >t с и Ь >и с, а отрезок d не сравним ни с одним из остальных.

Для любого фиксированного ж отношение «>х » является отношением порядка (см. раздел 5.2) на множестве отрезков, пересекающихся с вертикальной прямой, проходящей через ж. При разных значениях ж этот порядок (как и множество, на котором он определён) может быть различным. Отрезок попадает в это множество, когда вертикальная прямая проходит через его левый конец, и выбывает из него, когда она проходит через правый конец.

Что происходит, когда вертикальная прямая проходит через точку пересечения двух отрезков? Отношение порядка между пересекающимися отрезками в точке пересечения меняется на противоположное (рис. 35.4 (Ь)): прямые v и w находятся слева и справа от точки пересечения отрезков ей/, при этом е >v / и / >и е.

Напомним, что по нашему предположению никакие три отрезка не проходят через одну и ту же точку, поэтому в окрестности точки пересечения пересекающиеся отрезки непосредственно следуют один за другим (с точки зрения указанного порядка), рис. 35.4 (Ь).

Движение прямой.

Используя метод движущейся прямой, мы храним информацию двух видов:

1.Состояние дел у прямой (sweep-line status) задаётся упорядоченным множеством объектов, пересекаемых движущейся прямой в текущий момент.

2.Расписание (event-point schedule) представляет собой последовательность моментов времени, в которых состояние может измениться (перечисленных в порядке возрастания времени). Такие моменты времени мы будем называть критическими точками (event point), так что изменение состояния дел у прямой возможно только в критической точке.

Для некоторых алгоритмов (см., например, упражнение 35.2-7) критические точки определяется постепенно по ходу работы алгоритма. Однако мы будем рассматривать алгоритм, в котором расписание легко найти заранее. В частности, абсцисса конца любого отрезка является критической точкой. Упорядочим концы отрезков в порядке возрастания их абсцисс. Отрезок начинает влиять на состояние дел у прямой с момента, когда прямая проходит через его левый конец, и перестаёт с момента, когда прямая проходит



[стр.Начало] [стр.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]