代码之家 › 专栏 › 技术社区 › mpen

C++ 2D镶嵌库?

tesselation computational-geometry geometry c++

mpen · 技术社区 · 16 年前

我有一些凸多边形存储为点的STL向量(或多或少)。我想 tessellate 它们真的很快,最好是成大小相当均匀的碎片,没有“长条”。

我要用它把一些物体炸成碎片。有人知道一个很好的多边形镶嵌库吗(把它们分割成一个小的凸多边形或三角形网格)?

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

7 回复 | 直到 11 年前

balint.miklos 16 年前

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 回答问题很有帮助…

prideout 13 年前

poly2tri 看起来像是一个非常好的轻量级C++库,用于2D Delaunay三角剖分。

Victor Liu 16 年前

正如巴林特.米克罗斯在上面的评论中提到的,休丘克的 triangle 包装比较好。我自己使用过很多次;它很好地集成到项目中,并且 triangle++ C++接口。如果您想避免长条,那么允许三角形添加(内部)Steiner点,以便生成质量网格(通常是约束一致的Delaunay三角测量)。

Martin Beckett 16 年前

如果你不想把整个gcal构建到你的应用程序中,这可能更容易实现。

http://www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml

Lucas Walter alexfigtree 11 年前

我刚刚开始研究这个问题,我正在考虑沃罗诺伊镶嵌。原始的多边形将得到一个半随机点的散射,这将是沃罗诺伊细胞的中心,它们越均匀地分布,他们的细胞将更规则的大小,但他们不应该在一个完美的网格,否则内部的多边形都会看起来一样。因此,首先要能够生成这些单元中心点——在源多边形的边界框上生成它们,并且内部/外部测试不应该太难。

Voronoi边缘是这张图片中的虚线,是Delaunay三角测量的补充。所有锐利的三角形点都变钝了:

enter image description here

Boost具有一些Voronoi功能: http://www.boost.org/doc/libs/1_55_0/libs/polygon/doc/voronoi_basic_tutorial.htm

下一步是创建Voronoi多边形。沃罗克 http://math.lbl.gov/voro++/ 是面向三维的,但其他地方建议大约二维结构将工作,但比面向二维Voronoi的软件慢得多。另一个看起来比随机学术主页孤立项目要好得多的包是 https://github.com/aewallin/openvoronoi .

看起来opencv用于支持沿着这些线做一些事情,但是它已经被弃用了(但是C-API仍然有效吗?).cv::distcransform仍然保持不变,但可以在像素上操作并生成像素输出,而不是顶点和边多边形数据结构,但如果不是您的,可能足以满足我的需要。

一旦我了解更多,我会更新这个。

tfinniga 16 年前

关于您所需的输入和输出的更多细节可能会有所帮助。

例如,如果你只是想把多边形变成三角形,一个三角形风扇可能会起作用。如果你试图把一个多边形切成小块,你可以实现一些行军方格。

好吧,我做了一个错误的假设——我假设行军方格会更像行军方格。结果却完全不同,完全不是我的意思。:

无论如何,要直接回答你的问题,我不知道有什么简单的图书馆能满足你的要求。我同意CGAL的可用性。

我想的算法基本上是用直线分割多边形,直线是一个网格,所以你主要得到四次曲面。如果您有一个多边形线交叉点,那么实现就会很简单。提出这个问题的另一种方法是将二维多边形视为一个函数,并覆盖一个点网格。然后你只需要做一些类似于行进立方体的事情。如果所有4个点都在多边形中,则生成一个四边形;如果3个在生成一个三角形中,则2个在生成一个矩形中,等等,可能会造成过度破坏。如果你想要看起来稍微不规则的多边形,你可以随机化网格点的位置。

另一方面,您可以执行catmull-clark样式的细分,但忽略平滑。算法基本上是在每个边的质心和中点添加一个点。然后,对于原始多边形的每个角,您将生成一个新的较小的多边形,该多边形将前一个边中点连接到角、角、下一个边中点和质心。这将平铺空间,并具有与输入多边形类似的角度。

所以,有很多选择,我喜欢头脑风暴解决方案,但我仍然不知道你打算用它做什么。这是为了创建可破坏的网格吗?你在做一些需要更小元素的网格处理吗?试图避免古鲁德阴影文物?这是作为预处理还是实时处理运行的?正确性有多重要?更多的信息会产生更好的建议。

IV. 15 年前

如果你有凸面多边形,而且你不太注重质量,那么这真的很简单——就这么做吧。 ear clipping . 不用担心,凸多边形不是O(n^2)。如果你天真地这样做(即,你找到耳朵的时候夹耳朵),那么你会得到一个三角扇,如果你想避开长条,这有点麻烦。两个可以改进三角测量的普通启发式方法是

把耳朵分类,如果太慢的话
随机选择一只耳朵。

如果你想要一个更强大的基于耳朵裁剪的三角测量仪,请查看 FIST .