如何用折线切割二维三角网格？(How to cut a 2D triangle mesh by a polyline?)

如何用折线切割二维三角网格？(How to cut a 2D triangle mesh by a polyline?)

给定带有孔的二维三角形网格（.obj），我想通过折线（如下图中的红色曲线）切割网格，以生成两个单独的网格。

作为附加信息，折线是开放曲线。

有没有算法可以做到这一点？

我试图谷歌这个问题，但我只发现了一条线或一架飞机的网格切割。

Given a 2D triangle mesh (.obj) with hole(s), I want to cut the mesh by a polyline (as red curve in image below) to produce two separate meshes.

As additional info, the polyline is open curve.

Is there any algorithm to do this?

I tried to google this problem but I only found mesh cutting by a single line or by a plane.

最满意答案

我使用了CGAL的AABB树和Polyhedron数据结构来做类似你刚才提到的事情。 但我必须做实际的切割， 即创建新的顶点，添加新的边缘等，都是我（或我的队友）想出来的。 CGAL库为这样做非常方便。

基本方法是使用AABB树来计算线（或线条组，如果是折线）和网格之间的所有交叉点。 您将能够从CGAL以特定顺序获取交叉点。 然后你一个接一个地沿着它们走，添加新的边和顶点。 通常，除了起点和终点之外，您不必添加新顶点。

CGAL Polyhedron API支持沿边缘分割多边形，您可以在沿着结果集行走时使用这些多边形。 在内部，它使用半边数据结构，从get get开始支持这些操作。

I've used CGAL's AABB tree and the Polyhedron data structure, to do something similar to what you just asked. But I had to do the actual cutting i.e. creating new vertices, adding new edges etc, were all figured out by me (or my teammates). And the CGAL library came in very handy for doing this.

The basic method was to use the AABB tree to figure out all the intersections between the line (or set of lines, in case of a polyline) and the mesh. You'll be able to get the intersections in a specific order from CGAL. Then you walk along them one after another, adding the new edges and vertices. Normally you don't have to add new vertices except at the start and end points.

The CGAL Polyhedron API supports dividing polygons along edges, which you can use as you walk along the result set. Internally, it uses a half edge data structure, which supports these operations from the get go.