从三维网格生成二维截面多边形

由于网格不是凸的,因此生成的横截面可能会断开连接,因此实际上由多个多边形组成。这意味着必须检查每个三角形,因此至少需要对n个三角形执行o(n)操作。

有一种方法:

T <- the set of all triangles
P <- {}
while T is not empty:
  t <- some element from T
  remove t from T
  if t intersects the plane:
    l <- the line segment that is the intersection between t and the plane
    p <- [l]
    s <- l.start
    while l.end is not s:
      t <- the triangle neighbouring t on the edge that generated l.end
      remove t from T
      l <- the line segment that is the intersection between t and the plane
      append l to p
    add p to P

对于n个三角形,这将在o(n)时间内运行,前提是您的三角形有指向其三个邻居的指针,并且 T 支持固定时间删除(例如哈希集)。

和所有的几何算法一样,魔鬼在细节中。例如,仔细考虑三角形的顶点正好在平面上的情况。

通过查找与平面相交的所有多边形,然后查找相交的精确线段,可以使用少量几何图形来完成此操作。这些线段是您要查找的二维多边形的直线。