目前我正在做一项与多边形相关的工作。多边形可以描述为几个顶点。
struct Polygon{
vector<Point2D> vertex;
Color color;
};
现在,我有一些多边形已经矢量
一种方法可以告诉我,一个点在哪个多边形内
Polygon queryPolygon(Point2D point);
我需要设置返回的多边形的颜色。
我的第一个问题是如何知道返回的多边形是否在向量内
我的第一个想法是使用无序的集合和比较(vertex.begin(),vertex)。end())。我不知道是否有更好的主意。
另一个问题是某些多边形可能包含相同的边。如何设计数据结构,以便我能够知道包含相同边的多边形
vector<Polygon> queryPolygonWithSameEdge(Point2D edgeStart, Point2D edgeEnd);
当然暴力是一种方式,但是有更好的办法吗?
谢谢
第一个问题有一些不明确的方面(见我的评论)。尽管如此,我还是会回答,假设您只想将查询返回的任意多边形与存储在向量中的已知多边形进行比较,比如:
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
中,理解为您将对它们进行规范化,以确保点始终处于相同的顺序。
您可以将任何您想要的东西关联到边缘,例如:计数、颜色或带有指向拥有多边形的指针的容器。
我有一个Employee类对象的arraylist。每个员工都有id、fname、lname等。我需要获取员工id所在元素的索引,例如1234521953。如何找到员工所在的索引?每个身份证都是独一无二的这就是为什么我要通过身份证找到他。 这是我的班级成员: 我将它们添加到:
我正在尝试编写一个简单的应用程序,其中包含一个跟踪每个用户支付的款项的表和一个包含每个用户支付的总金额(所有付款的总和)的第二个表。目前,两个表都有相同的字段(firstName、lastName、金额),我已经将它们从同一个Java类映射到多个表,我无法将该类映射到多个表。对此有什么简单的解决方案吗?
问题内容: 我试图在一个元素上拍两个或多个相同类型的注释,在这种情况下是方法。这是我正在使用的近似代码: 编译以上内容时,javac抱怨重复的注释: 这样根本不可能重复注释吗?从学步上讲,上面的两个@Foo实例是否由于内容不同而不同吗? 如果上述方法不可行,有哪些可能的解决方法? 更新:我被要求描述我的用例。开始。 我正在建立一种语法糖化机制,以“映射” POJO到文档存储(例如MongoDB)。
让Person是一个具有属性name、age和idNumber的类。我希望有一个“人”的集合,我希望能够以最有效的方式执行以下操作: 通过他们的ID号检索他们。 获取年龄的人的列表 我的想法是同时维护一个使用id作为键的Hashmap和两个使用age和name作为每个树映射键的树映射。 这是最好的方式吗
我认为这对真正理解JAXB绑定文件的人来说很容易... 如何配置JAXB将多个元素解组到同一个类中? 注意:我想避免在我的项目中添加另一个依赖项(比如MOXy)。理想情况下,这可以通过注释或自定义绑定文件来实现。 我有一个XML文档,其中包含许多相同元素的变体——每个元素都有完全相同的属性。使用下面的示例,我只关心“员工”,但XML指定了“董事、经理和员工”。为了我们的目的,这些都是同一个父类的子
问题内容: 我有两个一维数组x和y,一个比另一个小。我试图找到x中y的每个元素的索引。 我发现有两种简单的方法可以做到这一点,第一种很慢,第二种需要占用大量内存。 记忆猪 是否有更快的方法或更少的内存密集型方法?理想情况下,搜索将利用以下事实:我们不是在列表中搜索一件事,而是在搜索许多东西,因此稍微适合并行化。如果您不假设y的每个元素实际上都在x中,则可获得加分。 问题答案: 正如Joe King