精华内容
下载资源
问答
  • 目录线性基线性空间线性基的交线性无关线性基的变换线性基求交的方法上述方法的正确性构造B′B'B′的方法上述方法的正确性代码实现 线性基 关于线性基是什么、如何构造线性基,相对比较容易理解,不是本文的重点。可...

    这篇文章要讨论的,是有关算法竞赛中的一个主题:线性基。我自己去认识、理解这个问题(指线性基求交),确实花了很大一番功夫。我将梳理我自己的思考认识,包括众多其他博客中所提到的、没提到的方方面面。

    线性基

    关于线性基是什么、如何构造线性基,相对比较容易理解,不是本文的重点。可以参考这篇博客

    线性空间

    一个线性基所表征的线性空间是这个线性基能表示的所有数的集合。

    线性基的交

    设有三个线性基AABBCC,如果它们所表征的线性空间的关系是:VAVB=VCV_A\cap V_B=V_C,那么我们称CCAABB

    线性无关

    和线性代数中的概念类似:如果一组数(在异或意义上)线性无关,那么任意取这组数中的若干个,它们的异或和都不为0。

    下面所说的“线性无关”,都指的是这个意思。

    线性基的变换

    设线性基A={a1,a2,...,an}A=\{a_1,a_2,...,a_n\},任取iji\neq j,令ai=aiaja_i'=a_i\oplus a_j,然后用aia_i'替换AA中的aia_i,那么替换后的AA与替换前等价。等价的含义是:变换之后,线性基的元素个数没有改变,并且所表征的线性空间没有变化。

    因此,我们可以对一个线性基反复进行上述操作,结果始终都是与最初的线性基等价的。

    线性基求交的方法

    假设有线性基AABB,我们想求它们的交。首先,将BB变换到合适的等价形式BB',使得BB'满足下列性质:

    • 定义W={bbB,bVA}W=\{b|b\in B' ,b\in V_A\}BW={bbB,bVA}B'-W=\{ b|b\in B',b\notin V_A\}
    • (BW)A(B'-W)\cup A线性无关(小提示:根据上面的定义,参与并操作的BWB'-WAA是没有相同元素的,所以并操作可以简单理解为把这两个集合中的元素都拿出来放到一起)。

    那么,WW即是线性基AABB的交。

    理解这个方法有2个要点:第一,如何变换BB得到一个合适的BB'?甚至于这样的BB'是否存在?第二,为什么WW就是AABB的交?

    上述方法的正确性

    先假设,我们确实有一种方法,总是可以将BB变换到合适的BB',然后我们考虑如何证明WW确实是AABB的交。

    由于BB'BB是等价的,所以它们所表征的线性空间相同,所以为了证明WWAABB的交(VW=VAVBV_W=V_A\cap V_B),只需要证明VW=VAVBV_W=V_A\cap V_{B'}

    根据WW的定义,显然有:VWVBVAV_W\subset V_{B'}\cap V_A。至此,我们的证明完成了一半。

    任取VBVAV_{B'}\cap V_A中的某元素vv,假设vVWv\notin V_W,这意味着:BB'是可以表示vv的,AA也是可以表示vv的,而WW却无法表示vv。由于WW本身是BB'的一个子集,因此用BB'表示vv时,必然要用到BWB'-W中的元素,设这些元素的异或和为SSBB’表示vv时,也可能用到WW中的元素,设这些元素的异或和为TT。那么我们有v=STv=S\oplus T。由于VWVAV_W\subset V_A因此TVAT\in V_A,又因为vVAv\in V_A,所以得出SVAS\in V_A。这意味着BWB'-W中取出来某些元素的异或和(SS)可以用AA表示,因此BWB'-WAA线性相关!与假设矛盾。因此必然有vVWv\in V_W

    因此VWVBVAV_W\supset V_{B'}\cap V_A,从而VW=VBVAV_W= V_{B'}\cap V_A

    构造BB'的方法

    A={a1,a2,...,an}A=\{a_1,a_2,...,a_n\}B={b1,b2,...,bm}B=\{b_1,b_2,...,b_m\}(排列顺序如何并不重要)。下面我们将BB变换为符合要求的B={b1,b2,...,bm}B'=\{b_1',b_2',...,b_m'\}

    考虑任意的bib_i,如果bib_i可以被a1,a2,...,an,b1,b2,...,bi1a_1,a_2,...,a_n,b_1,b_2,...,b_{i-1}线性表示,即bi=αβb_i=\alpha \oplus \beta,其中α\alpha是若干axa_x的异或和,β\beta是若干bxb_x的异或和。那么令bi=biβb_i'=b_i\oplus \beta。若bib_i无法被线性表示,那么令bi=bib_i'=b_i

    对所有的i=1,2,...,mi=1,2,...,m都执行上述操作,我们可以得到BB'的所有元素。

    上述方法的正确性

    首先显然的是,通过上述构造方法,BB'BB是等价的(提示:参考前述线性基的变换)。

    根据上一节的构造方法,bib_i'有两类来源:

    1. bib_i
    2. biβb_i\oplus \beta

    我们把第1类的bib_i'记为b(1)ib'_{(1)i},第2类记为b(2)ib_{(2)i}'

    显然,对于任意的b(2)ib_{(2)i}'b(2)iVAb'_{(2)i}\in V_A。这是因为b(2)i=biβ=αββ=αb'_{(2)i}=b_i\oplus \beta=\alpha \oplus \beta \oplus \beta=\alpha

    显然,对于任意的b(1)ib_{(1)i}'b(1)iVAb'_{(1)i}\notin V_A

    另外,我们将所有的b(1)ib'_{(1)i}拿出来,和a1,a2,...,ana_1,a_2,...,a_n放在一起,它们是线性无关的。

    这是因为,假如它们线性相关,那么一定存在:
    aj1aj2...ajyb(1)i1b(1)i2...b(1)ix=0a_{j_1}\oplus a_{j_2}...\oplus a_{j_y}\oplus b'_{(1)i_1}\oplus b'_{(1)i_2}...\oplus b'_{(1)i_x}=0

    由于是都是第1类的bib_i',所以上式等价于:
    aj1aj2...ajybi1bi2...bix=0a_{j_1}\oplus a_{j_2}...\oplus a_{j_y}\oplus b_{i_1}\oplus b_{i_2}...\oplus b_{i_x}=0

    不妨设i1<i2<...<ixi_1<i_2<...<i_x,那我们发现,bixb_{i_x}是可以被a1,a2,...,an,b1,b2,...,bix1a_1,a_2,...,a_n,b_1,b_2,...,b_{i_x-1}线性表示的,这与bixb_{i_x}'来源于第1类构造分支相矛盾。

    至此,我们已经可以看到下面的对应关系:
    W={bb2}BW={bb1}W=\{b'|b'产生于第2类构造分支\} \\ B'-W=\{b'|b'产生于第1类构造分支\}

    如此构造,所有要求的条件都得以满足。

    代码实现

    代码实现同样也不是本文的重点,你可以参考可以参考这篇博客或者这篇博客。如果你对线性基的构造比较熟悉,你可以轻松地判断一个数是否能被其他的几个数线性表示,有了这一手段,你就可以实现BB'的构造以及交的求解了。

    展开全文
  • 从该点出发,作任意方向的一根射线, 考察此射线与三维物体各面的交点数, ...如果在最小包围长方体之外,当然就在三维物体之外,这时就不用再对射线和各面之间一一求交了。 这个题目的繁琐性,在于要考察
    从该点出发,作任意方向的一根射线,
    考察此射线与三维物体各面的交点数,
    如果总数=0或其它偶数,则在三维物体之外,

    如果总数为奇,则在三维物体之内.

    为了减少时间,如果点的位置很有可能在三维物体之外时,你最好先测试一下此点是否落在三维物体的最小包围长方体之外?

    如果在最小包围长方体之外,当然就在三维物体之外,这时就不用再对射线和各面之间一一求交了。

    这个题目的繁琐性,在于要考察不少特殊情况,

    例如,下图中,直线L与三角形的交点是(1点)奇还(2点)偶?

    --------*------------------L
           * *
          *   *
         *     *
        *********

    这里应算2点,否则统计错了,答案就错了.

    无论是求直线与平面交点,还是求空间2平面的交线,都有类似问题.

    展开全文
  • 建立一个平面 通过四个点做垂直平面的直线,将其中一个垂线作为空间直角坐标系的z轴 将该轴的与平面的焦点作为圆心 量出四个点到平面的距离 将四个点两俩连接 出有交叉的两条线的直线表达式 两条线的焦点 ...
    建立一个平面 通过四个点做垂直平面的直线,将其中一个垂线作为空间直角坐标系的z轴
    
    
    将该轴的与平面的焦点作为圆心
    量出四个点到平面的距离
    将四个点两俩连接
    求出有交叉的两条线的直线表达式 求两条线的焦点 如果没有焦点说名不再一条线上
    
    
    展开全文
  • 光线追踪的效率问题一直以来都是关注的焦点,因为很多时候都会有非常多的求交运算要执行。目前几乎所有的加速算法都是尽量减少求交运算量,比如octree、kd-tree、包围盒(及层次包围盒)等。基于空间分割的算法最...

    本文属spanzhang(张友邦)原创,发布地址为:http://blog.csdn.net/spanzhang。转载或引用请注明原文之出处,谢谢!

    光线追踪的效率问题一直以来都是关注的焦点,因为很多时候都会有非常多的求交运算要执行。目前几乎所有的加速算法都是尽量减少求交运算量,比如octree、kd-tree、包围盒(及层次包围盒)等。基于空间分割的算法最重要的就是如何有效地分隔空间,让场景细节和主体脱离(划分在不同的层次中)。

    层次包围盒对空间的利用率非常高,如果场景中有多处细节中心,如何有效地构造包围盒层次来分别体现场景的细节就是算法成败的根本。当场将中有成千上万个多边形的时候,不可能手工构造,只能依靠算法来实现。在实践中,我实现了一个快速构造层次包围盒的算法,只需要通过一次扫描就能构造相对有效的层次包围盒模型。算法的核心主要是对细节的发现和分离。

    试验结果如下:

    5120个三角形,层次包围盒:5秒;普通算法:49秒。

     

    10804个三角形,采用层次包围盒:11秒;普通算法:1分46秒。

     

    可以看出,采用层次包围盒的算法快了10倍左右。对于图1来说,场景细节中心分散,并且没有主次。对于图2来说,场景细节中心集中,而且被外部更大的空间所包围。算法对这两种不同类型的场景都能很好的构造层次包围盒加速渲染。

    展开全文
  • Arcgis开发集锦.doc——

    2009-08-10 15:17:11
    Arcgis开发集锦。 目录 0 1. 用ArcEngine的工具条添加图层要素 1 2. ArcEngine中对Feature的编辑 3 3. Feature的概念 4 ...17. AE开发中矢量图层叠加求交分析 27 18. 矢量数据分析 30 19. GIS空间信息基本分析方法 31
  • 1. 试画图说明极线几何关系,并指出极点、极线...例如:假设已知点X,如何求x’ 1、点x和x’一定位于平面π上,而平面π可以利用基线CC’和图像点x的反投影射线确定 2、点x’又是右侧图像平面上的点,所以,点x’一...
  • 以4皇后为例,其他的N皇后问题以此类推。所谓4皇后问题就是求解如何...四皇后问题有很多种解法,这里主要介绍一种经典的解决方法:回溯法回溯法的基本思想是:可以构建出一棵解空间树,通过探索这棵解空间树,可以得...
  • 所谓4皇后问题就是求解如何在4×4的棋盘上无冲突的摆放4个皇后棋子。在国际象棋中,皇后的移动方式为横竖交叉的,因此在任意一个皇后所在位置的水平、竖直、以及45度斜线上都不能出现皇后的棋子,例子 要求编程...
  • ArcEngine开发集锦

    热门讨论 2010-07-22 23:55:11
    19. AE开发中矢量图层叠加求交分析 45 20. 矢量数据分析 50 21. GIS空间信息基本分析方法 50 22. 如何判断图形间的逻辑运算 53 23. AE中2种方式overlay 54 24. ArcEngine中实现捕捉功能 58 25. 在LAYER(i)上添加缓冲...
  • Arcgis开发集锦

    2011-02-17 17:30:36
    19. AE开发中矢量图层叠加求交分析 45 20. 矢量数据分析 50 21. GIS空间信息基本分析方法 50 22. 如何判断图形间的逻辑运算 53 23. AE中2种方式overlay 54 24. ArcEngine中实现捕捉功能 58 25. 在LAYER(i)上添加缓冲...
  • arcgis开发集锦

    2010-04-27 19:05:42
    19. AE开发中矢量图层叠加求交分析 45 20. 矢量数据分析 50 21. GIS空间信息基本分析方法 50 22. 如何判断图形间的逻辑运算 53 23. AE中2种方式overlay 54 24. ArcEngine中实现捕捉功能 58 25. 在LAYER(i)上添加缓冲...
  • 测量平差第一周作业

    2020-03-10 14:14:28
    由于观测结果不可避免的存在误差,因此,如何处理带有观测误差的观测值,找出待量的最佳估值。( 2 )对测量成果进行精度评定。 测量平差在GNSS原理与应用中的应用:单点定位、相对定位。 测量平差在摄影测量中的...
  • 那问题来了,如何求取这两个极值点及其对应的参数。 For example: 理想的极值点对应的参数一:alpha1=[20e3,10e3,-150,20,0] 第二个极值点对应的参数二:alpha2=[20e3,10e3,-150,20,1000] 利用Matlab自带的...
  • delphi 开发经验技巧宝典源码

    热门讨论 2010-08-12 16:47:23
    0001 如何定制工具栏 2 0002 如何定制组件面板 2 0003 如何定制代码编辑器 3 0004 保存自定义开发环境桌面 4 1.2 组件安装 4 0005 安装ActiveX组件 4 0006 安装不同类型的第三方组件 5 0007 在Delphi...
  • 0001 如何定制工具栏 2 0002 如何定制组件面板 2 0003 如何定制代码编辑器 3 0004 保存自定义开发环境桌面 4 1.2 组件安装 4 0005 安装ActiveX组件 4 0006 安装不同类型的第三方组件 5 0007 在Delphi...
  • 0001 如何定制工具栏 2 0002 如何定制组件面板 2 0003 如何定制代码编辑器 3 0004 保存自定义开发环境桌面 4 1.2 组件安装 4 0005 安装ActiveX组件 4 0006 安装不同类型的第三方组件 5 0007 在Delphi...
  • 0001 如何定制工具栏 2 0002 如何定制组件面板 2 0003 如何定制代码编辑器 3 0004 保存自定义开发环境桌面 4 1.2 组件安装 4 0005 安装ActiveX组件 4 0006 安装不同类型的第三方组件 5 0007 在Delphi...
  • 0001 如何定制工具栏 2 0002 如何定制组件面板 2 0003 如何定制代码编辑器 3 0004 保存自定义开发环境桌面 4 1.2 组件安装 4 0005 安装ActiveX组件 4 0006 安装不同类型的第三方组件 5 0007 在Delphi...
  • 0001 如何定制工具栏 2 0002 如何定制组件面板 2 0003 如何定制代码编辑器 3 0004 保存自定义开发环境桌面 4 1.2 组件安装 4 0005 安装ActiveX组件 4 0006 安装不同类型的第三方组件 5 0007 在Delphi...
  • 1.5.1如何估计算法运行时间 1.5.2最坏情况和平均情况的分析 1.5.3平摊分析 1.5.4输入大小和问题实例 思考题 第2章GIS算法的计算几何基础 2.1维数扩展的9交集模型 2.1.1概述 2.1.2模型介绍 2.1.3空间...
  • 数据结构演示软件

    2013-06-02 21:32:36
    (6)两个有序链表求交(ListIntersection_L) (7)两个有序链表求差(SubList_L) 3. 栈和队列 (1)计算阿克曼函数(AckMan) (2)栈的输出序列(Gen、Perform) (3)递归算法的演示  汉诺塔的算法(Hanoi) ...
  • (6)两个有序链表求交(ListIntersection_L) (7)两个有序链表求差(SubList_L) 3. 栈和队列 (1)计算阿克曼函数(AckMan) (2)栈的输出序列(Gen、Perform) (3)递归算法的演示  汉诺塔的算法(Hanoi) ...
  • 数据库状态及运行情况综合查看,使您了解ORACLE运行状况及空间、日志归档、数据文件等使用情况更直观,并可智能生成数据库热备份脚本和备份恢复方案,为您的数据库保驾护航,使您高枕无忧。 本系统可执行SQL分组语句后...
  • 现假定处理机字长为8位,男设计只用一个时间表来控制这些时钟进行的 执行管理程序 1)从能适应全部时钟级程序的周期出发,就定出该机采用的时钟中断周期。 (2)设计出上述程序的全部启动控制表格。 (1)根所要执行的...
  • 利用课表的编排,每个机房在不同的时间段内可以拥有不同的上机模式,再频繁复杂的上课与上机 换都能有条理的进行。 · 临时调课与预约服务 机房的课程安排经常出现临时性的调整,利用临时调课功能,可以调整...

空空如也

空空如也

1 2 3
收藏数 53
精华内容 21
关键字:

如何求交空间