C 2D镶嵌图书馆？

发布时间：2020-12-16 02:59:14 所属栏目：百科来源：网络整理

导读：我有一些凸多边形存储为一个STL向量的点(或多或少).我想要 tessellate他们真的很快,最好是相当均匀的大小的部分,没有“条子”. 我要用它来将一些物体爆炸成小块.有没有人知道一个很好的图书馆来镶嵌多边形(将它们分割成较小的凸多边形或三角形的网格)？我已

我有一些凸多边形存储为一个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是非常有帮助的回答问题…

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!