我有一些凸多边形存储为一个STL向量的点(或多或少).我想要
tessellate他们真的很快,最好是相当均匀的大小的部分,没有“条子”.
我要用它来将一些物体爆炸成小块.有没有人知道一个很好的图书馆来镶嵌多边形(将它们分割成较小的凸多边形或三角形的网格)？
我已经看过我已经找到的几个,但是我甚至不能让他们编译.这些学术类型不容易使用.
解决方法
CGAL有包来解决这个问题.最好的可能是使用
2D Polygon Partitioning包.例如,您可以生成多边形的y单调分区(适用于非凸多边形),您将得到如下结果：
y-monoyone-partitioning http://www.cgal.org/Manual/3.4/doc_html/cgal_manual/Partition_2/Trier_opt_cvx.gif
y-monoyone-partitioning http://www.cgal.org/Manual/3.4/doc_html/cgal_manual/Partition_2/Idar-Oberstein_appx_cvx.gif
运行时间为O(n log n).
在易用性方面,这是一个生成随机多边形并将其分区的小例子代码(基于this manual example)：
- 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上可以使用安装程序来获取预编译的库,并且在this page上为每个平台安装指南.安装可能不是最简单的,但是您可以获得最常用和强大的计算几何库有那里,cgal mailing list是非常有帮助的回答问题…
