在多个对象中找到一个相同的元素

Question

目前我正在做一项与多边形相关的工作。多边形可以描述为几个顶点。

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

现在，我有一些多边形已经矢量

一种方法可以告诉我，一个点在哪个多边形内

Polygon queryPolygon(Point2D point);

我需要设置返回的多边形的颜色。

我的第一个问题是如何知道返回的多边形是否在向量内

我的第一个想法是使用无序的集合和比较（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级）

现在不排除两条连续的边完全对齐。因此，多边形可能有一个与比较无关的附加点。

我让你来处理这个案子。但处理这种特殊情况最自然的地方是填充多边形。

为了对公共边进行鳍化，最简单的方法是IMHO将边添加到map中，理解为您将对它们进行规范化，以确保点始终处于相同的顺序。

您可以将任何您想要的东西关联到边缘，例如：计数、颜色或带有指向拥有多边形的指针的容器。