Главная / Образцы дипломных работ

Обзор по задачам упаковок

Внимание: Акция! Курсовая работа, Реферат или Отчет по практике за 10 рублей!
Только в текущем месяце у Вас есть шанс получить курсовую работу, реферат или отчет по практике за 10 рублей по вашим требованиям и методичке!
Все, что необходимо - это закрепить заявку (внести аванс) за консультацию по написанию предстоящей дипломной работе, ВКР или магистерской диссертации.
Нет ничего страшного, если дипломная работа, магистерская диссертация или диплом ВКР будет защищаться не в этом году.
Вы можете оформить заявку в рамках акции уже сегодня и как только получите задание на дипломную работу, сообщить нам об этом. Оплаченная сумма будет заморожена на необходимый вам период.
В бланке заказа в поле "Дополнительная информация" следует указать "Курсовая, реферат или отчет за 10 рублей"
Не упустите шанс сэкономить несколько тысяч рублей!
Подробности у специалистов нашей компании.

Код работы:	K002151
Тема:	Обзор по задачам упаковок

Содержание

Глава 1.Обзор по задачам упаковок.
Под задачами раскроя и (или) упаковки понимается широкий класс задач, объединенных однообразной логической структурой и допускающих различное толкование. Задача упаковки возникает при решении важных практических задач:
- задача раскроя материала (ткани, вырезания дисков из стального листа, листового металла, материалов из дерева);
- задача плотного размещения геометрических объектов в заданной области (размещение грузов, товаров на складе, и т. п.);
- задача загрузки транспорта (размещение товаров в транспортном средстве с учетом технологичности);
- задача загрузки рюкзака (выбор множества элементов с максимальной суммарной ценностью, объем которых не превосходит объема рюкзака);
- задача упаковки шаров;
- задача планировки помещений (максимизация полезных областей при планировании с учетом технологичных требований);
- задача обеспечения ритмичности производственного процесса (запуск и выпуск равных объемов продукции через одинаковые промежутки времени при равномерности трудовых затрат на изготовление этой продукции в течение каждого отрезка планового периода);
- задача распределения памяти вычислительной машины;
- задача о поставке в лесопилении (расположение пил при пилении бревна на доски разной толщины, выбор числа пил для максимизации выхода);
-задача о расстановке оборудования на заданной области);
- задача составления расписания многопроцессорных систем и т. д.
Каждая из приведенных задач может быть различным образом конкретизирована. Например, для задачи раскроя листового металла можно выделить несколько постановок. Эти задачи различаются геометрией материала и получаемых из него заготовок, размерностью и ассортиментом материала и заготовок, условиями реализации раскроя и другими дополнительными факторами.
Рассмотрим задачу упаковки шаров.
Представим, что некая фирма по производству шарикоподшипников получила заказ: отправить в иностранный порт столько одинаковых шариков для подшипников, сколько удастся погрузить на зафрахтованные суда в условленный день. Шарики приготовлены к отправке, однако в назначенный день в порту оказалось лишь одно судно, готовое принять груз. Член команды, ответственный за погрузку, объяснил представителю фирмы, что во избежание чрезмерной осадки судна шарики не должны занимать более трёх четвертей объёма трюма. Это замечание не смутило отправителя. «Вашему судну ничто не грозит, — ответил он уверенно, — заполняйте трюм доверху». Что делать ответственному за погрузку — верить или не верить клиенту?
Для решения этой задачи необходимо выяснить, насколько плотно можно уложить в пространстве большое количество одинаковых шаров. Если бы вместо шариков нужно было загрузить трюм судна одинаковыми кубиками, найти ответ было бы легко. Поскольку кубики плотно прилегают друг к другу и между ними не остаётся пустого места, они займут практически весь трюм (не считая небольших просветов вдоль стен и потолка), и в этом случае заверения клиента оказались бы неправдой. Однако шары нельзя упаковать так же плотно, как кубики: между ними всегда остаётся свободное место, и, если, несмотря на самую плотную упаковку, объём свободного пространства превысит четверть объёма трюма, его смело можно заполнить шариками и без риска выйти из гавани.
К сожалению, математически не доказано, что это максимально достижимая плотность. Из полученных до сих пор верхних оценок плотности наименьшая была найдена в 1958 году К. А. Роджерсом из Бирмингемского университета; он доказал, что никакая упаковка шаров не может иметь плотность большую чем ~0,7796. Однако этот результат не слишком поможет тому, кто ищет оптимальный способ упаковки шариков для подшипников. Дело в том, что в доказательстве Роджерса не предлагается никакой упаковки шаров, плотность которой была бы близка к найденной оценке. Более того, сам Роджерс в статье, где сообщалось о полученном доказательстве, заметил: «многие математики верят, а все физики знают», что правильный ответ составляет около 74%. За четверть века, прошедшие с тех пор, ничего не изменилось, и задача о плотной упаковке шаров, такая простая на вид и столь трудная по существу, остаётся одной из важных нерешённых проблем в математике.
Конфигурации плотной упаковки шаров изучаются уже многие годы. Отчасти это объясняется тем, что они тесно связаны с изучением свойств твёрдых тел и жидкостей. Так, например, физические свойства многих кристаллических материалов можно описывать, по крайней мере в первом приближении, исходя из модели кристалла как системы огромного числа твёрдых шаров (изображающих атомы) в плотной упаковке. Не менее важное применение эта модель находит при исследовании порошков и пористых материалов.
Кроме того, математики обобщили понятие шара и задачу об упаковке шаров на многомерные пространства и рассматривают объекты, называемые n-мерными шарами, алгебраическое описание которых напоминает алгебраическое описание обычных шаров. Оказалось, что поиск плотной упаковки шаров в n-мерном пространстве математически эквивалентен разработке конечного множества закодированных цифрами сообщений, которые допускают их передачу без искажений при минимальных затратах энергии. Более того, найденные в последние годы плотные упаковки в пространствах 24 и более измерений привели к крупным открытиям в самой математике — в той её области, которая называется теорией групп.
С проблемой упаковки шаров тесно связаны ещё две важные геометрические задачи. Одна из них известна как задача о «числе касаний»: сколько одинаковых шаров можно расположить вокруг одного такого же центрального шара, чтобы все они касались его? В 1694 году эта задача (в случае трёхмерного пространства) стала предметом получившего широкую известность диспута между Исааком Ньютоном и шотландским астрономом Джеймсом Грегори. Ньютон утверждал, что число касаний равно 12, и для описанной выше гранецентрированной кубической упаковки это действительно так (см. рис. 1). Грегори, по-видимому, не соглашался, настаивая на том, что можно «втиснуть» ещё один дополнительный шар, хотя он и не мог это доказать.
Одна из главных задач при осуществлении цифровой связи заключается в построении набора закодированных символов, или кодовых слов, который можно передать с максимальной надёжностью при минимальных затратах энергии. Допустим, что каждое кодовое слово представлено в виде восьмиразрядного символа, в каждом разряде которого стоит одно из пяти различных значений: 0, ?, 1, –?, –1. На первый взгляд кажется, что такая система обеспечит передачу 58 = 390 625 различных кодовых слов. Однако некоторые пары этих слов настолько мало различаются, что при передаче такая система будет слишком подвержена случайным ошибкам или электрическим помехам. Например, кодовые слова (1, 1, 1, 1, 1, 1, 1, 1) и (1, 1, 1, 1, 1, 1, 1, ?) так мало отличаются друг от друга, что если использовать их оба, то часто одно будет принято за другое. Иначе можно сказать, что если два кодовых слова столь же мало различаются, как (1, 1, 1, 1, 1, 1, 1, 1) и (1, 1, 1, 1, 1, 1, 1, ?), то потребуются очень большие затраты энергии, чтобы гарантировать различимость этих слов при наличии фонового шума.
Различимость кодовых слов и количество энергии, необходимое для их надёжной передачи, связаны общим математическим соотношением. Оно было впервые сформулировано в 1948 году Клодом Шенноном, работавшим тогда в фирме Bell Telephone Laboratories, в его статье «Математическая теория связи»).
Дэвид Слепян сказал, что «в этом веке больше не было, пожалуй, ни одной работы, которая бы так глубоко изменила наши представления о связи», как эта статья Шеннона. Шеннон показал, что при любом фиксированном количестве энергии всегда существует такая система кодовых слов, которая может быть передана практически без ошибок. При этом появляется лишь ограничение на скорость передачи кодовых слов: она не должна превышать некоторого критического порога, называемого пропускной способностью канала передачи. К сожалению, теорема Шеннона неконструктивна: в ней утверждается только существование таких систем кодирования, но нет и намёка на то, как их построить. И хотя с тех пор разработано много различных систем сигналов, ни одна из них не действует так прекрасно, как обещает теорема Шеннона.
Один из способов приблизиться к соотношению, указанному теоремой Шеннона, состоит в том, чтобы представить каждый сигнал как некоторую точку n-мерного пространства. Рассмотрим, например, произвольную последовательность из восьми чисел, принадлежащую системе сигналов. Физически каждому из этих чисел соответствует некоторый уровень напряжения в линии передачи, поэтому каждое кодовое слово можно графически представить на плоскости в виде набора из восьми отдельных импульсов заданной высоты на восьми интервалах временной оси. Ту же информацию можно выразить математически при помощи одной точки восьмимерного пространства.
Энергия, требуемая для передачи каждого импульса, пропорциональна квадрату напряжения, поэтому полная энергия, необходимая для передачи одного кодового слова, равна сумме квадратов трех дискретных напряжений, составляющих это кодовое слово. Эта сумма равна квадрату расстояния от начала координат точки трехмерного пространства, которая представляет это кодовое слово. Таким образом, проблема-минимизации затрат энергии эквивалентна задаче размещения всех точек, представляющих кодовые слова, как можно ближе к началу координат. С другой стороны, необходимость отчетливой различимости кодовых слов можно рассматривать как требование, чтобы соответствующие им точки в пространстве не подходили друг к другу ближе, чем на некоторое минимальное расстояние d. Сочетание двух этих требований геометрически эквивалентно поиску наиболее плотной упаковки неперекрывающихся твердых шаров радиуса d/2 вокруг начала координат.
Таким образом, задача разработки надёжной системы сигналов, обеспечивающей к тому же эффективное использование энергии, сводится к геометрической задаче размещения точек внутри некоторой области пространства при дополнительном условии, что они не должны находиться слишком близко друг к другу. Если требуется, чтобы расстояние между этими точками было, скажем, не меньше ?2, то задача эквивалентна построению плотнейшей упаковки шаров, радиус которых равен половине этого расстояния, т.е. ?2/2.
Сложность решения задачи упаковки обусловлена её принадлежностью к классу NP-полных задач, для решения которых не существует детерминированных алгоритмов полиномиальной сложности. Применение точных методов для решения NP-полных задач большой размерности невозможна из-за больших затрат временных ресурсов. Ситуация осложняется отсутствием математических моделей и алгоритмов, гарантирующих получение оптимального решения для большинства задач упаковки. В связи с этим, одним из наиболее перспективных направлений исследований является разработка и совершенствование различных приближенных, а также эвристических методов решения задач упаковки.
Как указано в начале, задачи упаковки важны для решения задач раскроя.
Впервые задачи раскроя геометрических объектов были рассмотрены великим русским математиком П.Л.Чебышевым. В его докладе «О кройке одежды» в 1878 г. рассматриваются вопросы о наилучшем покрытии кривых поверхностей плоскими выкройками из ткани.
В 1885 г. была опубликована работа Е.С.Федорова, в которой рассматривался ряд вопросов, возникавших при изучении кристаллов как природных многогранников. В книге «Симметрия и структура кристаллов» Е.С.Федоров определил совокупность элементов симметрии для конечных геометрических фигур в общем случае. Исходя из своих геометрических построений, он разработал классификацию кристаллических многогранников, теорию строения и симметрии кристаллов. Проективные преобразования (растяжение и сжатие) использованы для классификации кристаллических решеток. Получение многогранников, заполняющих пространство без налегания и двойных покрытий при условии их равенства, параллельности, ориентировки и смежности по целым граням, привело к четырем типам пространственных решеток.
Начиная с 1933 г. в печати начали регулярно появляться работы, посвященные проблемам раскроя материалов. Первыми задачами, для которых были предложены способы решения, оказались линейные задачи размещения, в которых геометрическая форма объектов не учитывается. Эти задачи получили название линейных, так как речь шла об определении минимума линейной функции при линейных ограничениях.

Так, в конце 30-х – начале 40-х годов фундаментальные исследования в области рационального раскроя были выполнены Л.В.Канторовичем и В.А.Залгаллером. Ими было показано, что для расчета оптимального раскроя могут быть использованы методы линейного программирования. Для преодоления трудностей, связанных с построением допустимых карт раскроя, указанными авторами были предложены приемы, которые, по существу, предвосхитили идеи динамического программирования.
В 1951 году Данциг, независимо от Л.В.Канторовича и В.А.Залгаллера, также показал связь между задачами раскроя задачами программирования.
В 1961 г. независимо от работ Залгаллер В.А. и Канторовича Л.В. Гилмори и Гомори решили с помощью метода линейного программирования проблему одномерного раскроя. В 1963 г. они применили технику линейного программирования к задаче раскроя бумаги. В 1965г. ими был предложен метод решения двумерной задачи раскроя. Для получения решения они ввели ограничения на направления резов, т.е. гильотинный раскрой, который может быть применен для решения практических проблем. В 1966 г. для решения задач одномерного и двумерного раскроев они использовали динамическое программирование.
В 1960-х годах методам решения задач фигурного раскроя были посвящены работы Л.Б.Беляковой. В 1975 г. Фримэн первым из зарубежных исследователей рассмотрел нерегулярное размещение объектов в прямоугольные области.
Кристофидес в 1977 г. использовал дерево решений для нахождения оптимального решения для двумерного раскроя. Это было первое применение эвристики для решения раскройной задачи.
Во второй половине 70-х годов появилось много эвристических способов решения.
В 80-х годах для решения проблемы раскроя-упаковки была использована теория искусственного интеллекта. В эти же годы было признано, что применение различных эвристик, возможно, лучший способ для нахождения хороших решений за приемлемое время.
В начале 90-х годов для решения проблемы раскроя были применены другие эволюционные методы, такие как, Simulated Annealing, Tabu Search, Ant Colonies и др.

В зависимости от размерности раскраиваемого материала различают одномерный, двумерный раскрой и объемный раскрой-упаковку (рис. 1).
По форме объектов различают прямолинейный и фигурный виды раскроя-упаковки. Прямолинейный объединяет линейный, прямоугольный и параллелепипедный виды раскроя-упаковки.

Рис. 1. Задачи упаковки.
Задачи плотного размещения двух- и трехмерных объектов сложных геометрических форм составляют, в свою очередь, фигурный раскрой-упаковку. Если в случае прямолинейного раскроя разрешены только сквозные резы, параллельные кромкам раскраиваемого материала, то такой раскрой принято называть гильотинным.
Гильотинный раскрой стальных и иных листов широко используется в машиностроении и других отраслях промышленности. Этот раскрой фактически является задачей упаковки прямоугольников различных размеров в заданный лист при использовании гильотинной процедуры. При этом важно уменьшить отходы листа.
Все остальные способы реализации раскроя-упаковки – негильотинные. Прямоугольный негильотинный раскрой представляет частный случай фигурного раскроя. Задача прямоугольной упаковки представляет значительный теоретический интерес, так как имеет многочисленные приложения: негильотинный прямоугольный раскрой в машиностроении, размещение элементов электронных схем на платах, оптимизация раскроя строительных материалов, распределение двумерного ресурса в экономических задачах.
Задачи упаковок сферических сегментов на сфере S находят важные приложения для исследования спутниковых систем многократного обзора всей поверхности Земли. В работе [ ] установлено, что задачи k-кратного покрытия S сферическими сегментами и задачи многократной упаковки сферических сегментов на сфере S связаны. Решая задачу упаковки на S можно решить задачу покрытия S. Таким образом, разрабатывая алгоритмы упаковки, мы получим алгоритмы для решения задач покрытия и наоборот. Это свойство будет использовано в данной работе.
В данной работе представлены математические модели задач многократной упаковки равных сферических сегментов наибольшего возможного углового радиуса и решающий алгоритм для такой задачи. Разработано программное обеспечение реализующее указанный алгоритм и проведены расчёты.
Отметим, что алгоритм нахождения многократных упаковок является достаточно сложным. Он основан на использовании многократных областей Вороного на сфере. Эти области, в отличие от работ других авторов, строятся точными методами, что сопряжено с необходимостью анализа различных вариантов возможных положений центров сферических сегментов. Точное нахождение областей Вороного позволяет повысить точность решения исходной задачи.

Модели и методы решения задач упаковок
Общая постановка задачи.
Пусть G – часть евклидова пространства Еn , либо совпадает с Еn .
Система равных (конгруэнтных) замкнутых сферических сегментов образует -кратное (k ? 1) покрытие G, если каждая точка s (s є G) принадлежит k сферическим сегментам как минимум. Система конгруэнтных открытых сферических сегментов образует k – кратную (k ? 1) упаковку в G, если каждый сферический сегмент содержится в G и любая точка s (s є G) принадлежит k сферическим сегментам как максимум.
Если G – ограниченное измеримое множество, то плотностью покрытия называется отношение суммы мер («объемов» в Еn при n>2 или площадей в
Е2), покрывающих сферических сегментов к мере G. Точно так же определяется плотность упаковки в G. В случае неограниченного G или когда G = Еn, под плотностью покрытия понимается предел плотностей сферических сегментов, покрывающих шар K ( R ) радиуса R, когда R ? ?, а для упаковки – предел плотностей сферических сегментов, упаковываемых в сферический сегмент K( R), когда R ? ?.
Для ограниченных G понятие плотности достаточно простое, для неограниченных G нужно показывать, что плотность не зависит от выбора центра сферического сегмента K( R ) и т.п. В данной работе исследуются покрытия ограниченных множеств и упаковки в ограниченных множествах, поэтому не анализируется понятие плотности для неограниченных множеств.
Для упаковок отыскиваются упаковки, имеющие наибольшую плотность, для покрытий – наименьшую плотность. Очевидны обобщения этих задач, когда упаковываемые или покрывающие сферические сегменты имеют различные радиусы (с заданными соотношениями их диаметров) или рассматриваются фигуры или тела, отличные от сферических сегментов.
Задачи упаковок и покрытий могут формулироваться и для случая, когда G – некоторая поверхность, например, G=S, S – сфера единичного радиуса в Еn . Так, если S – сфера единичного радиуса в Е3 , то исследуется покрытие S сферическими сегментами (для простоты их будем считать кругами). Аналогично рассматривается упаковка кругов (сферических сегментов) на сфере S. Считая кругом часть сферы S в Еn , n>3, принадлежащую некоторому сферическому сегменту К с центром на S, можно рассматривать упаковки и покрытия кругами сферы в Еn , n>3.
Из формулировок задач упаковок и покрытий видна их однотипность , в некотором смысле их похожесть. В дальнейшем будет выявлена их существенная взаимосвязь. Будет установлено, что для сферы в Еn, n?3, решение задачи многократного покрытия кругами можно свести к решению задачи многократной упаковки кругов, и наоборот. Именно ввиду такой их взаимосвязи эти задачи рассматриваются в данной работе вместе.
2.Постановка задачи(из диплома)
Пусть S- сфера единичного радиуса, в дальнейшем сфера S. Множество N замкнутых сферических сегментов (кругов) K_j, 1?j?N, одинакового радиуса r образует k- кратное (1?k?N) покрытие G, если каждая точка s из G принадлежит k этим сферическим сегментам как минимум.
Пусть S- сфера единичного радиуса, в дальнейшем сфера S. Множество N открытых сферических сегментов (кругов) K_j, 1?j?N, одинакового радиуса r образует k- кратную (1?k?N) упаковку G, если каждая точка s из G принадлежит не более чем k этим сферическим сегментам. Сформируем задачу.
Задача. Требуется выбрать расположение N сферических сегментов (кругов) K_j, 1?j?N, одинакового радиуса r, образующих k- кратное покрытие G таким образом, чтобы их радиус r достигал наименьшего возможного значения r_(N,k)^*.
Требуется выбрать расположение N сферических сегментов (кругов) K_j, 1?j?N, одинакового радиуса r, образующих k- кратные упаковки G таким образом, чтобы их радиус r достигал наибольшего возможного значения r_(N,k)^*.
Данная задача покрытия известна также как задача об N- центре. Актуальность поставленной тематики определяется не только важными разнообразными приложениями задач покрытий, но имеет также самостоятельный математический аспект, ибо к таким задачам (моделям) сводится исследование многих комбинаторных и других математических задач.
Цель дипломной работы:
анализ свойств математических моделей и развитие методов оптимизации многократных покрытий сферы;
анализ свойств математических моделей и развитие методов оптимизации многократной упаковки сферы;
Задачи исследования:
выявить свойства математических моделей задач покрытия;
выявить свойства математических моделей задач упаковки;
выявить свойства математических моделей задач упаковки;
разработать численные алгоритмы расположения сферических сегментов (кругов) для k- кратного (k?1) покрытия сферы;
разработать численные алгоритмы расположения сферических сегментов (кругов) для k- кратной (k?1) упаковки сферы;
получить алгоритмы для оценки минимальных радиусов покрывающих сегментов;
проанализировать полученные алгоритмы;
разработать программу, реализующую алгоритмы;
провести тестовые расчеты;
Продолжение общей постановки задачи
Известно, что задача k- кратного покрытия сферы S равными кругами сводится к задаче (N-k) – кратной упаковки N равных кругов на S, и наоборот. Установим зависимости между плотностями k- кратных покрытий и (N-k) – кратных упаковок.
Напомним, что сферический сегмент на сфере S мы называем кругом на S.
Теорема: Совокупность N конгруэнтных замкнутых кругов K_j, 1?j?N, углового радиуса ? образуют k- кратное (1?k?N-1) покрытие сферы S тогда и только тогда, когда N конгруэнтных открытых кругов K_j^c=S/K_j , 1?j?N, образуют (N-k) – кратную упаковку на S.

4.Алгоритм оптимизации многократной упаковки на сфере сферических сегментов
4.1.Общая схема алгоритма

Области Вороного широко используются многими авторами для решения задач покрытия, имеются различные варианты использования областей Вороного. Так, в работе [15] проведен сравнительный анализ нескольких возможных вариантов использования (многократных) областей Вороного. Приведен лучший алгоритм из работы [15] для решения задач k- кратного (k?1) покрытия.
Выбираем начальное расположение центров c_jсферических сегментов (кругов)K_j, 1?j?n, на S. Точки c_j, 1?j?n, порождают вектор ?.
Строим области Вороного V_j^kдля множества точек {c_j, 1?j?n}, V_j^k?S
Для каждой области V_j^k сдвигаем точку c_j к точке c_j^*, являющейся центром минимального круга, покрывающего всю область V_j^k (1?j?n). Точки c_j^* порождают вектор ?^*.
Если евклидово расстояние между ? и ?^* меньше заданного, то останавливаемся, иначе полагаем c_j?c_j^*, 1?j?n, и идем к шагу 2.
Все итерационные алгоритмы с использование только областей Вороного не гарантируют нахождения глобального экстремума радиусов покрывающих кругов.

4.2. Вспомогательные вычисления
4.2.1.Перевод сферических координат в декартовые координаты

Пусть т.s имеет широту ? и долготу ?, из геометрических рассуждений легко видеть, что
x=cos?? cos??,
y=cos?? sin?,
z=sin??
Поясним эти выражения по рис. 1.

Рис. 1
Из рис.1 видно, что x=l cos??, т.к. l=r cos??, а r=1, то
x=cos?? cos??
Аналогично, y=l sin??=cos?? sin?? и z=r sin??=sin??.

4.2.2.Перевод декартовых координат в сферические координаты
Пусть т.sимеет декартовые координаты x, y и z. Получим сферические координаты точки s.
Из выражения z=sin?? выразим
?=arcsin?z=arctg z/?(1-z^2 ) (1)
Если |z-1|??, т.е. если значение координаты zпо модулю намного отличается от единицы, то мы используем для вычисления широты ? формулу (1). При этом если z?0, то ??0, а если z<0, то и ?<0.
Если же |z-1|??, т.е. значение координаты zпо модулю отличается от единицы не более, чем на достаточно малую величину ?, то можно считать, что при z>0, ?=?/2, а при z<0, ?=-?/2.
Найдем долготу ?. Если ?=?/2 или ?=-?/2, то можно определить ?=0. В остальных случаях долготу ? находим исходя из выражения:
?=arcsin??y/cos?? ?=arctg (y/cos?? )/?(1-(y/cos?? )^2 ) (2)
Формулу (2) легко получить из выражения для декартовой координаты y: y=cos?? sin?? =>? sin????=y/cos?? ? => ?=arcsin??y/cos?? ?. Пусть y/cos?? =b, тогда ?=arcsin??|b|=arctg |b|/?(1-b^2 )?.
Изобразим долготу ? на рис.2. Найдем угол ?=?/2-?=?/2--arctg |b|/?(1-b^2 )=arcctg |b|/?(1-b^2 )=arctg ?(1-b^2 )/|b| .

Рис.2

Рассмотрим следующие возможные случаи:
если y?0, x?0, то ?=?/2-?=?/2-arctg ?(1-b^2 )/|b| ;
если y?0, x<0, то ?=?/2+?=?/2+arctg ?(1-b^2 )/|b| ;
если y<0, x?0, то ?=3?/2+?=3?/2+arctg ?(1-b^2 )/|b| ;
если y<0, x<0, то ?=3?/2-?=3?/2-arctg ?(1-b^2 )/|b| .
Таким образом, находим широту ? и долготу ?.

4.3.Определение минимального радиусаr_(N,k) сферических сегментов, образующих k-кратное покрытие сферы

Пусть известны следующие данные: число сферических сегментов (кругов) N, кратность покрытия сферы k и сферические координаты центров кругов (?_j;?_j ),1?j?N.
Необходимо найти минимальный радиус Nсферических сегментов, образующих k – кратное покрытие всей сферы. При решении данной задачи будем опираться на следующую лемму 5.1 из [14].
Лемма 5.1. Наименьший угловой радиус N равных замкнутых кругов с центрами a_j?S, 1?j?N, образующих k- кратное (1?k?N-1) покрытие сферы S, равен угловому радиусу наибольшего открытого круга, содержащего не более (k-1) точек a_j, 1?j?N.
Для дальнейшего решения поставленной задачи необходимо, во-первых, сферические координаты центров кругов перевести в их декартовое представление. Получим точки центров кругов a_j (x_j;y_j;z_j), 1?j?N. Переход из сферической системы координат в декартовую систему происходит по следующим формулам:
x_j=cos???_j cos???_j, ? ?
y_j=cos???_j sin???_j,? ?
z_j=sin???_j ?
Теперь начинается процедура нахождения минимального радиуса. Обозначим радиус r_(N,k)какR_k.Для начала будем считать R_k=0.Решение данной задачи будем проводить в два этапа:
Выбираем по две точки центров кругов
Выбираем по три точки центров кругов
Рассмотрим I этап. Выбираем по две разных точки центров кругов a_i,a_j,i?j. Таких возможных вариантов выбора будет
C_N^2=( N!)/(N-2)!2!
Далее проводим следующие действия:
а) Определяем S- середину отрезка [a_i,a_j ]. Координаты середины отрезка находим по следующим формулам:
x_s=(x_i+x_j)/2, y_s=(y_i+y_j)/2, z_s=(z_i+z_j)/2
Также находим расстояние от центра сферы до точки S, т.е. определяем длину вектора ?=?(x_s^2+y_s^2+z_s^2 ). Если ? меньше или равно заданной точности ?_2, то переходим к следующей паре точек, ибо плоскость P, проходящую через точки a_i,a_jможно повернуть таким образом, что плоскость P будет содержать три точки центров кругов a_i,a_j,a_l.
б) Если ? больше заданной точности ?_2, то строим вектор (OS) ? с началом в
т.O – центр сферы. Нормируем вектор (OS) ?:
x_s=x_s/?, y_s=y_s/?, z_s=z_s/?
Вычисляем скалярное произведение B=x_s x_i+y_s y_i+z_s z_i, гдеx_i, y_i, z_i- координаты точки a_i. Пусть m_1- количество точек, содержащихся в конусе K, образованном точками a_i,a_j, и m_1=0; m_3- количество точек, принадлежащих плоскости P, и m_3=0; введем число C=B+?_2.
в) Вычисляем угол ?=arc cos?? и определяем число точек центров кругов a_l, l?i, l?j, находящихся по разные стороны от плоскости P, проведённой через точку S перпендикулярно вектору (OS) ?. Для этого для каждой точки a_l, l?i, l?j вычисляем скалярное произведение A=x_l x_s+y_l y_s+z_l z_s. Если |A-B|C, то m_1=m_1+1, значит точка принадлежит конусу K.
г) Введем переменную R_k^'=0, обозначающую радиус на данном этапе. Если кратность покрытия сферы k?m_1+1, то R_k^'=?, если k?m_2+1, то R_k^'=?-?, где m_2-число точек вне K?P.
д) Проверяем условие R_k^'>R_k, т.к. по лемме 5.1 мы ищем радиус наибольшего открытого круга. Если условие выполняется, то R_k=R_k^'.
е) Выбираем другую пару точек a_i,a_j.Таким образом перебираем все пары точек, какие только возможно.
Рассмотрим II этап. Выбираем по три точки центров кругов a_i,a_j, a_l,i?j?l. Таких возможных вариантов выбора будет
C_N^3=( N!)/(N-3)!3!
Далее проводим следующие действия:
а) Проводим через три выбранные точки плоскость P и определяем ?- расстояние от центра сферы до плоскости P. Для этого построим уравнение плоскости, введя следующие обозначения:
x_1=x_i, x_2=x_j, x_3=x_l
y_1=y_i, y_2=y_j, y_3=y_l
z_1=z_i, z_2=z_j, z_3=z_l
Находим коэффициенты:
A=(y_2-y_1 )(z_3-z_1 )-(y_3-y_1)(z_2-z_1)
B=(x_3-x_1 )(z_2-z_1 )-(x_2-x_1)(z_3-z_1)
C=(x_2-x_1 )(y_2-y_1 )-(x_3-x_1)(y_2-y_1)
F=A^2+B^2+C^2, F=?F-норма вектора F
D=-[Ax_1+By_1+Cz_1]
Если D>0, то A=-A, B=-B, C=-C, D=-D.
Если норма F меньше или равна заданной точности ?_2, то ?=|D|, иначе производим нормировку ?=|D|/F.
б) Если плоскость P проходит через центр сферы, т.е. F??_2, то определяем, сколько точек a_m, m?i,j,l, находится по разные стороны от плоскости P следующим образом. Вводим переменные p=0, q=0, где p-число точек, находящихся дальше от центра, чем на P, и q-число точек на плоскости P. Перебирая все точки a_m, вычисляем V=Ax_m+By_m+Cz_m+D, т.е. координаты каждой точки a_m подставляем в уравнение плоскости. Если |V|?_2, то p=p+1.
Таким образом, перебрав все точки, проводим следующие присваивания: m_1=p, m_3=q, m_2=N-m_1-m_3. Дальше проверяем условия. Если k<(min?(m_1,m_2 ) )-1, то R_k^'=0. Если k?(min?(m_1,m_2 ) )-1, то R_k^'=?/2. Переходим к пункту г).
в) Если плоскость P не проходит через центр сферы, т. е. F>?_2, то из центра сферы проводим перпендикуляр к плоскости P и находим его координаты, т. е. x_s=A/F, y_s=B/F, z_s=C/F. Определяем угол ?=arc cos??.
Определяем сколько точек a_m, m?i,j,l, находится по разные стороны от плоскости P по скалярным произведениям следующим образом:
V=x_s x_i+y_s y_i+z_s z_i, x_i, y_i,z_i-координаты точки a_i. Введем число W=V+?_2
Также вводим аналогичные переменные m_1=0,m_3=0 (пункт б) Iэтап). Определяем скалярное произведение, перебирая точки a_m,V_1=x_m x_s+y_m y_s+z_m z_s.Если |V_1-V|?1,5?_2, то m_3=m_3+1.Если V_1>W, то m_1=m_1+1.
Перебрав все точки, определяем m_2=N-m_1-m_3.
Введем переменную R_k^'=0, обозначающую радиус в данном пункте. Если кратность покрытия сферы k?m_1+1, то R_k^'=?, если k?m_2+1, то R_k^'=?-?.
г) Проверяем условие R_k^'>R_k, т.к. по лемме 5.1 мы ищем радиус наибольшего открытого круга. Если условие выполняется, то R_k=R_k^'.
д) Выбираем другую тройку точек a_i,a_j,a_l, таким образом перебираем все тройки точек, какие только возможно.
Пройдя эти два этапа, мы найдем радиус R_k.

4.4 . Алгоритм нахождения многократных областей Вороного на сфере.
На сфере S известно положение n точек c_i (x_i ?,y?_i,z_i), 1?i?n. Надо найти вершины областей Вороного V_i, 1?i?n. Заранее неизвестно число вершин у области V_i, 1?i?n. У каждой области V_i может быть различное число вершин. Таким образом, по известным данным нужно найти вершины областей Вороного. Имеем:
n - число точек;
k – кратность покрытия;
массивы x(i), y(i), z(i)-1?i?n- координаты центров, т.е. точек c_i;
E.
Требуется найти на выходе:
Массивы xx(i,j), yy(i,j), zz(i,j) – координаты j – ой вершины i – ой области Вороного;
Массив p(i), 1?i?n, p(i)- число вершин области V_i, p(i)- целые числа.
Процедура нахождения вершин областей состоит в следующем.
Перебираем всевозможные различные тройки точек c_i,c_j ?,c?_l?S, 1?i,j,l?n.
Для каждой тройки точек c_i,c_j ?,c?_l?S проводим плоскость P_ijl через них:
|?(x-x_(i ) y-y_(i ) z-z_i@x_j-x_i y_j-y_i ? z?_j-z_i @x_l-x_i y_l-y_i ? z?_l-z_i )|=0
(x-x_(i ) )| ?(y_j-y_i ? z?_j-z_i @y_l-y_i ? z?_l-z_i )|-(y-y_i )| ?(? x?_j-x_i ? z?_j-z_i @? x?_l-x_i ? z?_l-z_i )|+(z-z_i )| ?(? x?_j-x_i y_j-y_i @? x?_l-x_i y_l-y_i )|=0
[(y_j-y_i )(? z?_l-z_i )-?( z?_j-z_i)( y_l-y_i)]x+[-(x_j-x_i )(? z?_l-z_i )+(? z?_j-z_i )( x_l-x_i)]y+[(x_j-x_i )(? y?_l-y_i )-?( y?_j-y_i)( x_l-x_i)]z-Ax_i-By_i-Cz_i=0
Ax+By+Cz-(Ax_i+By_i+Cz_i )=0,
sq=?(A^2+B^2+C^2 ),
v_1=A/sq, v_2=B/sq, v_3=C/sq .
Точка a_ijl имеет координаты (v_1,v_2,v_3), а точка ?-a?_ijl имеет координаты (-v_1,?-v?_2,?-v?_3).
Для точки a_ijl вычисляем скалярное произведение вектора (oa_ijl ) ? и векторов
(oc_q ) ?, 1?q?n.
Полученные n величин s(q) упорядочиваем по убыванию:
s(m_1 )?s(m_2 )?…?s(m_(k+2) )?…?s(m_n)
и запоминаем их индексы ? m?_(1 ), m_2,…,m_(k+2),…, m_n, (k – кратность покрытия, эта величина k задана заранее).
Выясняем будет ли:
|s(m_k )-s(m_(k+2) )|? E, (4.1)
где E- заданная величина, положим E=0.001.
Если (4.1) не выполняется, то идем к и1.
Если (4.1) выполняется, то находим
sm=v_1 x_i+v_2 y_i+v_3 z_i,
и выясняем будет ли:
|s(m_k )-sm|?E. (4.2)
Если (4.2) не выполняется, то идем к и1.
Если (4.2) в.......................

Для получения полной версии работы нажмите на кнопку "Узнать цену"

Узнать цену

Каталог работ

Похожие работы: