Вычисление Выпуклой Оболочки


Этот вопрос задает для вычисления выпуклой оболочки множества 2D точек. Выпуклая оболочка состоит из нескольких последовательных отрезков, которые достаточно, чтобы накрыть все точки в этом районе. В этом упражнении я использую Джарвиса марта алгоритма.

Вот код:

#include <iostream>
#include <fstream>
#include <string>

#include <vector>
#include <algorithm>

using uint = unsigned int;

struct Vector2D
{   
    int x_;
    int y_;
    Vector2D() : x_(0), y_(0) {}
    Vector2D(int x, int y) : x_(x), y_(y) {}
    Vector2D operator+(const Vector2D & vec) const
    {
        return Vector2D(x_ + vec.x_, y_ + vec.y_);
    }
    Vector2D operator-(const Vector2D & vec) const
    {
        return Vector2D(x_ - vec.x_, y_ - vec.y_);
    }
};

using itVector2D = std::vector<Vector2D>::iterator;

enum RelativePosition { Clockwise, CounterClockwise };

RelativePosition ComparePosition(Vector2D target, Vector2D reference);
itVector2D findeNextVertex(std::vector<Vector2D> & coords, itVector2D itSource);

int main()
{
    std::ifstream file;
    file.open("data.txt");
    if (!file.is_open())
    {   
        std::cerr << "unable to open file" << std::endl;
        return -1;
    }

    // total number of points
    uint nPoints = 0;
    file >> nPoints;

    // creating data set
    std::vector<Vector2D> coords;
    coords.reserve(nPoints);

    // reading data set
    Vector2D temp;
    for (uint i = 0; i < nPoints; ++i)
    {
        file >> temp.x_ >> temp.y_;
        coords.push_back(temp);
    }

    // find the topmost
    itVector2D itTopMost = std::max_element(coords.begin(), coords.end(),
        [](const Vector2D & a, const Vector2D & b) { return a.y_ < b.y_; });



    // while it doesnt trace back to origin 
    // perform algorithm once to get to the next vertex
    itVector2D itCurrent = itTopMost;

    do
    {
        itCurrent = findeNextVertex(coords, itCurrent);
        std::cout << itCurrent->x_ << " " << itCurrent->y_ << std::endl;
    } while (itCurrent != itTopMost);

    return 0;
}

RelativePosition ComparePosition(Vector2D target, Vector2D reference)
{
    // compute determinant to determine if it is CW or CCW
    return reference.y_ * target.x_ - reference.x_ * target.y_ > 0 ? Clockwise : CounterClockwise;
}

// find next convex hull vertex
itVector2D findeNextVertex(std::vector<Vector2D> & coords, itVector2D itSource)
{
    for (itVector2D itTarget = coords.begin(); itTarget != coords.end(); ++itTarget)
    {
        // if itTarget is the same point as itSource, skip this case
        if (itTarget == itSource)
        {
            continue;
        }

        // assume itTarget is counterclockwise to all itReference
        bool allCC = true;

        // for other cases, find out if itTarget is counter-clockwise to all the itReference
        for (itVector2D itReference = coords.begin(); itReference != coords.end(); ++itReference)
        {   
            if (itReference == itTarget || itReference == itSource)
            {
                continue;
            }

            Vector2D vecTarget = *itTarget - *itSource;
            Vector2D vecReference = *itReference - *itSource;

            if (ComparePosition(vecTarget, vecReference) != CounterClockwise)
            {
                allCC = false;
                break;
            }
        }

        // if this itTarget is counter-clockwise to all the itReference
        if (allCC)
        {
            return itTarget;
        }

    }
}

Я испытал один набор данных ниже (назван "data.txt" в Кодексе), что является правильным.

12
5 19
33 2
-5 88
54 5
12 13
18 39
15 42
17 -5
-3 23
9 29
-8 17
-1 25

Я очень новой для C++, так что любая обратная связь приветствуется. Вот некоторые вопросы, которые у меня после написания этого кода:

  1. Я встречал много случаев, когда данные типа unsigned int и особенно для случая, for(unsigned int i = ...; i < ....; ++i) поэтому я использую using uint = unsigned int. Это надо делать так? Специально для "цикл for ()" случае, потому что это беспокоит меня довольно часто.

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

  3. Я создал временную Vector2D предмет для хранения пары координат временно и вставьте его в вектор потом. Я могу избежать создания этого объекта температура?

  4. При нахождении верхней вершины, я std::max_element. Однако я обнаружил, что это действительно не зависят от этой функции, а лямбда-функции, я написал после. Если я переверну сравнительные "return a.y_ < b.y_;" больше, она дает мне другой ответ. Так что std::max_element действительно?

  5. Я видел людей, которые говорили подчеркивания после или перед именем переменной резервируется. Однако, другие не думаю, что это вызывает проблемы в области. Это хорошо, чтобы использовать его, как я сделал в коде Vector2D? Рекомендуемый способ заключается в использовании m_variableNameно я не очень люблю этот формат.

Какие-либо другие отзывы или комментарии также приветствуются!



Комментарии
3 ответа

Ручка пограничный случай

Во-первых, давайте исправим это предупреждение компилятора:

190179.cpp: In function ‘itVector2D findeNextVertex(std::vector<Vector2D>&, itVector2D)’:
190179.cpp:150:1: warning: control reaches end of non-void function [-Wreturn-type]
}

Мы должны только достичь этого в вырожденном случае, где нет точек кандидат (например, мы предоставили только 1 вход алгоритма). В таком случае, наиболее подходящий итератор для возврата является отправной точкой:

return itSource;

Удобство для отладки

Чтобы сохранить в зависимости от внешнего ресурса, я встроенных тестовых данных в программу (просто для упрощения эксперимента):

#ifdef DEBUG
std::istringstream file{""
"12\n"
"5 19\n"
"33 2\n"
"-5 88\n"
"54 5\n"
"12 13\n"
"18 39\n"
"15 42\n"
"17 -5\n"
"-3 23\n"
"9 29\n"
"-8 17\n"
"-1 25\n"
};
#else
std::ifstream file;
file.open("data.txt");
if (!file.is_open())
{
std::cerr << "unable to open file" << std::endl;
return 1;
}
#endif

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

То, что может быть путного, правда, есть отдельные вход и выход из обработки. В этом случае, рассмотрим пользу

const std::vector<Vector2D> coords = readInputPoints();

Мы можем легко заменить, что функция чтения из разных источников, и это позволило нам иметь неизменный список координат, снижая потенциал для случайного их изменения.

Проверка ошибок при чтении входы

После file >> nPointsважно проверить, что это удалось, прежде чем пытаться использовать nPoints. К счастью, потоковый оператор возвращает ссылку на входной поток, и это превращается в bool, поэтому мы можем использовать простой if заявление, как это:

uint nPoints = 0;
if (file >> nPoints) {
coords.reserve(nPoints);
// then read each point and insert it
}

Мы должны сделать то же самое для каждой точки, а также:

    for (uint i = 0; i < nPoints; ++i) {
int x, y;
if (file >> x >> y) {
coords.emplace_back(x, y);
}
}

Мимоходом, здесь я использовал emplace_back чтобы создать объект напрямую в векторе.

Vector2D структура

Эта структура является минимально необходимым для этого приложения (возможно, слишком минимальный; как я покажу), но имя популярное, и может наехать, если применяется в более крупной программы. Мы можем положить его в пространство имен, чтобы избежать этой проблемы. Для этой программы, анонимное пространство имен будет достаточно.

Мы можем добавить некоторые члены, чтобы сделать остальные более простой код. Давайте начнем с Заказ, что позволяет нам снять лямбда-функция от наших std::max_element() звоните:

auto tie() const { return std::tie(y_, x_); }

// "less-than" means lower, with leftmost breaking ties
bool operator<(const Vector2D& other) const
{
return tie() < other.tie();
}

Мы действительно могли сделать с оператора Print:

friend std::ostream& operator<<(std::ostream& os, const Vector2D& v)
{
return os << v.x_ << ' ' << v.y_ << '\n';
}

Другой расчет, который требует доступ к переменным-членам рассчитывается направлении. Давайте сделаем, что член тоже:

bool is_clockwise_to(const Vector2D& other) const
{
// a positive determinant indicates clockwise, and negative anticlockwise
// zero implies collinear
return y_ * other.x_ - x_ * other.y_ > 0;
}

Теперь мы можем сделать x_ и y_ частная.

Предпочитают использовать значения итераторов

Мы действительно заботимся больше о ценности очков мы ограничивающего, чем их личности. Под этим я подразумеваю, что в тестах, таких как (itReference == itTarget || itReference == itSource)мы на самом деле хотим отказаться от любой точки на тех местах, не только в конкретных случаях. Это, очевидно, не проблема, если нет дубликатов во входных данных, но мы не знаем, что это правда.

Упростить с помощью стандартного алгоритма

У нас есть цикл обновления allCC, который мы можем заменить с std::all_of() вызова.

Мелкие придирки


  • Орфография - есть дополнительная e в findeNextVertex()

  • Я предпочитаю не иметь продольный подчеркивает - Если вам нужно напоминание о том, что входит в ваши занятия, это говорит о том, что у вас слишком много членов, вероятно, делает больше, чем надо (почитай про принцип единственной обязанности ОО дизайн).

  • std::size_t это естественный тип по количеству вещей, а не unsigned int (хотя если у вас есть более чем 65536 точек, вы, вероятно, выбрали неправильный алгоритм).

  • Предпочитают использовать std::endl только когда вы нуждаетесь в поток, чтобы быть очищены, и старые '\n' в противном случае. Ненужные гиперемия может быть настоящий убийца производительности в разы!


Измененный код

#include <fstream>
#include <iostream>
#include <string>
#include <tuple>
#include <vector>
#include <algorithm>

namespace {

class Vector2D
{
int x;
int y;

// For sorting - lowest y first, then lowest x
auto tie() const { return std::tie(y, x); }

public:
Vector2D(int x, int y) : x(x), y(y) {}

Vector2D operator-(const Vector2D& other) const
{
return {x - other.x, y - other.y};
}

bool operator<(const Vector2D& other) const
{
return tie() < other.tie();
}
bool operator==(const Vector2D& other) const
{
return tie() == other.tie();
}

bool is_clockwise_to(const Vector2D& other) const
{
// a positive determinant indicates clockwise, and negative anticlockwise
// zero means collinear (which we consider "not clockwise")
return y * other.x - x * other.y > 0;
}

friend std::ostream& operator<<(std::ostream& os, const Vector2D& v)
{
return os << v.x << ' ' << v.y << '\n';
}
};

using namespace std::rel_ops;
}

// find next convex hull vertex
Vector2D nextVertex(const std::vector<Vector2D> & coords, const Vector2D& source)
{
for (auto const& target: coords)
{
auto const vecTarget = target - source;
if (vecTarget != Vector2D{ 0, 0 } &&
std::all_of(coords.begin(), coords.end(),
[&](const auto& c) {
return c == target
|| c == source
|| (c - source).is_clockwise_to(vecTarget);}))
{
return target;
}
}

// degenerate case
return source;
}

std::vector<Vector2D> readInputPoints()
{
std::ifstream file;
file.open("data.txt");
if (!file.is_open()) {
std::cerr << "unable to open file" << std::endl;
return {};
}

std::vector<Vector2D> coords;

// total number of points
std::size_t nPoints = 0;
file >> nPoints;
if (!file) return {};

coords.reserve(nPoints);

while (--nPoints) {
int x, y;
file >> x >> y;
if (!file) return {};

coords.emplace_back(x, y);
}

return coords;
}

int main()
{
const std::vector<Vector2D> coords = readInputPoints();

if (coords.empty()) {
std::cerr << "Could not read inputs!" << std::endl;
return 1;
}

// find the topmost
auto const& topMost = *std::max_element(coords.begin(), coords.end());
auto current = topMost;

do {
current = nextVertex(coords, current);
std::cout << current;
} while (current != topMost);
}


Улучшить алгоритм

Текущий алгоритм смотрит на следующих двух точках от каждой вершины, так что Весы как о(ны2) , где п - число точек, и Х число ограничивающих точек.

Мы можем использовать знания, что все точки лежат по одну сторону от некоторой линии через любой ограничивающий момент, чтобы только проверить каждого кандидата - если он дальше влево (или вправо, смотря с какой стороны круглого корпуса мы хотим пойти) предыдущего лучшего кандидата, то это лучший выбор. Это, конечно, просто выбирая более новый критерий, и это делает наш код, данные в качестве О(НП).

Вот что я имею в виду:

Vector2D nextVertex(const std::vector<Vector2D> & coords, const Vector2D& source)
{
// order by direction from source - this works because we know that all
// points lie on the same side of a line through source.
auto const by_angle = [&source](const Vector2D& a, const Vector2D& b) {
return (a - source).is_clockwise_to(b - source);
};

return *max_element(coords.begin(), coords.end(), by_angle);
}

Обратите внимание, что это вышло проще, чем мой первый улучшенную версию выше, и гораздо проще, чем оригинал. (Лямбда, которая захватывает ссылку на source может быть более продвинутые, чем вы привыкли, однако).

Возможно, вы хотите сделать уточнение, так что коллинеарных точек сортировки в порядке удаления от point (использовать std::hypot() в <cmath> заголовок для добавления члена Vector2D). Без этого мы могли бы source непосредственно между двумя граничными точками, и они будут равны.

Рассмотреть вопрос о включении некоторых случаях тест с граничными коллинеарных точек и некоторые тривиальные наборы точек (1 или 2 балла), поскольку они, вероятно, нуждаются в незначительных доработках.

5
ответ дан 22 марта 2018 в 11:03 Источник Поделиться

Я новичок в этом сообществе SE и я не уверен, что смогу решить все свои вопросы, но вот мои два цента об этом, правки и комментарии приветствуются:


  1. Если вы хотите избежать повторного ввода unsigned int каждый раз, когда вы используете его, вы можете создать псевдоним, введя using просто, как вы делаете (я не знакома с этим, я использую ее только для пространств имен), или вы могли бы использовать следующее:

    typedef unsigned int uint;

    typedef особенно часто используется для придания еще одно название для данного типа данных в C и C++.


  2. is_open() возвращает ли поток, связанный с файлом. Вы могли бы использовать fail() метод вместо этого. Это один проверяет общее состояние потока, например, проверять, если поток вошел в состояние не пытаюсь читать недопустимое значение. is_open() не проверяет такого рода вещи.

  3. Не знаю, что сказать об этом.

  4. max_element() возвращает итератор на наибольший элемент в диапазоне [First, в прошлом]. Есть прототип 2 для этой функции, основанные на разных концепциях. Вы используя 3 параметра и определяется на компе, а не на operator< как пояснил здесь. Я не знаю много о comp но я думаю, что его поведение отличается от operator<, который объясняет, почему у вас разные результаты при сравнении обоих методов вычислений.

  5. Использование знака подчеркивания-это что-то правят конвенций. Я не уверен в этом, но ИМО вы использовали его также и предотвратить путаницу между конструкторами параметрам и атрибутов объекта. Я видел это написал таким способом много раз на уроки, так что я не знаю, почему было бы неправильно делать это. И просто для протокола, я ненавижу m_my_variable синтаксис, а также. Ко мне, М, L и G письма не приносят ничего, кроме путаницы. Но опять же, это условность и, конечно, многие его очень любят :)

НТН!

5
ответ дан 22 марта 2018 в 11:03 Источник Поделиться

Какой ответ на ваши прямые вопросы:

1. unsigned int


  • Я лично не люблю таких типов, исключительно для краткости, однако они вполне подойдут для определения типов как distance Если вы когда-нибудь задумывались о смене его double

  • Неподписанные и подписанные и компиляции предупреждение-бесплатно - это уже избалованы библиотеки. Использовать неподписанные только для махинаций. Слушать гуру с++ обсуждаем это (минут 12:15, минута 42:40 и 1:02:50)

5. подчеркивания или маркировки членов


  • При чтении кода полезно иметь члены, помеченные как таковые. Особенно конструкторы с params именем, как страны-члены могут быть подвержены ошибкам.

  • _[a-z] отлично для члена. но оно зарезервировано в глобальном пространстве имен. Также _[_А-Z] является зарезервированным (см. ответ на "каковы правила об использовании знака подчеркивания в C++ идентификатор?"). Поэтому ведущим подчеркиванием здесь в безопасности; это зависит от ваших стандартов кодирования разрешено ли это.

4. std::max_element

Это на выбор, что std::max для двух значений: доставляя самый большой счет использования "меньше" сравнение. если ваш тип не сравнима из коробки или если вы хотите, чтобы переопределить значение по умолчанию сравнения вы можете предоставить собственный Compare которые должны быть реализованы как пользовательские "меньше". Если вам дают "больше, чем" порядок сортировки меняется на противоположный. Ваш max_element гарантирует максимальную y не считая x значения. Если ваш набор данных содержит координаты с тем же значением y но разные x значения этих координат равны с точки зрения функции сравнения. Первый из них одинаково максимум y координаты возвращается.

2
ответ дан 23 марта 2018 в 01:03 Источник Поделиться