Кук Д., Бейз Г. - Компьютерная математика (1048841), страница 52
Текст из файла (страница 52)
данного упражнения, если А, В, С и Р— регулярные матрицы размера пХп. 3. Определить копечный автомат для языка Ь, опреде ленного как 11»01» (т. е. Ь 1вю (О, 1)*: в) начинается с 1 и имеет только один нуль. Выписать правую линейную грамматику, определяемую этим автоматом, и последовательность перемещений, делающих представимой строку 111011, ГЛАВА «О КОМПЬ1ОТЕРПЛЯ ГЕОМЕТР11Я Эта глава дает векоторые сведения из геометрия, которые широко используются в компьютерной графике и компьютервом вспомогательном математическом обеспечении; при атом делается попытка изложить все болев строго и увпфвцировапио, чем это делается во многих книгах по компьютерам. Мы стремимся представить серию «приемов» в векотором, очевидно, случайном порядке, а также использовать копцепцвп, развитые в предыдущих главах (особенно в гл.
1 — 3, 5, б), чтобы обеспечить основу для обсуждения выбрапвых теы, включающих одпородные координаты, кривые п яоверхпостп. Дано также четырехмерное представление данных трехмерной геометрии, широко используемое ва практике. Перед началом обсуждевия будет полезно, чтобы читатель имел векоторое представление о разнице между терминами «топология» и «геометрияы геометрия изуча ет расстояния и углы, тогда как топология занимается более общими свойствами.
Например, две сферы с различными радиусами являются топологически вквивалевтными, а геометрически — вет. Два объекта топологическп зквивалевтны, если один пз пих может быть получен из другого искривлением и растяжением последнего без разрыва ~чтобы быть более точными, путем использования вепрерывпого отобран епия, обратпое к которому также непрерывно), тогда как в геометрии оквпвалептныв объекты должны быть идентпчпы во всех откошепиях, за исключением их воложевпя и ориептацип в пространстве. Теория графов является частью топологии, поскольку вершины не обладают свойством полон«еппя в прострапстве и топология графа есть отношение ребер.
Обычно удобна аапомипать е памяти компьютера два рааличвых мвожества данных, отпосящихся к рассматриваемому объекту,— топологические данные и геометрические давпые. Например, можно представать широкий 3'г« класс объектов при помощи каркасных моделей. На рис. 10.! дано такое представление конечного цилиндра. Топология модели такого тица может рассматриваться как граф и моя!ет быть представлена в виде связноц списочной структуры. Геометрические данные могут быть просто списком векторов, определяющих положения вершин в Йз. Целью разделения содержания геометрии и топологии является то, что мы хотим преобразовать пашу модель некоторым образом, например чтобы она была физически меньше, пли передвинуть ее в не- Рвс. !О.1 которое новое положение, изменив ориентацию в пространстве.
Такие преобразования не изменяют топологии модели, и нам просто изменить соответствусощим образом геометрическое множество данных. В $1, 2 мы будем заниматься системами координат, которые дают возмоягность пред ставить геометрические данные, и некоторыми полезнымп в дальнейшем множествами преобразований, которые могут применяться и геометрическим множествам данных.. $1. Системы координат для подмножеств В' В общем случае система координат (координатная система) или параметризация множества Я и! В" является идентификацией каждой точки в Я при помощи единственного упорядоченного набора чисел ($ь ..., $,)ж В' (ож Х). В терминологии отображений система координат для Я мол<ет быть определена как непрерывная бнекцня Ф: Я - 9', где У !и К . Любое преобразование или другое вычисление, осуществляемое на Я, тогда выполняется в терминах координат Дь..., $,).
Конкретное отображение, которое выбирается для данной аадачи, часто будет определяться геометрией пространства Я, Можно показать, что д для фиксированного Я является постоянным для всех систем координат и называется размерностью Я. К сожалению, в одном из приведенных ниже примеров (однородные системы координат) требуется, чтобы У было всем пространством; кроме того, существует много по- 64д лезиых подмножеств, для которых такие отображепия ие существуют (например, круг или сфера). Чтобы разобраться с этим, следовало бы совершить небольшой акскурс в топологию; однако вместо этого будем надеяться, что проведенное ниже рассуждение, несмотря на недостатки определения, поможет хорошо разобраться в данном вопросе. В основном нас будут интересовать пространства размерности 3 и меньше; например, кривые являются одномерными объектами, а поверхности имеют размерность 2.
В следующих примерах представлены некоторые наиболее общие координатные системы в Вз и В', однако там, где легко обсудить более общий случай, мы это будем делать. П ример 1.(. Прямоугольная система координат в В' (ныл). Если В (еь ..., е.) — базис в В", то каждый элемент хш В" ыожет быть записан единственным обравом в виде л х ~аео где а~енВ, 1<((н. < 1 Отображение Ф: К'- К", задаваемое как Ф(х)=(ан ...
..., а„), определяет координатную систему в К". Если В ортонормирован, то соответствующие координаты называются декартовыми координатами в В". В К' и Кз обычно ортонормированпый базис интерпретируют геометрически как правосторониюю систему координат в смысле $4гл.5. Х Следующий пример в В" является более сложным с математической точки зрения. Необходимо некоторое предварительное обсуждение перед тем, как мы опишем эту систему. Начнем с определения отношения - на В"+'.
Определим его следующим образом: х - у, есля х - ау для некоторого а иВЧО). Важные свойства этого отношения сформулированы в следующем предложении, доказательство которого оставляется в качестве упражнения. Предложение. Отношение является отношением эквивалентности на К"+'. Отношение - определяет следующие классы эквивалентности: Р" (Ы(0): Ь вЂ” одномерное векторное подпростравство К"+', 0 — нулевой вектор в В"ы) и (О). Иб Очевидпо, что Й"" Р" 0 (01. Определим подмпоже- ство Р". Определеппе. Пусть хюИ"+' имеет впд (хн ... ..., х„, О), где ве все х< равны нулю, Тогда [х] ж Р" на- зывают бесконечно удаленной точкой. Обозиачим множе- ство всех бесконечно удаленпых точек Р" через Ь" и определим Н" как Р"~Ь .
е Следующий результат играет важную ролы ои уста- павливает координатное отображение И". Предложение. Существует биекция ()": Н"- И". Д о к аз а т е л ьот во. Определим отиошепие ()": Н" И" следующим образом: (г" ([(х„..., т,+,)1) = $ — (х„..., х„). Вначале заметим, что правая часть ~к+1 всегда определева, так как Ь" исключена из области оп- ределения Д"; следовательно, Ж (Ч" ) Н'. Необходимо установить три факта: ()" — отображепие иа Н"; 3: " ивъективио; " сюръектиено. ~" является отображением, если (хи ~ х ~1) (уи ° 1 ул+1) 0" ([(х, " х.+ )])- Р" ([(у " у.+ )]).
Пусть (хи ..., х„1) (уи ..., у„+~); тогда существует аж ЙЧО) такое, что х< ° ау, для всех г, т < [ ~ и+ [. Тогда по определепию 9'([(х„... х +1)1) = '2' ([ау1 ' 1 ..., ау„+,)1) — (ау„..., ау,) = — (у„...,у,)= ййи ее+ е„+, ч ([(у„ ..., у.,~)]). Следовательно, 0" — отображеппе па Н". ()" ивъектпвио, если Д" ([х]) ()" ([у]): х-у. Запи- сывая выражевие для х к у в виде х (хи ..., х, х„~~) и у (уи ..., у., у +~), получаем Е" ([ 1) = О" ([у]),— '(, .", ") - — '(у„..., у.), ек+д ук+1 откуда х (х +~/у.+1)у ч х-у, а х.+1/у,+ь Следова- тельно, Д' икъективно. Г)" сюръектпвно, если для всех х (хи ..., х„)ж И" сущестует хежЙ"+' такое, что ч"([хе]) х.
Если опре- делим х* -(хн ..., х„, 1)ж И"+', тогда очевипио„что ~" ([хе]) х, т. е. 9" сюръективио. е П р и и е р 1,2. Одпородпые коордппаты в й" (и ю М)' Однородные координаты е К" определяют как отображеппе К" ва гт'", имеющее обратное отображение «)", так что Ф: К" Н", где Ф («)") '. Другими словами, однородными коордппатамп точки (хц ..., х„)«и К" являются (и+1)-мерпые паборы классов эквивалентности [(хц ..., х., 1)] ((рх„..., рх., р): р Ф 0). | Э лемевт иа [(хь ..., х., 1)] вазывают однородным представлением для (хц ..., х ).
Часто бывает удобно представить в компьютере гео метрические данные в одвородвой форме (см. 1 3). Что. бы из однородных коордипат получить физические, осу гцествим отображепие (х„..., х„+,) — (х„..., х,). «ь! Сформулированное выше предложение показывает, что все однородные представления данкой физической точки имеют те лсе самые физические координаты. Чтобы проясвить ситуацию, рассмотрим геометрическую ивтерпретацшо однородных координат в К.
Случай более высоких размеркох« стэй имеет подобную гео- клее« ме«ха метрическую иптерпретале«г«лег"«цию однако ее нелегко 1 (02 зйе Р изобразить ва рисунке. Элемевты Р' являются бесконечными ливиями в К', проходящими через качало координат, одпако хг начало коордипат выброшево (рпс. 10.2). Испо, что еди , бесковечпо удалеппой точкой Рвс, 10.2 будет ось Ох1 с выбро- шенным вачалом коордиват. Рпс. 10.3 проясвяет попятие «бесконечно удаленпая точка з Р' ° . Точки па ливии Ь„ [(и, 1)] являются одпородвым представлением л и й. Из рве. 10.3 впдпо, что при п - прямая Ь„ стремится к бескопечво удаленной точке Ь .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
