Геометрические объекты

Эта статья-вторая в цикле моих статей, посвящённых вычислительной геометрии.Предыдущая была посвящена общим и некоторым историческим сведениям теории алгоритмов и вычислительной геометрии. В ней были описаны понятия комбинаторной геометрии и теории выпуклости.Данная статья будет посвящена строгому математическому описанию геометрических объектов.
По-прежнему,Ваши предложения и замечания я жду по адресу:shershzzz@mail.ru. Шморгун Евгений,ДонНТУ

Мы формируем наши взгляды в том возрасте, когда менее всего способны что-либо понимать.
Георг фон Лихтенберг

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

1.Общие обозначения и термины

Геометрические объекты, с которыми имеет дело вычислительная геометрия, обычно представляются множествами точек в евклидовом пространстве.Имеется некоторая ситема координат,в которой каждая точка рассматриваемого нами геометрического объекта представима набором или,как говорят, вектором координат.Если Вы предпочитаете обобщения, то, в принципе, алгоритмы ,которые будут рассмотрены в дальнейшем могут быть распространены на любое число измерений без особых трудностей. Почему же тогда предпочитают изложение в рамках евклидового, а не какого-либо иного пространства? Причина состоит в том, что задачи, которые сформировали теорию алгоритмов и вычислительную геометрию были поставлены перед человечеством задолго до работ Лобачевского,Гаусса и Бойяи.Другими словами, при изложении вполне возможно пользоваться для усвоения понятий собственной геометрической интуицией, которая была приобретена нами после рождения.А это отнюдь немаловажный факт для решения большинства прикладных задач, поскольку отвлечённая математическая формулировка о объёме пятимерного куба будет весьма не кстати при ,скажем, вычислении объёма земляных работ.

Вообще говоря, геометрические объекты не обязаны состоять именно из конечных множеств.Но описаны они должны быть конечным образом.Причина этого-критическое время исполнения алгоритма, к чему я впоследствии вернусь.Требование конечности описания объектов позволяет нам рассматривать прямую линию, содержащую две точки;отрезок прямой линии, определённый парой своих конечных точек;плоскость, содержащую три заданные точки;многоугольник,состоящий их упорядоченной последовательности точек...Далее можете продолжать сами.

Итак...

Пусть E^d d-мерное евклидово пространство, или пространство d-плексов (x₁,...,x_d),состоящих из действительных чисел x_i=1,...,d, с расстоянием .Определим теперь важнейшие для нашего рассмотрения объекты вычислительной геометрии.

• Точка.Точкой р в пространстве E^d называется d-плекс (x₁,...,x_d).Эту точку можно итнтерпретировать как d-многокомпонентный вектор, исходящий из начала координат в E^d ,свободным концом которого является точка р .
• Прямая,плоскость,линейное многообразие.Пусть даны две разные точки q₁ и q₂, принадлежащие E^d;тогда линейная комбинация
  aq₁+(1-a)q₂,(a принадлежит R)
  называется прямой в E^d.В общем случае для заданных k линейно независимых точек q₁,...,q_r,принадлежащих E^d(k<=d),линейная комбинация
  
  называется линейным многообразием размерности (k-1) в E_d.
• Отрезок.Пусть даны две разные точки q₁ и q₂, принадлежащие E^d;тогда линейная комбинация
  aq₁+(1-a)q₂
  при условии 0<=a<=1 определит выпуклую комбинацию для q₁ и q₂.Эта выпуклая комбинация описывает прямолинейный отрезок,соединяющей две точки: q₁ и q₂.Принято обозначать этот отрезок .
• Выпуклое многообразие.Область D,принадлежащая пространству E^d, называется выпуклой, если для любой пары точек q₁ и q₂ из D отрезок целиком принадлежит D.Можно доказать, что пересечением выпуклых областей является выпуклая область.
• Выпуклая оболочка.Выпуклой оболочкой множества точек S,принадлежащих пространству E^d, называется граница наименьшей выпуклой области в E^d,которая охватывает S.
• Многоугольник.Многоугольником в пространстве E^d называется конечное множество отрезков, в котором каждый конец отрезка принадлежит ровно двум отрезкам и никакое подмножество этих отрезков не обладает указанным свойством.Эти отрезки принято называть сторонами(рёбрами),а их концы-вершинами многоугольника. Многоугольник называется простым, если никакая пара последовательных его ребер не имеет общих точек.Простой многоугольник разбивает плоскость на две неперсекающиеся области- внутреннюю(конечную) и внешнюю(бесконечную),которые разделены этим многоугольником(теорема Жордана).

Таким образом, я рассмотрел с Вами важнейшие объекты вычислительной геометрии с точки зрения математики.В следующей статье я сформулирую более сложные ,на мой взгляд, определния графа, триангуляции и полиэдра. Эти определения будут опираться на известные Вам из курса дискретной математики сведения и пригодятся нам для дальнейшего изучения нашего вопроса.Так же Вам стоит припомнить Object Pascal, поскольку помимо изложения математического материала, я намерен представить конкретный программный код ,который мы с Вами создадим в процессе чтения и изучения статьи. Также не лишним будет Вам загрузить на Ваш компьютер из Интернета VRML-клиент фирмы ParallelGraphics Cortona VRML Client с сайта этой фирмы www.parallelgraphics.com. Это понадобится для более полноценного представления материала, который я Вам предлагаю. Почему именно этот плагин и именно этой фирмы?Причина проста-я располагаю SDK именно для Cortona и на располагаю другим.Если у Вас есть некоторый опыт в программировании,то тот программный код,который я Вам предложу, совсем не сложно будет распространить на средства того VRML-клиента,который Вам больше нравится.Но, ещё раз повторюсь, лучше загрузить именно этот клиент,так как он и самый маленький из всех известных ,так и самый быстрый.
Удачи!