文档章节

自动几何推理的研究(二) 线

刘军兴
 刘军兴
发布于 2015/04/15 09:59
字数 1859
阅读 51
收藏 5

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

线对象大致分两类: 线段(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.

 

© 著作权归作者所有

共有 人打赏支持
刘军兴
粉丝 56
博文 187
码字总数 231243
作品 0
昌平
私信 提问
MSRA20周年研究趋势文章|图像识别的未来:机遇与挑战并存

文/微软亚洲研究院 代季峰 林思德 郭百宁 识别图像对人类来说是件极容易的事情,但是对机器而言,这也经历了漫长岁月。 在计算机视觉领域,图像识别这几年的发展突飞猛进。例如,在 PASCAL...

人工智能学家
11/16
0
0
预见未来 | 图像识别的未来:机遇与挑战并存

     编者按:自1998年成立以来,微软亚洲研究院一直致力于推动计算机科学领域的前沿技术发展。在建院20周年之际,我们特别邀请微软亚洲研究院不同领域的专家共同撰写“预见未来”系列文...

微软亚洲研究院
11/16
0
0
SIGGRAPH Asia 2018:微软亚洲研究院入选论文解读

     编者按:2018年的SIGGRAPH Asia大会于12月4日-7日在日本东京召开,在本届大会上,微软亚洲研究院共有5篇论文被接收,论文内容涵盖利用深度学习来实现从人像照片到肖像漫画的风格迁移...

微软亚洲研究院
12/06
0
0
想让照片里的美女“回头”?清华MIT谷歌用AI帮你实现了

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/yH0VLDe8VG8ep9VGe/article/details/82322470 伊瓢 发自 凹非寺 量子位 报道 | 公众号 QbitAI  “麻烦帮我...

量子位
09/02
0
0
计算机视觉与图像处理、模式识别、机器学习学科之间的关系

在我的理解里,要实现计算机视觉必须有图像处理的帮助,而图像处理倚仗与模式识别的有效运用,而模式识别是人工智能领域的一个重要分支,人工智能与机器学习密不可分。纵观一切关系,发现计算...

小金子
2014/07/07
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Spring Cloud Consul综合整理

部分资料来自 该项目通过自动配置和Spring环境以及其他Spring编程模型习惯用法提供了Spring Boot应用程序的Consul集成。 通过一些简单的注释,您可以快速启用和配置应用程序内的通用模式,并...

Gm_ning
8分钟前
0
0
Springboot 2.0 - 集成redis

最近在入门SpringBoot,然后在感慨 SpringBoot较于Spring真的方便多时,顺便记录下自己在集成redis时的一些想法。 从springboot官网查看redis的依赖包 <dependency>           ...

别打我会飞
10分钟前
0
0
支付宝APP支付申请配置过程详解

第一步:你需要申请一个支付宝商家账户账号,登陆之后进入产品中心,进行APP支付产品接入,填写相关资料,等待审核。 第二步:进行APP支付申请信息完善 第三步:进入蚂蚁金服开放平台进行开发...

Code辉
14分钟前
0
0
避免过度同步(67)

过度使用同步会导致性能低下、死锁或其他不确定问题 在一个同步方法或代码块中,不要放弃对客户端的控制 即:在一个同步区域内部,不要调用被覆盖方法,或者是传入对象提供的方法 这些外来方...

Java搬砖工程师
14分钟前
0
0
Java获取文件类型/扩展名

import java.io.IOException;import java.io.InputStream;import java.net.URL;import java.util.HashMap;import java.util.Map;public class FileTypeUtils { private fi......

Hzhodor
18分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部