自动几何推理的研究(二) 线
自动几何推理的研究(二) 线
刘军兴 发表于3年前
自动几何推理的研究(二) 线
  • 发表于 3年前
  • 阅读 49
  • 收藏 5
  • 点赞 0
  • 评论 0

腾讯云 技术升级10大核心产品年终让利>>>   

现在研究线. 线对象被大量使用, 为此需要仔细分析.

线对象大致分两类: 线段(L_Segment), 直线(L_Line).

线段(L_Segment) 主要用于线段相等记录(Cong_Seg), 线段等比(Ratio_Seg)记录中, 也用于线段相等集合(CSegs).
线段对象本身不作为搜索数据.

直线(L_Line) 主要用于平行线(P_Line), 垂线(T_Line), 角(AngleS) 记录中. 实现中直线以路径(G_Path)为基类,
这样与圆(Circle)共用一个实现基类, 可以方便的共用路径相关的函数 (如相交,合并,增删点)等功能.

直线在逻辑上再分为只含两个点的线, 两个以上点的线(即多点共线 coll). 两个点确定一条线, 在程序中两点构成的
线主要用于表示平行线,垂线,角中需要使用线的地方. 两点线不用做搜索数据, 共线(三点及以上)才作为搜索数据.

线段和直线都在线容器中管理(存放), 容器类 L_Line_Container, 引用的变量名为 all_ln. 此名字继承自 GExpert.

在系统中, 每个线段(L_Segment)由两个点构成, 如线段 AB, CD 分别由点 A,B 和 C,D 构成. 引用线段变量时
通常使用小写字母, 如 a,b. (引用点一般用大写字母). 特别指明是线段时一般用前缀 sg. 线段 AB 和线段 BA 是
等价的, 因此系统中仅保存线段 AB, 按照 A<B 的方式存于线段中, 其中 A<B 表示 A.idx<B.idx, idx 是点的索引.

线段对象在 all_ln 中存放在数组 seg_idx[] 中. 按照 A,B 计算一个三角数得到该线段的索引. 假设系统有 N 个点,
则最多构成 N*(N-1)/2 个线段. 因此将索引放在数组中不是很大的问题. 由于数组访问非常迅速. 这样, 查找是否
存在点 A,B 构成的线段就十分高效.

只含两点的直线对象(L_Line) 类似于线段, 存放在 all_ln 容器的数组 ln_idx[] 中. 也是按照点1,点2 计算三角数
索引, 这与线段非常类似.

由于线段和两点线非常相似, 先前曾有一个实现是线段,两点线实现为一个类; 在 c# 这类静态语言中不易这么做,
但也许 javascript 动态语言就比较容易实现. 而做的动机是可以节省存储.

含三点及以上的直线对象(L_Line)也叫共线记录(collinear), 其一是这些共线以链表的形式存放(现在是双向链表),
这样可以方便的遍历所有共线; 其二是共线记录也放在 ln_idx[] 索引中, 占据每一对点形成的三角数索引位置.
  举例: 设有共线 [A,B,D,E], 则此共线占据 ln_idx[] 中 (A,B), (A,D), (A,E), (B,D), (B,E), (D,E) 共六个位置.
这样取线上任意两点, 均可在 ln_idx[] 中找到此两点所在的线.

 

线的查找: 查找过点 A,B 的线, 先计算A,B 构成的索引 pidx, 返回 ln_idx[pidx] 值.
   如果该值为空, 则表示尚未创建过 A,B 的线.

两点线的添加: 创建一个线对象(L_Line), 更新 ln_idx[] 指定位置的索引. 断言 ln_idx[] 该线位置一定没有已存在
的线对象(否则不该调用添加函数)

上两者查找+添加一般合并为 fadd_ln() 方法, 即有则返回, 没有则创建并返回.

给线添加点: 设已有直线 A,B (没有可使用上述添加算法), 在线上添加一点 C. 一般用于 ON_LINE C A B 命令,
  对应几何语言: 点 C 在直线 AB 上(的实现). 创建新的线对象, 包含原有线+新的点C, 更新此新线对象到集合中.
更新算法稍后描述.

合并两条线: 设已有直线 [A,B,C], 和直线 [C,D,E], 假设某个推理推导出两直线共线(如发现 AC∥CD),
则需要合并. 创建新的线对象, 包含两条直线的所有不重复的点, 如本例合并后的线为 [A,B,C,D,E]. 更新此新线对象
到 all_ln 容器中.

线更新算法: 当产生了新的共线数据时, 要调用线(索引)更新算法. 根据数据结构设计, 新的线, 如 [A,B,C,D,E] 要占据
多个 ln_idx[] 索引位置(占据 N*(N-1)/2个索引位置, N 是点的数量). 重点是被占据的索引位置可能被别的线对象
占用了. 如 (A,B) 索引位置被直线 [A,B,C] 占用, (B,D) 索引位置可能被两点线 [B,D] 占据, 于是才有线更新的必要.

简要描述为: 尝试设置新线所有点对 (u,v) 位置的索引, 如果没有被占据, 则更新; 如果被两点线占据, 则更新, 并记录
一个标志(至少有一个线被更改); 如果被其它共线占据, 则需要递归使用合并线算法(也许不会发生??).
如果发生了至少一个线被更改的情况(标志为真), 则需要更新所有引用该线的对象, 包括平行线(P_Line), 垂线(T_Line),
角(AngleS), 这些对象的更新一般导致创建新的记录. 麻烦就麻烦在这里, 因此, 如果有空, 可以考虑减少或不更新的
可能性. 也或许可以延迟更新引用的地方(总之, 有一定复杂性).

判定 A,B,C 三点共线: 即判定 all_ln 容器中有此共线记录. 方法一: 遍历所有共线记录, 判定有一个记录同时含有
此三点; 方法二: 在 ln_idx[] 中找直线 AB, 如果没有则肯定没有共线记录, 如果有则判定该直线中含点 C 则共线;
方法三: 找直线 AB,BC, 如果是同一条线, 则共线. 此判定在系统中被(很)大量使用, 优化实现是非常值得的.

判定 A,B,C,D 四点共线: 等价于判定 A,B,C 以及 A,B,D 共线.

判定线 a,b 共线: (此a,b 可能是两点线) 首先查找 a,b 对应的共线, 如果其共线相同, 则 a,b 共线.

两条线的合并构造: 线,圆都使用 G_Path 路径对象作为基类, 线的合并构造等价于 路径的合并构造, 也即两个圆如果
合并构造, 也使用同样的算法. 相当于合并两个有序数组(路径对象中点按照 idx 序存放于数组中),
  参见:  http://www.cnblogs.com/A_ming/archive/2010/04/15/1712313.html
与参考文略微的改变是要去除重复点. 所以算法的主要循环变成:
   while (i < cnt1 && j < cnt2) {
     if (pt1[i] < pt2[j]) pt[k++] = pt1[i++];
     else if (pt1[i] == pt2[j]) pt[k++] = pt1[i++], j++;  // 同时递增 j 去除重复.
     else pt[k++] = pt2[j++]; 
   }

这种合并两个有序数组的算法也用于其它地方(如 P_Line 中的 ln[] 数组).

求两线交点: (求两路径交点) 由于点数组都是有序的, 因此不用双重遍历两个数组比较相等.
  经典算法是, 相等 pt1[i] == pt2[j] 则找到了交点; 否则 pt1[i] < pt2[j] 则递增 i, 否则递增 j.

 

共有 人打赏支持
粉丝 55
博文 141
码字总数 222144
×
刘军兴
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: