Основы теоретической робототехники. Теория толерантных пространств (обзор) — страница 8

  • Просмотров 246
  • Скачиваний 3
  • Размер файла 326
    Кб

отрезка, которые входят в разные касательные отрезки, т.е. неколлинеарны, то в таком террайне отсутствуют нетривиальные (т.е. состоящие более чем из одной точки) ядра видимости. Утверждение следует из теоремы, доказанной в [14], о представлении ядер видимости. Атлас возможных типов ядер видимости представлен на рис.5. Здесь изображены: (5a): "Веер" ядер у вершины p. Каждое ядро – полуинтервал, одно из граничных точек террайна

(второго типа), остальные из внутренних точек террайна (первого типа), с граничной точкой террайна– концом полуинтервала. (5b): Ядро первого типа – интервал. (5c): Усеченное ядро первого типа – отрезок – с граничной точкой террайна – одним из концов отрезка. (5d): В данной ситуации ядра не наблюдается. (5e): Невырожденное ядро второго типа, состоящее из одного или нескольких интервалов (случай несвязного ядра) граничных точек

террайна. (5f): Усеченное ядро второго типа, представляющее собой отрезок, входящий в состав граничного отрезка террайна. (5g): Разбиение ядра второго типа из-за ситуации типа "двойной замок". (5h): Ситуация типа "цепь": между компонентами несвязного ядра второго типа находятся ядра первого типа. Рис. 5. Атлас ядер Классом видимости называется максимальная область, все точки которой видимы одна из другой. Это понятие, также

как и понятие класса толерантности в общем случае [7, 8], является аналогом понятия клики на конечном графе. Класс видимости может быть связным или несвязным множеством. Нетрудно видеть, что несвязный класс видимости может быть гомоморфно отображен на полный граф. Справедливы следующие теоремы. Теорема о связных классах видимости. Связный класс видимости является выпуклым многоугольником, или (в вырожденном случае) касательным

отрезком, на котором наблюдается ситуация типа двойной замок. Если такой класс является выпуклым многоугольником, то каждая его сторона либо (а) входит в состав некоторого граничного отрезка препятствия, либо (б) на этой стороне расположены хотя бы одна замыкающая вершина, а если таких замыкающих вершин несколько, то ориентация их всех одинакова; при этом хотя бы одна сторона многоугольника удовлетворяет условию (б). Теорема о

несвязных классах видимости. Несвязный класс видимости состоит из конечного числа l≥3 связных непересекающихся компонент M1,...,Ml, каждая из которых может быть либо точкой, либо отрезком, либо выпуклым многоугольником. При этом существует n≤l(l-1)/2 связных классов видимости K1,...,Kn таких, что каждая компонента Mi является пересечением mi этих связных классов, где 2≤mi≤l-1. Если понятие ядра видимости является более "экзотическим"