Проект «Выпуклая оболочка» реализует исполнителя, вычисляющего некоторые геометрические характеристики (периметр и площадь) выпуклой оболочки последовательно поступающих точек плоскости.
Выпуклая оболочка множества точек плоскости — это минимальное выпуклое множество, содержащее все заданные точки.
Точки поступают друг за другом и в любой момент времени исполнитель должен знать периметр и площадь выпуклой оболочки уже поступивших точек.
В исполнителе хранятся не все поступившие точки, а только вершины выпуклой оболочки. Это означает, что при поступлении новой точки выпуклая оболочка перевычисляется: если новая точка оказалась внутри или на границе имеющейся выпуклой оболочки, то выпуклая оболочка не меняется; если новая точка оказалась снаружи имеющейся выпуклой оболочки, то вычисляются вершины новой выпуклой оболочки.
Перевычисление выпуклой оболочки происходит по следующему алгоритму. Определяется, какие ребра старой выпуклой оболочки окажутся внутри новой, эти ребра удаляются из выпуклой оболочки, а в нее добавляются два новых ребра, выходящих из новой точки.
Если в новую точку поместить лампочку, то она осветит удаляемые ребра выпуклой оболочки. Будем называть эти ребра освещенными из новой точки.
Для определения того, является ли ребро освещенным, используется вычисление ориентированной площади треугольника, образованного этим ребром и добавляемой точкой. Если ребра выпуклой оболочки ориентированы против часовой стрелки, то ребро AB освещено из точки T тогда и только тогда, когда S(ABT) < 0 или (S(ABT) = 0 и точка T вне отрезка AB).
Ориентированная площадь треугольника ABT считается как половина площади параллелограмма, натянутого на вектора TA и TB:
S(ABT)=((A.X-T.X)*(B.Y-T.Y) – (A.Y-T.Y)*(B.X-T.X))*0.5
Точки выпуклой оболочки хранятся в структуре данных дек R2 точек.
Текущим ребром будем называть ребро, образованное точками, находящимися в начале и в конце дека.
Обход точек выпуклой оболочки совершается в направлении от начала к концу дека, то есть переход к следующему ребру делается перемещением точки из начала дека в его конец.
При добавлении к выпуклой оболочке новой точки в деке ищется освещенное ребро. Если оно не находится, то считается, что точка находится внутри выпуклой оболочки и обработка на этом заканчивается.
Если же при поиске оказывается, что текущее ребро освещено, то мы должны удалить все освещенные ребра, которые находятся перед ним и после него, и учесть изменение периметра и площади выпуклой оболочки.
Вот программа удаления освещенных ребер перед текущим ребром:
Цикл пока ребро <Д.конец,Д.начало> освещено из точки T выполнять
Периметр -= длина ребра <Д.конец,Д.начало>
Площадь += площадь треугольника <Д.конец,Д.начало,T>
Д.удалить начало
Число ребер -= 1
Конец цикла
Аналогично удаляются освещенные ребра за текущим ребром.
Реализация выпуклой оболочки на языке C++ (В.В.Борисенко): R2Conv.h
В этой реализациии в классе R2Convex многоугольник, образующий выпуклую оболочку, хранится в объекте m_Polygon класса R2Polygon.
В свою очередь, точки многоугольника в классе R2Polygon хранятся в объекте m_Deq класса R2PointDeq, реализущего дек R2 точек.
Реализация дека R2 точек R2PointDeq находится в файле PointDeq.h. Дек реализован на базе массива m_Elements, реализация непрерывная, циклическая. Индекс элемента массива, являющегося началом дека, хранится в переменной m_Begin. Индекс конца дека хранится в m_End. Элементы дека размещаются в элементах массива, начиная с индекса m_Begin и заканчивая индексом m_End.
Обход точек дека осуществляется при помощи классов R2Convex::iterator и R2Convex::const_iterator. Реализация этих итераторов использует точки m_A и m_B, если число вершин меньше 3, и итераторы многоугольника m_Polygon, если число вершин больше или равно 3.
В свою очередь, итераторы многоугольника R2Polygon::iterator и R2Polygon::const_iterator базируются на классах R2PointDeq::iterator() и R2PointDeq::const_iterator() соответственно.
Простая программа, которая использует реализацию класса R2Conv (В.В.Борисенко): convtst.cpp
Графический интерфейс проекта «Выпуклая оболочка» реализован В.В.Борисенко на базе проекта GWindow (В.В.Борисенко): convmain.cpp
Класс MyWindow базируется на классе GWindow, виртуальные функции OnExpose(), OnKeyPress() и OnButtonPress() переопределены следующим образом:
- в функции OnExpose() рисуется выпуклая оболочка, выводятся ее периметр и площадь;
- при нажатии левой клавиши мыши - в функции OnButtonPress() в выпуклую оболочку добавляется точка с координатами, соответствующими положению мыши, вызывается функция перерисовки окна redraw(), что влечет за собой вызов функции OnExpose();
- при нажатии средней клавиши мыши - в функции OnButtonPress() выпуклая оболочка делается пустой;
- при нажатии клавиши «q» - в функции OnKeyPress() программа прекращает работу;
1. Кушниренко А.Г., Лебедев Г.В. Программирование для математиков: Учеб. пособие для вузов — М.: Наука. Гл.ред.физ.-мат.лит., 1988