|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[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) критические точки определяется постепенно по ходу работы алгоритма. Однако мы будем рассматривать алгоритм, в котором расписание легко найти заранее. В частности, абсцисса конца любого отрезка является критической точкой. Упорядочим концы отрезков в порядке возрастания их абсцисс. Отрезок начинает влиять на состояние дел у прямой с момента, когда прямая проходит через его левый конец, и перестаёт с момента, когда прямая проходит |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||