Примеры работы алгоритма и иллюстрации
Пример 1.
Пусть построена следующая выпуклая оболочка (см. левую часть рисунка):
|
|
|
|
Дерево, построенное для этой оболочки, изображено в центре. Справа изображена ситуация, имевшая место при вставке последней точки.
Выполним построение выпуклой оболочки в пошаговом режиме (выбрать пункт меню «Алгоритм»-> «Пошаговый режим», после чего для выполнения очередного шага построения оболочки использовать или пункт меню «Алгоритм»->«Следующий шаг», или соответствующую кнопку панели инструментов).
Шаг 1
|
|
|
|
Добавляем новую точку; проводим прямые, соединяющие эту точку с минимальным элементом дерева (1) и корнем (5); определяем ситуацию. Минимальный элемент и корень можно определить по дереву. Минимальный элемент – элемент левого поддерева самого нижнего уровня.
На рисунке изображена ситуация №8. Это означает, что левую опорную точку следует искать в левом поддереве, а правую – в правом, считая корень дерева.
Шаг 2
|
|
|
|
Итак, левая и правая опорные точки расположены в разных поддеревьях. Сначала ищем левую вершину. Для этого проводим линию к корню левого поддерева и проверяем, является ли он опорной точкой. Дерево изображено в усеченном виде для того, чтобы было ясно, в каком поддереве осуществляется поиск опорной точки.
По рисунку выпуклой оболочки хорошо видно, что точка с идентификационным номером 3 является опорной, поэтому поиск левой опорной точки должен быть прекращен.
Шаг 3
|
|
|
|
Поиск правой опорной точки осуществляется в правом поддереве исходного дерева плюс корень.
Возвращаемся к исходному дереву. Проводим линию к корню. Проверяем: является ли он опорной точкой.
По рисунку видно, что точка, идентификационный номер которой равен 5, является опорной точкой.
Обе опорные точки найдены.
Шаг 4
|
|
|
|
После нахождения опорных точек определяется освещенная цепь - последовательность элементов, которые необходимо удалить из выпуклой оболочки. На рисунке с изображением выпуклой оболочки освещенная цепь обозначена зеленым цветом. В дереве удаляемые элементы перечеркнуты.
Шаг 5.
|
|
|
|
Выпуклая оболочка построена. Отображаем все точки и новое дерево после расцеплений, удаления старых вершин и сцепления.
Пример 2.
Рассмотрим ситуацию, когда опорные точки определяются не сразу.
Пусть построена следующая выпуклая оболочка:
Шаг 1
|
|
|
|
Добавляем новую точку; проводим прямые, соединяющие эту точку с минимальным элементом дерева (1) и корнем (2); определяем ситуацию.
На рисунке изображена ситуация №8. Это означает, что левую опорную точку следует искать в левом поддереве, а правую – в правом, считая корень дерева.
Шаг 2
|
|
|
|
Ищем левую вершину. Для этого проводим линию к корню левого поддерева и проверяем, является ли он опорной точкой. В центре рисунка изображено только левое поддерево исходного дерева, т.к. именно в нем осуществляется поиск опорной точки.
По рисунку выпуклой оболочки (слева) видно, что точка с идентификационным номером 1 является опорной.
Шаг 3
|
|
|
|
Поиск правой опорной точки осуществляется в правом поддереве исходного дерева плюс корень.
Проводим линию к корню. Проверяем: является ли он опорной точкой. В данном случае корень (элемент с номером 2) не является опорной точкой. Дальше поиск будет осуществляться непосредственно в правом поддереве. Дальнейшая область поиска выделена красным цветом. Продолжаем поиск.
Шаг 4
|
|
|
|
Проводим прямую к корню правого поддерева. Определяем, является ли элемент с номером 5 опорной точкой. Снова не опорная точка. Точка 5 является вогнутой точкой. Это значит, что дальнейший поиск правой опорной точки должен выполняться в левом поддереве. Выделяем левое поддерево красным цветом.
Шаг 5.
|
|
|
|
Проводим прямую к корню левого поддерева (элемент 4). На этот раз точка является опорной. Поиск закончен.
Шаг 6
|
|
|
|
Шаг 7
|
|
|
|
Выпуклая оболочка построена.