C ++ 2D细分库？ [英] C++ 2D tessellation library?

问题描述

我有一些凸多边形存储为点的STL向量（或多或少）。我想要快速）：

  typedef CGAL :: Exact_predicates_inexact_constructions_kernel K; 
 typedef CGAL :: Partition_traits_2< K>性状; 
 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>创造者; 
 typedef CGAL :: Random_points_in_square_2< Point_2，Creator>点生成器
 
 
 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））; 
 
 //此时partition_polys包含输入多边形的分区
 return 0; 
} 
  

要安装cgal，如果你在windows上，可以使用安装程序预编译库，以及此页面上每个平台的安装指南。这可能不是最简单的安装，但你得到最常用的和鲁棒的计算几何库，有在那里，和 cgal邮件列表对于回答问题非常有帮助...

I've got some convex polygons stored as an STL vector of points (more or less). I want to tessellate them really quickly, preferably into fairly evenly sized pieces, and with no "slivers".

I'm going to use it to explode some objects into little pieces. Does anyone know of a nice library to tessellate polygons (partition them into a mesh of smaller convex polygons or triangles)?

I've looked at a few I've found online already, but I can't even get them to compile. These academic type don't give much regard for ease of use.

解决方案

CGAL has packages to solve this problem. The best would be probably to use the 2D Polygon Partitioning package. For example you could generate y-monotone partition of a polygon (works for non-convex polygons, as well) and you would get something like this:

The runnning time is O(n log n).

In terms of ease of use this is a small example code generating a random polygon and partitioning it (based on 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;
}

To install cgal, if you are on windows you can use the installer to get the precompiled library, and there are installations guides for every platform on this page. It might not be the simplest to install but you get the most used and robust computational geometry library there is out there, and the cgal mailing list is very helpful to answer questions...

这篇关于C ++ 2D细分库？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！