найти один и тот же элемент среди нескольких объектов

Question

В настоящее время я делаю работу, связанную с полигонами. Многоугольник можно описать как несколько вершин.

struct Polygon{
   vector<Point2D> vertex;
   Color color;
};

Теперь у меня уже есть несколько полигонов вектор полигоны

и метод может сказать мне, что внутри какого полигона есть точка

Polygon queryPolygon(Point2D point);

Мне нужно установить цвет возвращаемого многоугольника.

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

Моя первая идея - использовать unordered_set и сравнивать (vertex.begin (), vertex.end ()) . Я не знаю, есть ли идея получше.

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

vector<Polygon> queryPolygonWithSameEdge(Point2D edgeStart, Point2D edgeEnd);

Конечно, грубая сила - это один из способов, но есть ли лучшие идеи?

Спасибо.

Answer 1

Первый вопрос

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

auto f = find_if (v.begin(), v.end(), [&p](const auto &x) { return compare1(x.vertex, p.vertex); });
if (f!=v.end()) {
    cout << "Found at "<< f-v.begin() <<endl; 
}
else cout << "Not found";

Сравнение многоугольников (уровень 1)

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

Для простого сравнения, если вершины в двух векторах одинаковы:

bool compare1(const vector<Point2D> &x, const vector<Point2D> &y ) {
    return x==y;  
}

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

Сравнение полигонов (уровень 2)

Здесь мы позаботимся о потенциальной другой отправной точке.Поэтому первым делом нужно найти смещение первой точки многоугольника кулака во втором многоугольнике и выполнить сравнение, позаботившись о смещении.Если точка не найдена в втором многоугольнике, они не совпадают:

bool compare2(const vector<Point2D> &x, const vector<Point2D> &y ) {
    if (x.size() != y.size())   // if different size it's not the same
        return false; 
    auto offset = find (y.cbegin(), y.cend(), x[0]);  // asumes at least 1 point 
    if (offset==y.cend()) 
        return false; 
    return equal(offset, y.cend(), x.cbegin()) 
              && equal(y.cbegin(), offset, x.cbegin()+(y.cend()-offset));  
}

Сравнение многоугольников (уровень 3)

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

bool compare3(const vector<Point2D> &x, const vector<Point2D> &y ) {
    if (x.size() != y.size())
        return false; 
    auto offset = find (y.cbegin(), y.cend(), x[0]);  // asumes at least 1 point 
    if (offset==y.cend())                             // no point in commont
        return false; 
    else if (equal(offset, y.cend(), x.cbegin()) 
              && equal(y.cbegin(), offset, x.cbegin()+(y.cend()-offset)))
        return true;  
                                                   // not equal.  And in reverse order ? 
    auto roffset = make_reverse_iterator(offset+1);
    return equal(roffset, y.crend(),  x.cbegin())
              && equal(y.crbegin(), roffset, x.cbegin()+(y.crend()-roffset));
}

Здесь у вас есть онлайн-демонстрация

Сравнение полигонов (уровень 4)

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

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

Второй вопрос

Чтобы найти общие ребра, ИМХО самым простым способом было бы добавить ребра к map, понимая, что вы нормализуете их доубедитесь, что точки всегда в одном и том же порядке.

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