C ++ 2D曲面细分库？
https://stackoverflow.com/questions/1418831
-
07-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我有一些凸多边形存储为STL矢量点（或多或少）。我想非常快速地镶嵌它们，最好是大小相当均匀，并且没有“条子” ;。
我将用它将一些物品爆炸成小块。有没有人知道一个漂亮的图表来镶边多边形（将它们分成一个较小的凸多边形或三角形的网格）？
我已经看过一些我已经在网上找到的，但我甚至无法让它们编译。这些学术类型并不重视易用性。
解决方案
CGAL 有解决此问题的软件包。最好的可能是使用 2D多边形分区包裹。例如，你可以生成多边形的y单调分区（也适用于非凸多边形），你会得到这样的结果：
运行时间为O（n log n）。
在易用性方面，这是一个生成随机多边形并对其进行分区的小示例代码（基于本手册示例）：
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Partition_traits_2<K> Traits;
typedef Traits::Point_2 Point_2;
typedef Traits::Polygon_2 Polygon_2;
typedef std::list<Polygon_2> Polygon_list;
typedef CGAL::Creator_uniform_2<int, Point_2> Creator;
typedef CGAL::Random_points_in_square_2<Point_2, Creator> Point_generator;
int main( )
{
Polygon_2 polygon;
Polygon_list partition_polys;
CGAL::random_polygon_2(50, std::back_inserter(polygon),
Point_generator(100));
CGAL::y_monotone_partition_2(polygon.vertices_begin(),
polygon.vertices_end(),
std::back_inserter(partition_polys));
// at this point partition_polys contains the partition of the input polygons
return 0;
}
要安装cgal，如果您在Windows上，可以使用安装程序获取预编译库，并且此页面。它可能不是最简单的安装，但你得到了最常用和最强大的计算几何库，并且 cgal邮件列表非常有助于回答问题......
其他提示
poly2tri 看起来像是一个非常好的2D Delaunay轻量级C ++库三角测量。
正如上面评论中提到的balint.miklos，Shewchuk的三角形套餐相当不错。我自己多次使用它;它很好地集成到项目中，并且有 triangle ++ C ++界面。如果你想避免细长，那么允许三角形添加（内部）Steiner点，这样你就可以生成一个高质量的网格（通常是一个约束的符合delaunay三角剖分）。
如果您不想将整个GCAL构建到您的应用程序中 - 这可能更容易实现。
http://www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml
我刚开始研究同样的问题，我正在考虑voronoi曲面细分。原始多边形将获得散射的半随机点，这些半随机点将成为voronoi单元的中心，它们的分布越均匀，单元格的大小将越规则，但它们不应处于完美的网格中，否则内部多边形看起来都一样。所以第一件事就是能够生成那些细胞中心点 - 在源多边形的边界框上生成它们，内部/外部测试不应该太难。
voronoi边缘是这张图片中的虚线，并且是delaunay三角剖分的补充。所有尖锐的三角形点都变得迟钝了：
Boost有一些voronoi功能： http://www.boost.org/doc/库/ 1_55_0 /库/多边形/ DOC / voronoi_basic_tutorial.htm
下一步是创建voronoi多边形。 Voro ++ http://math.lbl.gov/voro++/ 以3D为导向，但在别处建议大约2d结构将起作用，但比面向2D voronoi的软件要慢得多。另一个看起来比随机学术主页孤儿项目好很多的软件包是 https://github.com/ aewallin / openvoronoi 。
看起来OpenCV过去常常支持这些行，但它已被弃用（但c-api仍然有用吗？）。仍然维护cv :: distTransform，但是对像素进行操作并生成像素输出，而不是顶点和边缘多边形数据结构，但如果不是你的话，可能就足够了。
一旦我学到了更多，我就会更新。
关于所需输入和输出的更多细节可能会有所帮助。
例如，如果您只是想将多边形变成三角形，那么三角扇可能会起作用。如果你试图将多边形切成小块，你可以实现某种行进方块。
好吧，我做了一个错误的假设 - 我假设行军广场更像是行进立方体。事实证明它完全不同，而不是我的意思..：|
在任何情况下，要直接回答您的问题，我不知道任何简单的库可以满足您的需求。我同意CGAL的可用性。
我想到的算法基本上是用线条分割多边形，其中线条是网格，所以你大多数都是四边形。如果你有一个多边形线交叉点，实现将很简单。造成这个问题的另一种方法是像处理函数一样处理2d多边形，并覆盖点网格。然后你只需要做一些类似于行进立方体的东西..如果所有4个点都在多边形中，做一个四边形，如果3个在做一个三角形，2个在做一个矩形，等等。可能是矫枉过正。如果您想要略微不规则的多边形，则可以随机化网格点的位置。
另一方面，你可以做一个catmull-clark样式细分，但省略平滑。该算法基本上是在质心和每个边缘的中点添加一个点。然后，对于原始多边形的每个角，您将创建一个新的较小的多边形，该多边形连接角落之前的边缘中点，角落，下一个边缘中点和质心。这会平铺空间，并且将具有与输入多边形类似的角度。
所以，很多选择，我喜欢头脑风暴解决方案，但我仍然不知道你计划用它做什么。这是否会产生可破坏的网格？你在做某种需要更小元素的网格处理吗？试图避免Gouraud阴影文物？这是作为预处理还是实时运行的东西？准确性有多重要？更多信息可以提供更好的建议。
