如何用折线切割2D Mesh的算法及点集有序分离方案

你已经完成了网格与折线的交点检测，只要按以下步骤处理即可得到适配耳切算法的两个有序点集： #

1. 预处理：插入交点到原有序列 #

• 把所有检测到的交点，按位置先后插入到网格的边界顶点有序序列和折线顶点有序序列中：
  • 比如网格原边界按逆时针排序为[A,B,C,D]，交点P落在边BC上，就把P插入到B和C之间，新的序列变为[A,B,P,C,D]
  • 每个交点要额外标记两个属性：是折线穿入网格的入点还是穿出网格的出点、该交点在网格序列的索引、在折线序列的索引
• 判断出入点可以用叉乘：取折线当前边的方向向量，和网格对应边的法向量做叉乘，2D场景下z值为正则是入点，负则是出点，直接调用Unity的Vector3.Cross()即可计算

2. 拆分生成两个闭合有序点集 #

原始网格本身是闭合的多边形环，折线穿入穿出后会把原环切割为两个子环，按如下规则拼接即可：

1. 取第一个入点作为起点，沿着网格原有顶点顺序（保持逆时针/顺时针不变）遍历，依次把顶点加入第一个点集，直到遇到下一个配对的出点
2. 从该出点开始，调转方向沿折线序列往回走到起始的入点，把折线在两个交点之间的顶点依次加入第一个点集，此时第一个点集已经形成闭合环，满足耳切算法的输入要求
3. 第二个点集的拼接逻辑同理：从刚才的出点出发，继续沿网格原有顺序遍历剩余的顶点，直到走回起始的入点，再沿折线从入点走到出点，即可得到第二个闭合有序点集

如果折线和网格有超过2个交点，按顺序两两配对入点和出点，重复上述逻辑即可

注意：两个点集的顶点环绕方向必须和原网格保持一致（统一顺时针或统一逆时针），否则耳切算法会生成法向错误的三角面 #

3. 内部顶点处理（可选） #

如果你的网格存在非边界的内部顶点，只要封装一个射线法判断点是否在多边形内的工具方法bool IsPointInPolygon(Vector3 point, List<Vector3> polygon)，把每个内部顶点判断归属到对应点集即可，不需要调整原有顺序。 #

实现效果示意图 #

#

内容的提问来源于stack exchange，提问作者artpen