3. 线性对象

浏览量:30

参考

      Thomas H. Cormen, et al. Introduction to algorithms. Vol. 2. Cambridge: MIT press, 2001.       David Eberly. "Distance between two line segments in 3D." Magic Software Inc, 1999.       Philip Schneider, and David H. Eberly. "Geometric tools for computer

spacer
浏览量:141

3.7. 线段集的交

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 3.7. 线段集的交 本小节重点解决求线段集中所有交点的问题,首先会先介绍线段集相交算法的发展历史及其应用,然后介绍Shamos-Hoey算法的基本思想,因为Bentley-Ottmann算法只是对它的扩展,最后着重介绍Bentley-Ottmann算法的基本思想和实现。 3.7.1. 线段集相交算法简介 求\(n\)条线段的相交测试,最多有\(n\left( {n - 1} \right)/2 = O({n^2})\)个交点,最坏情况下就需要一个时间复杂度为\(O({n^2})\)的算法。最简单的暴力算法就是分别对\(O({n^2})\)个线段对进行相交测试,并记录下所有的交点,但对于只有少数交点的线段集,则不需要对每个线段对进行相交测试。 设\(S\)是\(n\)条线段的集合,\(I\)是线段集\(S\)中所有的\(k\)个交点的集合,当\(k = \left( {n - 1} \right)n/2\)时,是最坏情况。早在1976年,Shamos&Hoey提出了通过扫描线的方法在时间为\(O(n\log n)\)、空间为\(O(n)\)内判定集合\(S\)中是否存在相交点的算法。3年后,Bentley&Ottmann对该算法进行了扩展,新的算法能在时间为\(O(n\log n + k\log n)\)、空间为\(O(n + k)\)内,计算集合\(S\)中所有的交点,Pach& Sharir(1991)、Brown(1981)把该算法的空间降低到了\(O(n)\)。由于Bentley-Ottmann算法容易理解、实现较为简单,因此在之后的几十年里得到广泛的应用,但是求线段集所有交点的问题的理论下限为\(O(n\log n + k)\),Bentley-Ottmann算法并没有达到理论上的下限,Chazelle(1986)提出了一种时间为\(O(n{\log ^2}n/\log \log n + k)\)的算法,进一步降低了时间复杂度。直至1988年,Chazelle& Edelsbrunner提出了时间复杂度达到最优的算法,但是他们提出的算法需要\(O(n + k)\)的空间,而且很难实现。后来,Balaban

spacer
浏览量:24

3.6. 直线之间的夹角

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 3.6. 直线之间的夹角 问题描述:求两条直线\({L_0}(s) = {P_0} + s{\vec d_0}\)和\({L_1}(t) = {P_1} + t{\vec d_1}\)之间的夹角。 这可以利用点积和角度之间的关系来计算,有: \ 图3.22两条方向相同的直线 图3.23两条方向相反的直线 角度值介于0到180。之间,主要依据两条向量\({\vec d_0}\)和\({\vec d_1}\)的方向,如图3.22所示,如果两条直线方向相同,它们间的夹角小于90。;相反,如图3.23所示,当它们的方向相反时,它们间的夹角大于90。。  

spacer
浏览量:60

3.5. 线性对象的相交

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 3.5. 线性对象的相交 本小节重点介绍二维空间上线性对象之间的相交测试算法,采用参数方程法可以解决二维空间上直线与直线、直线与射线、直线与线段、射线与射线、射线与线段、线段与线段的相交测试问题,对于线段与线段的相交测试问题,还介绍了交叉跨越法和Antonio极简法这两种算法,最后简单的介绍了三种解决三维空间上线性对象相交测试的方法。 3.5.1. 直线与直线的相交 问题描述:两条二维空间上的直线\({P_0} + s{\vec d_0}\)与\({P_1} + t{\vec d_1}\),\(t,s \in \left( { - \infty , + \infty } \right)\)之间的相交测试。 两条直线之间只有三种关系:相交、平行、重合。 在判定算法前,先介绍下二维向量的基础知识,二维向量叉积的计算结果是一个常数,计算公式为: \

spacer
浏览量:23

3.4. 线性对象间的距离

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 3.4. 线性对象间的距离 三维空间下的线性对象间才有距离的概念,三种线性对象中线段可以看成是最特殊的,而Eberly对三维线段与线段的距离计算作了详细的论证。本章节首先分析不同线性对象之间最小距离计算的数学原理,然后分别介绍各种线性对象之间距离计算的方法。 3.4.1. 线性对象间距离的数学原理 线性对象可以表示为\(L(s) = P + s\vec d\),直线、射线和线段之间的差别就在于\(s\)的取值范围,例如,若\(L(s)\)表示直线,则\(s \in ( - \infty , + \infty )\);若\(L(s)\)表示射线,则\(s \in \)。 图3.6 两条直线性对象之间的距离 设有两条线性对象\({L_0}(s) = {P_0} + s{\vec d_0}\)和\({L_1}(t) = {P_1} + t{\vec

spacer
浏览量:32

3.3. 点到线性对象的距离

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 3.3. 点到线性对象的距离 点到线性对象的距离问题包括二维和三维两种情况,三维空间上点到线性对象的距离计算方法与二维的相同,只是维度上存在差别,所以这里只阐述二维的情况。 3.3.1. 点到直线的距离 问题描述:求二维空间上的点\(Y\)到直线\(L(t) = P + t\vec d,t \in \left( { - \infty , + \infty } \right)\)的距离。 图3.3 点\(Y\)到直线\(L(t)\)的距离 如图3.3所示,设直线上与\(Y\)最近的点是\(L(\hat t)\),易知点\(L(\hat t)\)是点\(Y\)到直线上的投影,\(Y\)与\(L(\hat t)\)的连线,垂直于直线。因此可以得到等式: \

spacer
浏览量:37

3.2. 点与线性对象的关系判定

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 3.2. 点与线性对象的关系判定 问题描述:判定二维空间上的点\(Y\)与线性对象\(P + t\vec d\)的关系。 点与直线的关系就两种情况:在直线上和不在直线上。可以用式子(3.11)来判定,若\({\Delta _1} = 0\),则点\(Y\)在直线上;否则,点\(Y\)不在直线上。 \ \ 图3.2 点与线性对象的关系判定 点与射线的关系判定与此相似,不同的是,如果点\(Y\)在射线所在的直线上,但它还有可能不在射线上,如图3.2(a)所示,因此需要增加一步判定。如果\({\Delta _1} = 0 \wedge {\Delta

spacer
浏览量:35

3.1. 线性对象简介

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 3.1. 线性对象简介 3.1.1. 二维空间 二维空间下的线性对象包括:直线、射线、线段。直线可以用参数方程表示: \ \(P\)表示直线上的点,向量\(\vec d = ({d_x},{d_y})\)表示直线的方向,通常情况下,直线参数方程采用这种方法来定义。如图3.1(a)所示,将直线的方向沿着逆时针方向旋转90度,就得到法向量\(\vec n = ( - {d_y},{d_x})\),另外一种采用法向量的直线定义方法,称为法线形式,表达式是 \

spacer