文档章节

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

刘军兴
 刘军兴
发布于 2015/04/15 09:59
字数 1859
阅读 50
收藏 5
点赞 0
评论 0

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

线对象大致分两类: 线段(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
博文 150
码字总数 226172
作品 0
昌平
计算机视觉与图像处理、模式识别、机器学习学科之间的关系

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

小金子 ⋅ 2014/07/07 ⋅ 0

学习人工智能AI需要哪些最基础的知识?

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

qq_32539403 ⋅ 2017/06/20 ⋅ 0

学界 | UCSB提出变分知识图谱推理:在KG中引入变分推理框架

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

机器之心 ⋅ 03/28 ⋅ 0

机器智能加速器:大数据环境下知识工程的机遇和挑战 | 清华李涓子教授

导读:知识图谱已经成为推动人工智能发展的核心驱动力之一。本文选自清华大学计算机科学与技术系教授、清华-青岛数据科学研究院科技大数据研究中心主任李涓子老师于2017年12月20日在阿里联合...

tmb8z9vdm66wh68vx1 ⋅ 2017/12/28 ⋅ 0

观点 | 专访贝叶斯网络之父Judea Pearl:我是AI社区的「叛徒」

  选自QuantaMagazine   作者:Kevin Hartnett   机器之心编译   参与:路、王淑婷      人工智能领域的先驱、贝叶斯网络之父 Judea Pearl 认为 AI 深陷于概率关联的泥潭,而忽视...

机器之心 ⋅ 05/16 ⋅ 0

机器智能加速器:大数据环境下知识工程的机遇和挑战 | 清华李涓子教授

李涓子,清华大学计算机科学与技术系教授,博士生导师。清华-青岛数据科学研究院科技大数据研究中心主任、中国中文信息学会语言与知识计算专委会主任、中国计算机学会术语委员会执行委员。研...

技术小能手 ⋅ 2017/12/29 ⋅ 0

几何画板制作二次函数系的方法

在解析几何中研究函数时通常是研究一个函数系共有的特征。单个的几何画板二次函数可以轻易绘制出来,那能不能绘制一个函数系呢?本文就像向大家介绍怎样用几何画板画二次函数系。 例如y=ax²...

学术研究软件 ⋅ 2016/05/13 ⋅ 0

修改一个像素,就能让神经网络识别图像出错

选自arXiv 作者:Su Jiawei等人 机器之心编辑部 用于识别图片中物体的神经网络可以被精心设计的对抗样本欺骗,这个问题目前在计算机视觉领域备受关注。此前,生成对抗样本通常需要向原图片中...

机器之心 ⋅ 2017/10/27 ⋅ 0

emacs lisp 研究 lisp.h (几何画板开发笔记 四)

由于想为所做的几何画板(类)和几何推理引入一种驱动语言,近期研究了 lisp 语言, 其中 emacs lisp 方言的实现看起来规模大小适合,我基本选择它作为研究对象,以 期待能引入到几何软件中。...

刘军兴 ⋅ 2014/05/11 ⋅ 0

用几何画板画矩形网格的方法

在几何学中,总是会借助网格来研究几何图形,比如方形网格和三角网格。在使用几何画板来研究几何图形时,也可以构造出网格,从而方便研究。最常使用的网格就是矩形网格,下面我们就一起来学习...

学术研究软件 ⋅ 2016/12/01 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

istio 文档

https://istio.io/docs/concepts/ https://istio.io/docs/concepts/traffic-management/handling-failures/ https://istio.io/docs/concepts/traffic-management/rules-configuration/......

xiaomin0322 ⋅ 19分钟前 ⋅ 0

编程语言的作用及与操作系统和硬件的关系

一、编程语言的作用及与操作系统和硬件的关系 作用:编程语言是计算机语言,是一种程序员与计算机之间沟通的介质,通过编程语言可以使得计算机能够根据人的指令一步一步去工作,完成某种特定...

slagga ⋅ 29分钟前 ⋅ 0

runtime实现按钮点击事件

也不能说是实现吧,,,就是有点类似于RAC里边的写法,不用给btn添加另外的点击事件,就那个add...select...这样子很不友好,来看下代码: [self.btn handleControlEvent:UIControlEventTou...

RainOrz ⋅ 30分钟前 ⋅ 0

Windows系统运维转linux系统运维的经历

开篇之前,首先介绍一下我的背景把:我是一个三线城市的甲方运维。最近,在《Linux就该这么学》书籍的影响下和朋友小A(Linux运维已经三年了,工资也比我的高很多)的影响下,决定转行。最近...

linux-tao ⋅ 30分钟前 ⋅ 0

zip压缩工具,tar打包工具

zip压缩工具 zip打包工具跟前面说到的gzip,bz2,xz 工具最大的不一样是zip可以压缩目录。如果没有安装,需要使用yum install -y zip 来安装。安装完之后就可以直接使用了,跟之前提到的压缩...

李超小牛子 ⋅ 38分钟前 ⋅ 0

使用npm发布自己的npm组件包

一、注册npm账号 官网:https://www.npmjs.com/signup 注册之后需要进行邮箱验证,否则后面进行组件包发布时候会提示403错误,让进行邮箱核准。 二、本地新建一个文件夹,cd进入后使用npm i...

灰白发 ⋅ 40分钟前 ⋅ 0

010. 深入JVM学习—垃圾收集策略概览

1. 新生代可用GC策略 1. 串行GC(Serial Copying) 算法:复制(Copying)清理算法; 操作步骤: 扫描年轻代中所有存活的对象; 使用Minor GC进行垃圾回收,同时将存活对象保存到“S0”或“S...

影狼 ⋅ 41分钟前 ⋅ 0

JVM性能调优实践——JVM篇

在遇到实际性能问题时,除了关注系统性能指标。还要结合应用程序的系统的日志、堆栈信息、GClog、threaddump等数据进行问题分析和定位。关于性能指标分析可以参考前一篇JVM性能调优实践——性...

Java小铺 ⋅ 42分钟前 ⋅ 0

误关了gitlab sign-in 功能的恢复记录

本想关sign-up的,误点了sign-in 退出后登录界面提示: No authentication methods configured 一脸懵逼.. 百度后众多方案说修改application_settings 的 signin_enabled字段; 实际上新版本字段...

铂金蛋蛋 ⋅ 42分钟前 ⋅ 0

登录后,后续请求接口没有带登录cookie可能原因

1.XMLHttpRequest.withCredentials没设置好,参考https://developer.mozilla.org/zh-CN/docs/Web/API/XMLHttpRequest/withCredentials...

LM_Mike ⋅ 43分钟前 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部