文档章节

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

刘军兴
 刘军兴
发布于 2015/04/15 09:59
字数 1859
阅读 50
收藏 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.

 

© 著作权归作者所有

共有 人打赏支持
刘军兴
粉丝 54
博文 184
码字总数 226359
作品 0
昌平
计算机视觉与图像处理、模式识别、机器学习学科之间的关系

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

小金子
2014/07/07
0
0
多位教授牵手FB AI 研究院,机器人实验室毗邻CMU成立

雷锋网 AI 科技评论按:美国时间 2018 年 7 月 17 日,Facebook 首席 AI 科学家 Yann LeCun 在 Facebook 新闻中心发出一篇博文,表示有多位教授将加盟 Facebook AI 研究院,不仅继续提升现有...

杨晓凡
07/18
0
0
想让照片里的美女“回头”?清华MIT谷歌用AI帮你实现了

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

量子位
09/02
0
0
学习人工智能AI需要哪些最基础的知识?

人工智能的定义可以分为两部分,即“人工”和“智能”。“人工”比较好理解,争议性也不大。有时我们会要考虑什么是人力所能及制造的,或着人自身的智能程度有没有高到可以创造人工智能的地步...

qq_32539403
2017/06/20
0
0
学界 | UCSB提出变分知识图谱推理:在KG中引入变分推理框架

  选自arXiv   作者:Wenhu Chen等   机器之心编译   参与:张楚、思源      推理知识图谱中缺失的连接已经吸引了研究界的广泛关注。在本论文中,加州大学圣塔芭芭拉分校的王威廉...

机器之心
03/28
0
0

没有更多内容

加载失败,请刷新页面

加载更多

简单谈一谈压力测试

最近,在做API的压力测试,趟了不少坑,然后呢,简要记录一下。 压测前需要准备的一些事 拿到API文档不要立马上手,先基准测试,就是执行一次接口测试,至少要压这个接口,要先熟悉一下他的参...

浮躁的码农
39分钟前
0
0
PHP 错误调查

一.定义:PHP错误是由PHP无法读懂执行的代码引起的错误。 二:错误日志 error log 1.在php.ini 里设置 log_errors = on, log文件位置 error_log=/tmp/php_errors.log 2.代码里设置ini_set('...

忙碌的小蜜蜂
42分钟前
0
0
knn算法

import numpy as np def CreateDateSet(): group = np.array([[1.0, 2.0], [1.2, 0.1], [0.1, 1.4], [0.3, 3.5]]) labels = ['A','A','B','B'] return group,labels coding:utf-8 from numpy......

南桥北木
42分钟前
0
0
自己手写一个 SpringMVC 框架

前端框架很多,但没有一个框架称霸,后端框架现在Spring已经完成大一统.所以学习Spring是Java程序员的必修课. Spring 框架对于 Java 后端程序员来说再熟悉不过了,以前只知道它用的反射实现的,...

别打我会飞
今天
2
0
01-《Apache Tomcat 9》之文件索引

《Apache Tomcat 9》是《看Apache官方文档学英语》的第一个专栏!让我们一起在看文档的过程中学英语,在学英语的过程中夯实技术! Documentation Index - 文件索引 Introduction - 介绍 This...

飞鱼说编程
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部