C++ 2D曲面细分库？

Question

我有一些凸多边形存储为STL矢量点(或多或少).我想快速镶嵌它们,最好是尺寸相当均匀的碎片,没有"条子".

我打算用它把一些物品分成小块.有没有人知道一个漂亮的图表来镶嵌多边形(将它们分成一个较小的凸多边形或三角形的网格)？

我已经看过一些我已经在网上找到的,但我甚至无法让它们编译.这些学术类型并不重视易用性.

Answer 1

CGAL有解决这个问题的软件包.最好的可能是使用2D多边形分区包.例如,你可以生成多边形的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).

在易用性方面,这是一个生成随机多边形并对其进行分区的小示例代码(基于此手动示例):

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邮件列表非常有助于回答问题...

Answer 2

对于2D Delaunay三角测量,poly2tri看起来像一个非常好的轻量级C++库.