一种复杂平面片交线段的求取方法

摘要

本发明涉及一种复杂平面片交线段的求取方法，其基本思想是认为两个复杂平面片求交的结果是由若干个线段组成的，首先由两个平面片所在的平面方程求出足够长的理论交线段；接着在每个平面片上求出边线段与理论交线段的交点，并按照交点的投影系数大小对交点进行排序，每对交点形成一个交线段，这样得到每个平面片交线段的集合；最后求出两个平面片交线段集合的交集，即为所求的两个复杂平面片的交线段。本发明具有简单易行、算法逻辑严密和几何完备性好、算法计算量小等优点，可用于CAD、CAM、CAE、虚拟现实、3D打印等领域的几何建模。

主权项

一种复杂平面片交线段的求取方法，其特征是：包括如下步骤：步骤101：读入第一平面片A和第二平面片B的数据，依次读入第一平面片A和第二平面片B的数据，将第一平面片A的所有顶点、边、外环和内环的数据分别读入到A_Point_list、A_Line_list、A_Outer_Loop_list、A_Inners_Loop_list链表中，将第二平面片B的所有顶点、边、外环和内环的数据分别读入到B_Point_list、B_Line_list、B_Outer_Loop_list、B_Inners_Loop_list链表中；步骤102：遍历链表A_Point_list、A_Line_list、A_Outer_Loop_list求取第一平面片A的包围盒值A.min.X.、A.min.Y、A.min.Z、A.max.X、A.max.Y、A.max.Z；遍历链表B_Point_list、B_Line_list、B_Outer_Loop_list求取第二平面片B的包围盒值B.min.X.、B.min.Y、B.min.Z、B.max.X、B.max.Y、B.max.Z；步骤103：判断第一平面片A的包围盒与第二平面片B的包围盒是否相交，若相交则转至步骤105，若不相交则转至步骤104；步骤104：第一平面片A与第二平面片B不相交，则令A_inter_B＝null，转至步骤116；步骤105：遍历第一平面片A的链表A_Point_list中，取前三个点构造平面方程YA；步骤106：遍历第二平面片B的链表B_Point_list中，取前三个点构造平面方程YB；步骤107：由平面方程YA和YB求取平面片A和B的理论交线，由理论交线形成一个长线段，将其记为L；步骤108：遍历第一平面片A的A_Outer_Loop_list链表和A_Inners_Loop_list链表中的线段，取出一个线段与线段L求交，求得的交点保存在数组data_C中；步骤109：判断第一平面片A的A_Outer_Loop_list链表和A_Inners_Loop_list链表中的线段是否全部遍历完，未遍历完则转至步骤108，否则转至步骤110；步骤110：求data_C中的交点在线段L上的投影系数，将其保存在数组tmp_1中，按照tmp_1中投影系数从小到大的顺序对交点进行排序并删除重复交点，将排序后的交点保存在数组data_A中，相对应的投影系数保存在数组coefficient_A中；这里投影系数的概念为：设点为P，线段的起始端点和终止端点分别为M、N，点P在线段向量上的投影系数定义为：$l_p=\frac{\left(\overrightarrow{MP},\overrightarrow{MN}\right)}{\left(\overrightarrow{MN},\overrightarrow{MN}\right)};$步骤111：遍历第二平面片B的B_Outer_Loop_list链表和B_Inners_Loop_list链表中的线段，取出一个线段与线段L求交，求得的交点保存在数组data_D中；步骤112：判断第二平面片B的B_Outer_Loop_list链表和B_Inners_Loop_list链表中的线段是否全部遍历完，未遍历完则转至步骤111，否则转至步骤113；步骤113：求data_D中的交点在线段L上的投影系数，将其保存在数组tmp_2中，按照tmp_2中投影系数从小到大的顺序对交点进行排序并删除重复交点，将排序后的交点保存在数组data_B中，相对应的投影系数保存在数组coefficient_B中；步骤114：将数组coefficient_A中的投影系数按前后顺序，每两个投影系数构成一个区间；将数组coefficient_B中的投影系数按前后顺序，每两个投影系数构成一个区间；求取这些区间的交集，将结果保存在数组coefficient_U中；步骤115：按照coefficient_U中投影系数对应的交点对形成交线段，将得到的交线段保存在链表A_inter_B中；步骤116：第一平面片A和第二平面片B求交结果为链表A_inter_B中的线段。