Здравствуйте, greenpci, Вы писали:

G>Конвекс Хал — даются точки, надо их обвязать, как бы, резинкой вокруг.

"Выпуклая оболочка", дорогой Ватсон!

G>Я придумал свой алгоритм (велосипед), реализовал на плюсах, опубликовал в гит хабе. Даже написал описание алгоритма с картинками. Все в академических целях. Помогите, пожалуйста. Сделайте код ревью. Код не длинный, должен быть понятен.

G>Цель: читабельность, легкая модификация (расширение) в будущем, быстродействие в рамках разумного, но не в ущерб всему остальному.

G>Программа консольная. Берет файл с картинкой, окружает точки конвекс халом, сохраняет результат в другой файл. Екзешник, кстати, проверен софтпедией, вирусов и малваре нету. Смотрите там есть ссылка на сертификат.

Есть ряд моментов, которые стоит отшлифовать.
1. Странное разбиение на файлы:
— исключение в common.h, почему бы не в ch_exception.h?
— SharedPoint опять в common.h, тогда как PointVector и SharedPointVector — в point.h, а PointList и SharedPointList — в convex_hull.h

2. По-моему, изрядный перебор с абстрагированием. Особенно странно он смотрится в сочетании с типами контейнеров, прибитыми гвоздями.
Интерфейс можно было как-то попроще сделать

struct Point { int x, y; }; // для начала, зафиксируем тип точки
// в будущем можно его сделать произвольным - а алгоритм, соответственно, полиморфным

// для тех, кому нравится работать с произвольными контейнерами:
template<class InIter, class OutIter>
OutIter convex_hull(InIter begin, InIter end, OutIter dst)
{
  std::vector<Point> points(begin, end);
  do_convex_hull(points);
  std::copy(points.begin(), points.end(), dst);
}

// нешаблонная функция - реализацию можно вынести в отдельный .cpp
// тип рабочего контейнера зафиксирован - vector<Point>
// (в будущем можно сделать произвольным - например, vector<void*>
//  плюс передавать стратегию для работы с точками: функции
//  get_x(void const*), get_y(void const*), remove(void*)
// )
void do_convex_hull(std::vector<Point>& points)
{
  // отсортировать в полярных координатах
  // удалить точки, образующие вогнутые углы
}

3. Можем подумать об инкрементных алгоритмах.
Если все точки поступают на вход, отсортированные по y и x (по сканлиниям), то выпуклую оболочку можно наращивать.
— для верхней-левой точки оболочка тривиальна и состоит из неё
— для оболочки, состоящей из левой и правой полилиний, новая точка либо просто добавляется к полилиниям, либо заставляет последовательно отбросить некоторые предыдущие вершины (образующие вогнутую дугу) и, опять же, добавляется
То есть, нам потребуются два вектора.

struct ConvexHullBuilder
{
  std::vector<Point> left, right;
  void add(Point pt);
};

4. shared_ptr'ы нигде не нужны. Откройте для себя передачу аргументов по ссылке


То есть, моё мнение: код нужно переделать вдребезги пополам
Либо очень тщательно обосновать каждый пункт: зачем ЭТО сделано ТАК и вынесено СЮДА (или не вынесено, а помещено в общую кучу).