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

Question

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

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

现在，我已经有了一些多边形 vector polygons

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

Polygon queryPolygon(Point2D point);

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

我的第一个问题是如何知道返回的多边形是否在vector多边形内，我已经有了。

我的第一个想法是使用unordered_set 并比较(vertex.begin(), vertex.end())。不知道有没有更好的办法。

另一个问题是一些多边形可能包含相同的边。如何设计数据结构，以便我可以知道包含相同边的多边形

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

当然暴力破解是一种方法，但是有没有更好的办法呢？

谢谢。

Answer 1

第一个问题

关于第一个问题，有一些不清楚的方面(请参阅我的评论)。尽管如此，我还是会回答，假设您只想将查询返回的任意多边形与存储在 vector 中的已知多边形进行比较，例如:

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)

第一层是逐点比较。问题是点的顺序很重要，因为用完全相同的点，你可以画一个 pentagon或 pentagram , 仅取决于选择的顺序以及您是否接受 self-intersecting polygons .

简单比较两个 vector 中的顶点是否相同:

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));
}

这里有一个 online demo

比较多边形(级别 4)

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

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

第二个问题

要找到公共(public)边，恕我直言，最简单的方法是将边添加到 map 中，据了解，您会将它们归一化以确保这些点始终处于相同的顺序。

您可以将任何您想要的边与边相关联，例如:计数、颜色或带有指向所属多边形的指针的容器。