我有一组未经组织的2D点，想要找到这个集合的“轮廓”（而不是凸包）。由于我有速度目标（平均计算机上少于10毫秒），不能使用alpha shapes。我的第一个方法是计算网格并找到轮廓正方形（将空正方形视为邻居的正方形）。因此，我认为我有效地减少了点的数量（大约从22000个点缩小到3000个点）。但我仍然需要优化这个新集合。
我的问题是：如何在我的绿色点中找到真正的轮廓点？
2个回答
1
经过一个充满思考的周末，我可能找到了一个方便的解决方案。
所以我们需要一个网格，我们需要用我们的点填充它，这里没有困难。
我们必须决定哪些正方形被视为“轮廓”。我们的标准是：至少有一个空邻居和至少3个非空邻居。
我们缺乏连接信息。因此，我们选择一个具有2个或更少“轮廓”邻居的“轮廓”正方形。然后我们选择其中一个邻居。从那里开始扩展。我们只需在当前正方形周围画圆，找到下一个“轮廓”正方形，知道前一个“轮廓”正方形即可。我们的轮廓标准防止我们陷入死胡同。
现在我们有连接正方形的向量，如果我们的形状没有孔，那么通常只有一个连接正方形的向量！
现在对于每个正方形，我们需要找到最佳的轮廓点。我们选择离我们平面重心最远的点。这适用于大多数形状。另一种技术是计算所选正方形的空邻居的重心，并选择最近的点。
对于28000个点的集合，这种技术需要8毫秒。CGAL的Alpha形状对于28000个点将平均需要125毫秒。
注：我希望我表达清楚了，英语不是我的母语:s
所以我们需要一个网格，我们需要用我们的点填充它，这里没有困难。
我们必须决定哪些正方形被视为“轮廓”。我们的标准是：至少有一个空邻居和至少3个非空邻居。
我们缺乏连接信息。因此，我们选择一个具有2个或更少“轮廓”邻居的“轮廓”正方形。然后我们选择其中一个邻居。从那里开始扩展。我们只需在当前正方形周围画圆，找到下一个“轮廓”正方形，知道前一个“轮廓”正方形即可。我们的轮廓标准防止我们陷入死胡同。
现在我们有连接正方形的向量，如果我们的形状没有孔，那么通常只有一个连接正方形的向量！
现在对于每个正方形，我们需要找到最佳的轮廓点。我们选择离我们平面重心最远的点。这适用于大多数形状。另一种技术是计算所选正方形的空邻居的重心，并选择最近的点。
对于28000个点的集合，这种技术需要8毫秒。CGAL的Alpha形状对于28000个点将平均需要125毫秒。
注：我希望我表达清楚了，英语不是我的母语:s
- Cyril
0
你真的应该使用alpha形状。也许只使用绿色点作为alpha算法的输入。
- lrineau
3
即使对于2500个点，CGAL的alpha形状计算时间也只有15毫秒。加上寻找绿色点的5毫秒，总共是20毫秒的计算时间。我已经找到了一个解决方案（正在输入），它只需要3毫秒并且输出效果很好。 - Cyril
@Xerto：要么你的机器很慢，要么你使用CGAL alpha shapes的方式不对。在我的笔记本电脑上，25000个点的运行时间大约为5毫秒，除非你指定了一个太大的alpha值并返回所有边缘（在这种情况下，对于25000个点，大约需要20毫秒）。 - lrineau
我的处理器是Core 2 Duo，此外该软件是为一架无人机设计的，因此我们有低规格（可能是Atom）。对于CGAL的Alphashapes，我使用文档中提供的示例。 - Cyril
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接