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

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

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

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

да, правильно. Я представлял что выпуклый корпус (hull — the body or frame of a ship, most of which goes under the water (Cambridge Dictionary), но оболочка гораздо лучше.

...

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

Принимаю. Вспоминаю, сам чувствовал вину, когда разместил в common.h вместо отдельного файла. В C# обычно правила жесткие — каждый клас, интерфейс, даже нестед в отдельный файл. В си плюс плюс также надо похоже.

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

К>struct Point { int x, y; };

// для начала, зафиксируем тип точки
К>// в будущем можно его сделать произвольным — а алгоритм, соответственно, полиморфным

Я использовал инкрементальный алгоритм, как ты говорил ниже. Мотивация моя была в следующем: меньше памяти (ведь точек может быть очень много) и не надо делать два прохода: сохранить точки в векторе, пройтись по ним для нахождения выпуклой оболочки. Я 1*N сэкономил этим, не считая расширения вектора при вставке (чтобы обойти расширение, мне бы пришлось объявлять вектор на все точки — увеличить потребление памяти в два раза).

Ты тоже упоминаешь инкрементальный алгоритм ниже, тольео у тебя "Push", а у меня "Pull". Сказались годы работы на шарпе с его IEnumerable. Ты считаешь этот интерфейс (см ниже) перебор с абстрагированием? Хм... Возможно. Я просто думал, как же си шарпный IEnumerable<Point> на плюсах сделать. Ничего лучшего чем это не придумал.

class PointQueue
{
public:
  SharedPoint NextPoint()
  {
    return NextPointInternal();
  }
};

Прибитые гвоздями — это похоже про shared_ptr. Обосную ниже.

К>// для тех, кому нравится работать с произвольными контейнерами:
К>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);
К>}

Хороший интерфейс, а ля STL. Только слишком много N добавляет. Два копирования. Кстати в моей первой версии кода я тоже передавал vector. Потом поменял на "Pull-IEnumerable" при мыслях о производительности и памяти.

К>// нешаблонная функция — реализацию можно вынести в отдельный .cpp
К>// тип рабочего контейнера зафиксирован — vector<Point>
К>// (в будущем можно сделать произвольным — например, vector<void*>
К>// плюс передавать стратегию для работы с точками: функции
К>// get_x(void const*), get_y(void const*), remove(void*)
К>// )
К>void do_convex_hull(std::vector<Point>& points)
К>{
К> // отсортировать в полярных координатах
К> // удалить точки, образующие вогнутые углы
К>}
К>[/c]
По поводу void* тут сразу два нарушения:
C++ Coding Standards 101 Rules by Alexandresku and Sutter
90. Avoid type switching; prefer polymorphism
92. Avoid using reinterpret_cast

Я думаю все плюсники эту книжку должны любить пламенной любовью.

Хотя с другой стороны в дот нете WPF постоянно Object грызет. Не type safe нифига.

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

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

Это твой "Push" как я понимаю. То есть код, читающий точки, должен будет получить ConvexHullBuilder. Тебе не кажется, что это нарушение Rule Of Demeter (Least knowledge) и Separation of Concern. Получается, что тот код будет tightly coupled с конвекс халом. А что если я захочу просто точки получить для чего-нибудь другого, применяя тот же клас? Смысл моих абстракций вверху был "разлучить" код читающий точки и код делающий оболочку. Чтобы они были независимыми.

К>4. shared_ptr'ы нигде не нужны. Откройте для себя передачу аргументов по ссылке
C++ Coding Standards 101 Rules by Alexandresku and Sutter
79. Store only values and smart pointers in containers

Я не хотел передавать Point по значению, потому, что мой поинт был с двумя double — 16 байт. Копировать их при передаче значения было бы долго. Использовать референсы можно было бы, но у меня они уже должны были быть обернутыми в shared_ptr, из-за Александреску с его правилами (см. выше)
Еще вот это
virtual SharedPoint NextPointInternal() = 0;
не понятно как сделать без SharedPoint.

Ты в своем void add(Point pt) вообще копируешь по значению. Я кстати оставил double на будущее. Вдруг захотят дробные на вход подять.

К>То есть, моё мнение: код нужно переделать вдребезги пополам
блин, ты бы видел какой пишут код тут у нас. Поубивал бы.

По поводу книжки. Ищите в гугле:
C++ Coding Standards: 101 Rules, Guidelines, and Best Practices
By Herb Sutter, Andrei Alexandrescu