Многолистная фигура и ее медиальные дескрипторы

• Автор: Мехедов, Иван Сергеевич
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Москва
• Количество страниц: 136 с. : ил.

1. Определение многолистной фигуры и ее медиальных дескрипторов
1.1 Плоская фигура и ее медиальные дескрипторы
1.1.1 Плоская фигура, её срединная ось, радиальная функция и
медиальная функции
1.1.2 Диаграмма Вороного многоугольной фигуры
1.1.3 Граф Делоне многоугольной фигуры
1.1.4 Связь между срединной осыо, диаграммой Вороного и графом
Делоне многоугольной фигуры
1.2 Многолистная фигура, ее срединная ось, радиальная и медиальная
функции
1.2.1 Лоскутная поверхность
1.2.2 Многолистная плоская фигура
1.2.3 Разбиение многолистной фигуры
1.2.4 Срединная ось многолистной фигуры
1.2.5 Радиальная функция многолистой фигуры
1.2.6 Медиальная функция многолистой фигуры
1.3 Многоугольная многолистная фигуры, ее диаграмма Вороного и граф
Делоне
1.3.1 Диаграмма Вороного многоугольной многолистной фигуры
1.3.2 Граф Делоне многоугольной многолистной фигуры
1.3.3 Связь между срединной осью, диаграммой Вороного и графом
Делоне многоугольной многолистной фигуры

2. Вычисление медиальных дескрипторов многоугольной многолист-ной фигуры
2.1 Вычисление медиальных дескрипторов плоской фигуры
2.2 Вычисление срединной оси, диаграммы Вороного, радиальной и медиальной функций многоугольной многолистной фигуры
2.3 Построение графа Делоне многоугольной многолистной фигуры
2.3.1 Построение графа Делоне многоугольной многолистной фигуры относительно разбиения мощности 2
2.3.2 Построение графа Делоне многоугольной многолистной фигуры относительно разбиения произвольной мощности
3. Решение некоторых прикладных задач на основе вычисления медиальной функции многоугольной многолистной фигуры
3.1 Преобразование геометрического представления пространственных
данных в ГИС
3.2 Свертка площадных объектов в линейные
3.3 Преобразование общего полигонального представления улично-дорожной сети к линейному представлению
3.4 Преобразование общего полигонального представления уличнодорожной сети к содержательному полигональному представлению
3.5 Вычислительный эксперимент и внедрение результатов
Заключение
Обозначения
Список литературы

Актуальность темы. Понятие срединной оси1 плоской фигуры было впервые введено в конце 1960-х годов Блюмом[5]. Он показал, что срединная ось объекта, присутствующего на двумерном изображении, может использоваться для эффективного описания формы объекта, его геометрической структуры, что положило начало теории медиального представления формы.
Срединная ось плоской фигуры представляет собой множество внутренних точек фигуры, каждая из которых имеет, по меньшей мере, две ближайшие граничные точки (рис. 0.1). Каждая точка срединной оси фигуры является центром вписанного в фигуру круга, т.е. круга, все внутренние точки которого лежат внутри фигуры, а граница касается границы фигуры в двух или более точках. Медиальное представление фигуры задается множеством пар (р, г), где р — центр, а г — радиус круга. Само же множество пар (р, г) называется медиальной функцией плоской фигуры, а зависимость радиуса круга г от точки срединной оси р — радиальной функцией плоской фигуры. Срединная ось, радиальная и медиальная функции плоской фигуры названы в работе медиальными дескрипторами плоской фигуры.
С начала 1970-х годов стали появляться работы, так или иначе связанные с понятием срединной оси фигура. При этом можно выделить
хот англ. medial axis; в русскоязычной литературе зачастую срединная ось называется скелетом, хотя скелет является более общим понятием, включающим в себя как срединную ось, так и прямолинейный скелет [2, 31], криволинейный скелет [9], а также скелет бинарного изображения [38].

имнооднозначное соответствие. Порождающий сайт ячейки Вороного будем также называть порождающим, сайтом лоскута Вороного, который при проекции переходит в эту ячейку. Очевидно, что ячейка Вороного содержит свой порождающий сайт, равно как и лоскут Вороного содержит прообраз своего порождающего сайта.
Определение 1.43. Сайты многоугольной многолистной фигуры называются смежными относительно порождающей поверхности П, если их лоскуты Вороного имеют, по крайней мере, одну общую точку, не лежащую на границе П.
Замечание 1.8. Поскольку сайты, имеющие вырожденные ячейки Вороного, состоят из точек, лежащих на границе ф, то такие сайты, по Определению 1.43, не являются смежными никаким другим сайтам.
Утверждение 1.15. Пусть а и Ь не являются соседними. Тогда а и Ъ смежны тогда и только тогда, когда существует окружность Ог(х), касающаяся этих двух сайтов, и существует лоскут Т1Х С П, имеющий непустое пересечение с 7Г“1(а) И 7Г~1(6), причем Ог(х) = лг(0,х).
Доказательство. Пусть а и Ь — смежные и не соседние, следовательно, найдется некоторая точка шх Є Xу {а, Ь) такая, что х — лг(шх) Є Iу(а, Ь, П) является ближайшей граничной точкой для а и для Ь. Пусть ха Є а — ближайшая к х граничная точка относительно П и ша Є П, а хь Є Ь — ближайшая к х граничная точка относительно П и шь Є П. Обозначим Па и Д, — лоскуты, соответствующие максимальным окружностям с центром в точке х относительно П и точках ша и шь на ней, соответственно. Тогда 7г_1(жа) Є Па, тт~1(хь) Є Д,.
Поскольку ша и шь лежат на общем участке границы двух лоскутов в разбиении Вороного лоскутной поверхности, и 7гг(о;а) = л2(шь) = х, то ша = шь- Тогда из Утверждения 1.9 следует, что ха и Хь лежат