确定多边形网格的切割部分

我有一个多边形网格 ,由顶点$ V $,边$ E $和面$ F $定义。 人们可以将其视为现实生活中的三维地形。

我想获得由垂直切割平面定义的这个地形的切割部分。 我可以用什么algorithm来高效地确定地形的切割部分? 这里的切割部分仅仅是切割部分垂直平面与多边形网格之间的交线的折线。

编辑:由于我的高程图是一个网格,这意味着我知道与顶点,面和边相关的每个信息,例如哪些面连接到哪个边。是否可以利用这些信息来加速剪切部分进一步?

既然你只有一个海拔地图,你可以开始投影2D平面上的一切。 所以你的高程图将变成二维网,切割平面将成为切割线。 在2D中find所有相交点之后,您可以将其重新投影到3D点。 这将大大简化algorithm和处理时间。

  • 要在二维平面中投影,您可以忽略Z分量
  • 您可以使用线段交点algorithm来查找点。
  • 您可以先快速检查给定边的两个顶点是否位于切割线的同一侧,然后边缘没有切割点。
  • 如果您的裁剪平面/线条创建凹面形状/多边形,那么您需要将此前的早期检查扩展到并确保至less一个顶点位于每条线的“内侧”。
  • 如果您的裁剪平面/线条不创建凹面形状/多边形,那么您应该首先将它们拆分为线段,并仅执行线段/线段相交检查。
  • 一旦你有所有相交的边和他们的交点find你的多段线,你应该沿着共享边遍历的面。 (要小心,如果面可以凸出,在这种情况下,他们可以有多个2相交的边缘)。
  • 在3D中取消投影多段线。 要取消投影点,可以使用距离与点所属线段的两个顶点的比例。 在2D和3D中,比例应该是相同的。