convex_hull.cpp

#include <iostream>
#include <fstream>
#include <vector>
#include <time.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>

using namespace std;
typedef int TypeOfPoint; // Тип точки
typedef pair<TypeOfPoint, TypeOfPoint> Point; // Точка
typedef vector<Point> Points; // Вектор из точек
typedef vector<Point*> ConvexHull; // Выпуклая оболочка (указатели на точки)

void add_to_ConvexHull(ConvexHull &, Point * p); // Добавление точки в выпуклую оболочку
void create_ConvexHull(ConvexHull &, Points &); // Создание выпуклой оболочки из вектора точек
void print_Points(const Points &); // Вывод вектора точек на экран
void print_ConvexHull(const ConvexHull &); // Вывод выпуклой оболочки на экран
void printf_ConvexHull(const ConvexHull &, const string &); // Вывод выпуклой оболочки в файл

int main(){
    ifstream fin("in.txt"); // Открываем файл для чления
    if (!fin) return 1;

    Points v; // Вектор, хранящий точки

//  Считываем точки из файла:
    for(TypeOfPoint x, y; fin>>x>>y; v.push_back(Point(x, y)));

    ConvexHull hull; // Выпуклая оболочка
    create_ConvexHull(hull, v); // Создаем выпуклую оболочку из вектора точек

    printf_ConvexHull(hull, "out1.txt"); // Выводим в файл
    return 0;
}

void create_ConvexHull(ConvexHull & hull, Points & v){
//  Создание выпуклой оболочки из вектора точек на плоскости
    for(int i = 0, n = v.size(); i < n; i++){
        add_to_ConvexHull(hull, &v[i]);
        //print_ConvexHull(hull); // Раскомментировать, если нужен вывод промежуточных результатов на экран
    }
}

void add_to_ConvexHull(ConvexHull & hull, Point* p){
//  Добавление точки к уже существующей выпуклой оболочке

//  Используемые функции:
    void add_to_zero(ConvexHull &, Point*); // Добавление к пустой оболочке (1)
    void add_to_one(ConvexHull &, Point*); // Добавление к оболочке, состоящей из одной точки (2)
    void add_to_two(ConvexHull &, Point*); // Добавление к оболочке, состоящей из двух точек (3)
    void add_to_other(ConvexHull &, Point*); // Добавление к оболочке, состоящей из множества точек (4)

//  Выбираем случай, исходя из размера оболочки:
    switch(hull.size()){
        case 0:  add_to_zero(hull, p);  break; // Случай 1
        case 1:  add_to_one(hull, p);   break; // Случай 2
        case 2:  add_to_two(hull, p);   break; // Случай 3
        default: add_to_other(hull, p); break; // Случай 4
    }
}

double det(const Point * a, const Point * b){
//  Подсчет определителя, первой строкой которого идут координаты точки a, второй строкой - координаты точки b
    return (a->first * b->second - b->first * a->second);
}

double square_triangle(const Point * a, const Point * b, const Point * c){
//  Подсчет ориентированной площади треугольника, состоящего из вершин a, b и c
    return ((det(a,b)+det(b,c)+det(c,a))/2.0);
}

void add_to_zero(ConvexHull & hull, Point * p){
//  Добавление указателя на точку к пустой выпуклой оболочке
    hull.push_back(p);
}

void add_to_one(ConvexHull & hull, Point * p){
//  Добавление указателя на точку к выпуклой оболочке, состоящей из одной точки

//  Сравниваем уже имеющуюся точку с новой точкой. Если не совпадают, то добавляем
    if (*hull[0] != *p) hull.push_back(p);
}

void add_to_two(ConvexHull & hull, Point * p){
//  Добавление указателя на точку к выпуклой оболочке, состоящей из двух точек

//  Считаем ориентированную площадь треугольника, состоящего из точек в оболочке и новой точки
    double sq = square_triangle(hull[0], hull[1], p);

//  Объявим используемую функцию для проверки принадлежности к отрезку:
    bool in_interval(const Point *, const Point *, const Point *);

//  Если площадь равна нулю, то проверяем, лежит ли новая точка на отрезке, соединяющем две точки выпуклой оболочки
    if (sq == 0 ){
//      Объявим используемую функцию для вычисления расстояния между двумя точками:
        double dist(const Point *, const Point *);

        if (!in_interval(hull[0], hull[1], p)) // Если новая точка не лежит на отрезке, но ориентированная площадь равна нулю
            if (dist(hull[0], p) > dist(hull[1], p)) // Если расстояние от новой точки до нулевой больше, чем от новой до первой
                hull[1] = p; // То заменяем первую точку на новую
            else // Иначе
                hull[0] = p; // Заменяем вторую точку на новую
        return; // Выходим из функции
    }

//  Добавляем обавляем точку в конец
    hull.push_back(p);

//  Если значение ориентированной площади отрицательно, то меняем местами точку вначале и вконце.
//  Это позволяет сохранить направление обхода против часовой стрелки.
    if (sq < 0) swap(hull[0], hull[2]);
}

void erase_ConvexHull(ConvexHull & hull, int a, int b){
//  Вырезает из выпуклой оболочки точки с позиции a до позиции b включительно
    int n = hull.size();

//  Объявим функцию, которая вычисляет целое значение переменной по модулю n:
    void to_0_n(int &, int);

    to_0_n(a, n); // Вычисляем a по модулю n
    to_0_n(b, n); // Вычисляем b по модулю n

    if (a > b) // Если левый конец отрезка больше правого, то выходим из функции
        return;

    if (a == b) // Если начало совпадает с концом, то нам нужно вырезать только один элемент
        hull.erase(hull.begin()+a);
    else // Иначе вырезаем весь отрезок
        hull.erase(hull.begin()+a, hull.begin()+b);
}

void to_0_n(int & val, int n){
//  Функция вычисляет значение val по модулю n
    if (val >= n) val %= n;
    if (val < 0) val = n - abs(val) % n;
}

void inc_to_0_n(int & val, int n){
//  Функция увеличивает значение val, а затем вычисляет его по модулю n
    ++val;
    to_0_n(val, n);
}

void dec_to_0_n(int & val, int n){
//  Функция уменьшает значение val, а затем вычисляет его по модулю n
    --val;
    to_0_n(val, n);
}

void shift_left(ConvexHull & hull, int k){
//  Сдвигает все элементы выпуклой оболочки на k позиций влево
    reverse(hull.begin(), hull.begin()+k-1);
    reverse(hull.begin()+k, hull.end());
    reverse(hull.begin(),hull.end());
}

void shift_right(ConvexHull & hull, int k){
//  Сдвигает все элементы выпуклой оболочки на k позиций вправо
    shift_left(hull, hull.size()-k+1);
}

double dist(const Point * A, const Point * B){
//  Вычисляет расстояние от точки A до точки B

//  Вычтем точку A из точки B:
    Point C(B->first - A->first, B->second - A->second);

//  Возводим каждую компоненту в квадрат, суммируем и извлекаем корень:
    return (sqrt(pow(C.first, 2)+pow(C.second, 2)));
}

bool in_interval(const Point * A, const Point * B, const Point * C){
//  Проверяет, принадлежит ли точка C отрезку AB
//  Точка C точно не принадлежит этому отрезку, если сумма расстояний от его концов до точки C больше длины отрезка

//  Функция, вычисляющая длину отрезка:
    double dist(const Point*, const Point*);

//  Вычисляем длины отрезков AC, BC и AB:
    double AC = dist(A, C);
    double BC = dist(B, C);
    double AB = dist(A, B);

//  Проверяем условие принадлежности:
    return (AC + BC == AB);
}

void add_to_other(ConvexHull & hull, Point * p){
//  Добавляет новую точку к выпуклой оболочке, состоящей больше, чем из двух точек
//  cout << "adding "<< p->first << " " << p->second << " ..." << endl;
//  print_ConvexHull(hull);
    pair<int, int> interval[] = {pair<int, int>(-1, -1), pair<int, int>(-1, -1)};
    int n = hull.size(), cur = 0;
    for(int i = 0; i < n; i++){
//      Вычислим индекс j точки, следующей сразу за текущей точкой:
        int j = i + 1;
        to_0_n(j, n);

//      Посчитаем ориентированную площадь треугольника, образованного точками hull[i], p, hull[j]
        double sq = square_triangle(hull[i], p, hull[j]);
        if (sq == 0 && in_interval(hull[i], hull[j], p)) // Если она равна нулю и точка лежит на отрезке между точками hull[i] и hull[j]
            return; // То выходим из функции

//      С этого момента мы считаем, что отрезок [i, j] выпуклой оболочки необходимо модифицировать

        if (sq >= 0){ // Если значение площади не отрицательно
//          Если еще не задан текущий отрезок, который нам нужно модифицировать в выпуклой оболочке
            if (interval[cur].first == interval[cur].second)
                interval[cur] = pair<int, int>(i, j); // То задаем его
            else if (interval[cur].second == i) // Иначе, если конец текущего отрезка совпадает с началом полученного отрезка [i, j]
                interval[cur].second = j; // Концом текущего отрезка становится конец полученного (то есть к концу текущего отрезка прибавляется полученный)
            else if (interval[cur].first == j) // Иначе, если начало текущего отрезка совпадает с концом полученного отрезка [i, j]
                interval[cur].first = i; // Началом текущего отрезка становится начало полученнго (то есть к началу текущего отрезка прибавляется полученный)
            else // Иначе, полученный отрезок [i, j] становится вторым отрезком, который необходимо модифицировать, и сразу же текущим
                interval[++cur] = pair<int, int>(i, j);
        }
    }

//  На выходе мы имеем два отрезка, которые необходимо соединить в один, если совпадают конец второго и начало первого:
    if (interval[1].second == interval[0].first)
        interval[0].first = interval[1].first;

//  Теперь мы будем рассматривать один целый отрезок [begin, end]
    int begin = interval[0].first;
    int end = interval[0].second;

//  Вычисляем его длину по модулю n:
    int len = (end - begin);
    to_0_n(len, n);

    if (begin > end && end != 0) { // Если начало отрезка больше конца
        shift_left(hull, end); // То сдвигаем все элементы оболочки влево на величину, равную концу отрезка
        begin -= end;
        end -= end;
    }

//  Крайние точки мы должны оставить в покое, поэтому:
    inc_to_0_n(begin, n); // Увеличиваем на единицу начало отрезка
    dec_to_0_n(end, n); // Уменьшаем на единицу конец отрезка

    switch (len){ // В зависимости от длины отрезка
        case 0: return; // Ничего не делаем, если длина отрезка равна 0
        case 1: hull.emplace(hull.begin()+begin, p); break; // Вставляем новую точку, если длина отрезка равна 1
        case 2: hull[begin] = p; break; // Заменяем точку, расположенную вначале отрезка, на новую точку
        default:
            hull[begin] = p; // Заменяем точку вначале отрезка на новую точку
            inc_to_0_n(begin, n); // Увеличиваем начало отрезка
            erase_ConvexHull(hull, begin, end); // Вырезаем все остальные точки из отрезка [begin, end]
            break;
    }
}

void print_Points(const Points & v){
//  Вывод на экран вектора из точек
    for(int i = 0, n = v.size(); i < n; i++)
        cout<<"("<<v[i].first<<";"<<v[i].second<<") ";
    cout<<endl;
}

void print_ConvexHull(const ConvexHull & hull){
//  Вывод на экран выпуклой оболочки, состоящей из указателей на точки
    for(int i = 0, n = hull.size(); i < n; i++)
        cout<<"("<<hull[i]->first<<";"<<hull[i]->second<<") ";
    cout<<endl;
}

void printf_ConvexHull(const ConvexHull & hull, const string & filename){
//  Вывод в файл выпуклой оболочки, состоящей из указателей на точки
    ofstream fout(filename);
    for(int i = 0, n = hull.size(); i < n; i++)
        fout<<hull[i]->first<<" "<<hull[i]->second<<endl;
}