精华内容
下载资源
问答
  • 平面几何:两点确定一条直线

    千次阅读 2018-11-08 23:02:00
    个不同A,B确定一条直线,AB相同返回的值全0 直线方程:Ax+By+c=0 A = y2 - y1; B = x1 - x2; C = -Ax1 - By1 = x2y1 - x1y2; 证明之后补上; Line LineMake(Point A, Point B) { Line l; l.A = B.y - A.y; l.B...

    两个不同点A,B确定一条直线,AB相同返回的值全0

    • 直线方程:Ax+By+c=0
    • A = y2 - y1;
    • B = x1 - x2;
    • C = -Ax1 - By1 = x2y1 - x1y2;

    证明之后补上;

    Line LineMake(Point A, Point B)
    {
    Line l;
    l.A = B.y - A.y;
    l.B = A.x - B.x;
    l.C = B.x * A.y - A.x * B.y;
    return l;
    }

    展开全文
  • 变分法证明两点之间线段最短

    万次阅读 2019-01-08 16:27:33
    在Part 2., 我们会以用这次介绍的内容和上述方程解决两点之间直线最短的问题为开头,继续介绍变分法。 ----------------------------------------------------------------------------------------------------...

    传送门https://zhuanlan.zhihu.com/yueaptx

    变分法简介Part 1.(Calculus of Variations)

    Dr.Stein

    Dr.Stein

    计算力学

    ​关注他

    283 人赞了该文章

    1. 泛函数 (Functionals)

     

    简而言之,泛函数是函数的函数,即它的输入是函数,输出是实数。而这个输出值取决于一个或多个函数(输入)在一整个路径上的积分而非像一般函数一样取决于离散的变量。这样说可能还是比较抽象,不过坚持看到下文的Example 1就可以更好理解了。

    通常在变分法中,泛函数是一个积分,记做I

    I(y)=\int_{x1}^{x2}Fdx

    其中我们想要通过选择被积函数F来最大化或最小化泛函数I的值。同时我们称F为拉格朗日函数(Lagrange function)。F可以是函数y(x)y(x)各阶导数的函数(以下y(x)均简写成y)。为了说明方便,我们先姑且设Fyy'的函数,所以我们可以进一步将泛函数I写成:

    I(y)=\int_{x1}^{x2}F(y,y';x)dx

    积分里面我用分号;将x和前面的y隔开代表yy'x的函数。一般Fy的函数关系是已知的,所以想要最大或最小化泛函数,实际上是通过选择适当的函数y(x)

    为了透彻理解这个概念,我们可以来看一个简单的例子。

    Example 1.

    一个最简单直观的例子是求两个固定点之间的最短路径。当然大家都知道两点之间直线最短,这里可以用变分法做出解释。

    如上图所示路径是一任意路径,我们取区中一小段微元ds,可以容易计算微元断的长度为:

    ds^2=dx^2+dy^2=[1+(y')^2]dx^2,即:

    ds=\sqrt{1+(y')^2}dx

    积分得到总的路径长度为:

    L=\int_{x1}^{x2}ds=\int_{x1}^{x2}\sqrt{1+(y')^2}dx

    这个例子中,L是泛函数,\sqrt{1+(y')^2}是拉格朗日函数F,我们想要找一个函数y(x)使得泛函数L的值最小。这次Part 1.的任务就是为解决这个问题做准备。Part 2.中我们会用变分法证明这个y(x)确实是直线的方程。

    2. 泛函数的极值

     

    这里重申下,泛函数I在区间[x_1,x_2]上的值取决于积分路径的选择,即取决于函数y(x)的选择。我们有理由假设存在一个这样的y(x),可以使得泛函数I取到极值。而在这个y(x)附近的任意路径我们记做\tilde{y}(x)。另外,我们假设y(x)两阶可微。通过引入一个微小量\epsilon\ll 1和一个任意可微函数\eta(x),我们可以用y(x)表示\tilde{y}(x):

    \tilde{y}(x)=y(x)+\epsilon\eta(x)

    这样做的好处是对于一个给定的\eta(x),我们可以通过改变\epsilon的值来得到无穷多的路径,同时对于任何\eta(x),当\epsilon=0的时候,\tilde{y}(x)y(x)重合。

    图像直观表示如下图:

    由于在边界条件的限制,\eta(x_1)=\eta(x_2)=0。这样就能保证\tilde{y}(x)可以通过两个固定端点。

    这时我们可以说,y(x)所对应的泛函数I的值是泛函数\tilde{I}=\int_{x_1}^{x_2}F(\tilde{y},\tilde{y}';x)dx的极值。我们可以进一步用\epsilon表示\tilde{I}

    \tilde{I}=\int_{x_1}^{x_2}F(\tilde{y},\tilde{y}';x)dx=\int_{x1}^{x_2}F(y+\epsilon\eta,y'+\epsilon\eta';x)dx

    虽然y(x)未知,但是根据之前的合理假设,y(x)是一个存在的确定函数。所以根据上式,如果给定一个特定的\eta(x)\tilde{I}的变化只取决于\epsilon的变化。所以我们现在可以把\tilde{I}看做是\epsilon的函数。用泰勒展开公式将\tilde{I}\epsilon=0处展开得到:

    \tilde{I}(\epsilon)=\tilde{I}|_{\epsilon=0}+(\frac{d\tilde{I}}{d\epsilon})\Big|_{\epsilon=0}\cdot\epsilon+ (\frac{d^2\tilde{I}}{d\epsilon^2})\Big|_{\epsilon=0}\cdot\frac{\epsilon^2}{2!} +\cdot \cdot \cdot =\tilde{I}_0+\tilde{I}_1\epsilon+\tilde{I}_2\epsilon^2+\cdot \cdot \cdot

    很明显,当\epsilon=0时,\tilde{I}|_{\epsilon=0}=I,带入上式可得到:

    \tilde{I}-I=\tilde{I}_1\epsilon+\tilde{I}_2\epsilon^2+\cdot \cdot \cdot

    这里我们记\delta I=\tilde{I}_1\epsilon=\frac{d\tilde{I}}{d\epsilon}\Big|_{\epsilon=0}\cdot\epsilon,并称之为一阶变分。同理二阶变分为\delta I^2=\tilde{I}_2\epsilon^2

    (这里插一句变分和微分的区别。变分在上图的直观解释是\tilde{y}y在竖直方向上的距离,称之为\delta y,所以这个差是在同一个x上计算的。而微分则是由于x的微小变动引起的y的变动。)

    然后我们可以类比求函数极值时的做法。求函数极值时,我们会令函数的一阶导数为零。这里同样,为了求泛函数\tilde{I}的极值,我们令一阶变分\delta I=0。现在我们计算化简\delta I:

    \delta I=(\int_{x_1}^{x_2}\frac{d\tilde{F}}{d\epsilon}\Big|_{\epsilon=0} dx)\cdot\epsilon
    \frac{d\tilde{F}}{d\epsilon}\Big|_{\epsilon=0} \cdot\epsilon=(\frac{\partial\tilde{F}}{\partial\tilde{y}}\cdot\frac{d\tilde{y}}{d\epsilon}+  \frac{\partial\tilde{F}}{\partial\tilde{y'}}\cdot\frac{d\tilde{y'}}{d\epsilon})\Big|_{\epsilon=0}\cdot\epsilon

    因为 \tilde{y}(x)=y(x)+\epsilon\eta(x), 不难得到:\frac{d\tilde{y}}{d\epsilon}=\eta,\frac{d\tilde{y'}}{d\epsilon}=\eta',另外我们有\delta y=\epsilon \eta,\delta y'=\epsilon\eta'

    又因为当\epsilon\rightarrow 0时,\tilde{F}\rightarrow 0, \tilde{y}\rightarrow y,\tilde{y}'\rightarrow y',将这些式子带入原式可以得到:

    \delta I=\int_{x_1}^{x_2}(\frac{\partial F}{\partial y}\delta y+\frac{\partial F}{\partial y'}\delta y')dx

    终于到最后一步啦,分部积分一下得到:

    \delta I=\int_{x_1}^{x_2}(\frac{\partial F}{\partial y}-\frac{d}{dx}(\frac{\partial F}{\partial y'} ))\delta ydx+\frac{\partial F}{\partial y'}\delta y\Big|_{x_1}^{x_2}

    \delta I=0就可以解得最小化泛函数的y啦。我们注意到\delta I有两个部分。对于第一个积分部分,由于\delta y是任意的,所以要想使这个部分等于零,需要保证^{[1]}

    \frac{\partial F}{\partial y}-\frac{d}{dx}(\frac{\partial F}{\partial y'} )=0 (x_1\leq x\leq x_2)

    这就是传说中的欧拉-拉格朗日方程(E-L equation)。

    而第二部分等于零则是边界条件。

    在Part 2., 我们会以用这次介绍的内容和上述方程解决两点之间直线最短的问题为开头,继续介绍变分法。

    ---------------------------------------------------------------------------------------------------------------------------

    注[1]:

    假设x_1x_2是给定的常数,\phi(x)是一个特定的在x_1\leq x\leq x_2上连续的函数,那么如果对于任意连续可微的函数\eta(x)都成立\int_{x_1}^{x_2}\phi(x)\eta(x)dx=0,则\phi(x)=0 (x_1\leq x\leq x_2)。

    (任意函数和一个非零的特定函数的乘积仍是任意函数,由于无法保证任意函数的积分是零,所以这个特定函数必须在这个区间上恒等于零使得乘积为零,这样可以保证积分为零。)

    展开全文
  • 直线和线段相交平面相交直线-平面相交平面相交三个平面相交实现intersect2D_2Segments()inSegment()intersect3D_SegmentPlane()intersect3D_2Planes()参考文献几何图元的相交是许多计算机图形学和建模应用中的重要...

    直线和线段相交

    平面相交

    直线-平面相交

    两平面相交

    三个平面相交

    实现

    intersect2D_2Segments()

    inSegment()

    intersect3D_SegmentPlane()

    intersect3D_2Planes()

    参考文献

    几何图元的相交是许多计算机图形学和建模应用中的重要组成部分。在这里我们来看一下最简单的 2D 和 3D 线性图元:直线、线段和平面的算法。

    直线和线段相交

    为了计算2D和3D中直线和线段的相交点,使用参数方程表示法是最好的。其它表示法在《计算几何算法2. 关于线和点到线的距离》一节中已经讨论过。本节研究如何从其它表示法转换到参数表示法。

    在任意维度中,由两点P0、P1定义的直线参数方程式,当参数s为实数且u=P1-P0为直线的方向向量时可以表示为

    P(s) = P0+ s(P1-P0) = P0+ su,

    当P(s)是有限线段P0P1上的一个点且01,P(s) 在线段P1的外侧。

    让两条直线满足方程:P(s) = P0 + s (P1-P0) 和 Q(t) = Q0 + t (Q1-Q0),它们中的一条或者全部是有限线段或者射线。当且仅当方向共线时,直线平行,也就是说当两个向量u=P1-P0 和v=Q1-Q0 成线性关系时,即u=Cv,C为实数。 对于u=(uk)和v=(vk),t意味着所有比值uk/vk 相等,或者对于所有的k,u1/v1=uk/vk 都成立,这等同于所有满足u1vk-ukv1=0的情况。在2D中,对于u=(u1,u2) 和v=(v1,v2),u⊥· v = u1v2-u2v1 = 0 这里u⊥=(-u2,u1)垂直于u(⊥称为正交运算符)。。这种情况说明在欧几里得平面上当两条都垂直于相同的方向向量u⊥时,两条直线是平行的。当这种情况成立时,两条直线既不重合也不相交。

    通过验证点P0是否同时在直线和另外一条直线Q(t)上就可以很容易的验证两条直线是否重合。也就是说,存在一个参数t0 使等式P0=Q(t0)=Q0+t0v成立。如果w=(wk)=P0-Q0,对于某个参数t0存在等式w=t0v,等同于对于任意的参数k 存在等式w1vk-wkv1=0。在2D中,这是正交运算情况:w⊥· v = w1v2-w2v1 = 0。如果这些条件成立,可以解出参数t0的值,和无限的直线式重合的。如果一条直线(而不是其它)是一条有限线段,它们重合相交。然而,如果两条直线都是有限线段,它们就可能重叠也可能不重叠。在这种情况下,解出t0和t1 的值使得满足条件 P0=Q(t0) 和P1=Q(t1)。如果线段区间[t0,t1] 和[0,1]不相交,直线就不相交。否则,对区间进行相交运算得出[r0,r1] = [t0,t1] ∩ [0,1]。相交线段就是Q(r0)Q(r1) = P0P1 ∩Q0Q1。这在任何维度空间里都成立。

    当两条直线不平行时,它们可能相交于特殊的一点。在2D欧几里得空间,它们总会相交。在更高维度,它们可能彼此错过不相交。但是如果它们的确相交,它们在2D平面上的线性投影也会相交。所以,一条线段简单的约束到两个坐标点(u 或者v不为0),通过P(sI)和Q(tI)计算出2D相交点,然后验证是否P(sI)=Q(tI) 对所有的坐标点都成立。为了计算出2D相交点I=P(sI)=Q(tI),考虑如下图中的两条直线和相关向量:

    为了确定sI,在w=P0-Q0的情况下,我们得出向量等式P(s)-Q0 = w + su。在相交点,向量 P(s)-Q0 垂直于v⊥,这等同于v⊥· (w+su) = 0。求解等式,我们得到:

    注意,只有像之前讨论过的直线平行时,v⊥· u = 0。相似地,求解Q(tI),我们得出:

    当u⊥· v = – v⊥· u时,分母和标志相同,只有在我们想同时知道sI 和 tI时,才计算分母。

    如果两条直线中的一条是有限线段(或是一条射线),设为P0P1,然后当且仅当0<=sI<=1 (或对于射线有 sI>=0)时相交点在线段的内部。如果两条线都为有限线段,就要求解出参数sI 和 tI,它们都必须在区间[0,1]之间,线段才有可能相交。尽管这听起来足够简单,但是两条线段相交的代码需要一些技巧,因为有很多特殊的情况需要验证(参见我们的2D线段相交实现例子)。

    平面相交

    直线–平面相交

    在3D中,直线 L或者平行于平面π或者与平面π相交于一点。假设 L满足下列参数方程 P(s) = P0 + s(P1-P0) = P0 + su,给定点V0在平面p上,法向量为 n。我们首先检查L是否平行于平面π,如果n·u=0,那就意味着直线法向量 u垂直于平面法向量n。如果成立,直线 L和平面π平行,即或者不相交,或者完全在平面p内。通过验证L上是否存在点P在平面π内,可以判断L和平面π是否相交,也就是说是否满足隐式直线方程:n·(P-V0) = 0。

    如果直线和平面不平行,即直线L和平面π相交于点P(sI),利用类似于2D中两条直线相交的方法,我们可以计算出点P(sI)的值。如图所示:

    在相交点,当w=P0-V0,向量P(s)-V0 = w+su垂直于n。这等同于点乘:n · (w+su) = 0。求解得出:

    如果L 是从P0到P1的有限线段,我们必须检查sI是否满足 0<=sI <=1,从而证明线段和平面是否相交。对于正方向的射线,当sI >=0时,和平面相交。

    两平面相交

    在3D中,两平面 π1和π2或者平行或者相交于直线L。假设 πi(i=1,2)是由点Vi 和法向量ni所确定, 满足方程:ni · P + di = 0。只要平面π1和π2的法向量平行,它们就平行,等同于n1×n2 = 0。在软件中,我们经常用是否|n1×n2| < δ当除以δ时是否引起溢出,这是判断 n1 和 n2 是否平行的条件。如果不平行的话,u = n1×n2 >= δ > 0 是相交直线L的方向向量,因为 u 同时垂直于n1 和 n2,也就如图中所示的那样平行于两个平面。 如果 |u| 是个小数,最好将它缩放至|u| = 1,以保证u是单位方向向量。

    在计算n1×n2(3次相加和6次相乘)后,为了完全确定相交直线,我们仍然需要在上面找到一个特殊点;也就是说,我们需要找到同时在两平面上的点P0=(x0,y0,z0)。我们可以通过求解关于p1和p2的隐式方程来得到P0。但是这只有两个方程,却需要求解3个未知数,既然点P0 能够在任意用于其它自由度的一维直线L上,所以我们需要另外一个条件来求解出点P0。有以下几种方法可以做到这一点:

    (A)直接使用线性方程。将其中一坐标点设为0,即为z0=0,然后解出另外两个点。但是这只在L和平面z0=0相交时适用。当u =(ux,uy,uz)中的z值不为0时为真。所以,我们必须选择u的非零坐标点,然后设P0 = 0。我们应该选择拥有最大绝对值的坐标点,因为这会是最健壮的。如果uz != 0,P0=(x0,y0,0)在L上。求解两方程:a1x0+b1y0+d1=0 和a2x0+b2y0+d2=0,得出:

    还有L的参数方程:

    这里的分母和u非零的第三个坐标点是相等的。所以,忽视对非零坐标点的验证,这次求解的所有运算等于有5次相加和12次相乘。

    (B)直线相交点。如果知道平面上一条特定的直线(例如,平面上的两个点),和这条直线和其他平面相交,那么相交点”I”同时位于两个平面上。如此,这个点就位于两平面相交线上,L 的参数方程可以表示为:P(s) = I + s(n1×n2)。为了计算n1×n2和相交点(给定直线的),我们要进行11次加法运算和19次乘法运算。

    在平面内构建一条和其他平面相交的直线的一种方法是,将此平面的法向量投射到另外一个平面上。给定一条直线,令其始终垂直于两平面的相交线。因此,n2在平面π1上的投影确定了和π2相交的直线。更具体来说,将两点0=(0,0,0)和n2=(nx2,ny2,nz2)分别投影到π1 (0) 和π1 (n2) 上。投影到π1上的直线是L1: Q(t) = π1 (0) + tπ1(n2),它和π2的相交线能被计算出来。在最有效的情况下,也就是当n1和n2 都为单位法向量并且常数p1(0) 被预先存储起来的情况下,整个运算包括17次相加运算和22次相乘运算。

    (C)3平面相交于一点。当法向量n3 = n1×n2和d3=0 (意味着通过原点)时,可以选择用隐式方程式表达的第三个平面π3。这一直成立因为:(1) L垂直于π3这样就和π3相交,(2) 向量n1,n2和n3线性无关。也就是说平面π1,π2和π3相交于唯一点P0,P0必然也在L上。当π3上的d3=0时,用3平面相交线的方程式,我们可以得出:

    还有L的参数方程:

    .

    这次求解共有11次相加和23次相乘。

    当n1和n2为单位法向量且n1· n2 = cos q(q是两向量之间的夹角)时,这个方程式可以被简化。然后,n1· n1 = n2· n2 = 1,和|n1×n2|2 = sin2 q = 1 – cos2 q = 1 – (n1· n2)2 作为它的分母。最终,我们利用叉乘的右结合性,对于任意的3D向量a,b,和c,等式a×(b×c) = (a· c)b – (a· b)c始终成立。应用到分子上,经过简化可以得出:(d2n1–d1n2)×(n1×n2) = (d2 cos q –d1) n1 + (d1 cos q –d2) n2。于是,

    这种解决方案描述了L上的点P0作为向量n1和n2的线性组合,这是通过原点的平面p3的基础生产算法。运算次数为11次相加+20次相乘。

    最后要说的一点是,最有效率的解决方法是解决方法(A),这种方法计算出相交线的方程只用到了5次相加和12次相乘。

    三平面相交

    在3D中,三平面p1,p2 和p3有几下几种方式能够相交(或者不想交):

    几何关系

    交集

    数学表达

    三平面平行

    nj×nk=0 (j,k=1,3)

    三平面相交

    一个平面

    n1·V1=n1·V2=n1·V3

    三平面不相交

    n1·V1¹n1·V2¹n1·V3¹n1·V1

    只有两个平面平行,第三个平面和其余的两个平面分别相交于一条直线 [注:两个平行的平面有可能相交]

    2条平行的直线

    [重合部分 => 1 条直线]

    只有当nj×nk=0 (j¹k)成立

    没有两个平面平行,它们两两相交于三条直线。

    nj×nk¹0 (j¹k)

    相交线互相平行

    n1·(n2×n3)=0

    相交线相交

    1条直线

    从一条直线上测试一点

    相交线不想交

    3条平行的直线

    相交线都不平行

    一个特定的点

    n1·(n2×n3)¹0

    如图所示:

    应该首先测试相交点的最普遍的情况,也就是说n1·(n2×n3)¹0,它可以排除其它的情况。当相交点是一个特定点时,它由以下公式给出:

    可以通过P0是否满足p1,p2 和p3的参数方程来验证。

    然而,当分母n1·(n2×n3)非常小时,在计算性能上存在问题。在这种情况下,最好的办法是取其中两个平面的相交线,然后计算这条直线和第三个平面的相交点。

    程序实现

    // Point and Vector with

    // coordinates {float x, y, z;}

    // operators for:

    // == to test equality

    // != to test inequality

    // Point = Point ± Vector

    // Vector = Point - Point

    // Vector = Scalar * Vector (scalar product)

    // Vector = Vector * Vector (3D cross product)

    // 直线、射线和线段由点定义{Point P0, P1;}

    // (直线是无穷的,射线和线段开始于P0)

    // (射线从P1向外延伸,但是线段结束于P1)

    // 平面由一个点和一个方向向量定义{Point V0; Vector n;}

    //===============================================================

    #define SMALL_NUM 0.00000001 // anything that avoids division overflow

    // 点乘(3D)

    #define dot(u,v) ((u).x * (v).x + (u).y * (v).y + (u).z * (v).z)

    #define perp(u,v) ((u).x * (v).y - (u).y * (v).x) //正交运算(2D)

    // intersect2D_2Segments():2D有限线段相交

    // 输入:两条有限线段S1和S2

    // 输出: *I0 = 相交点(如果存在)

    // *I1 = 相交线段的终点 [I0,I1] (如果存在)

    // 返回值: 0=disjoint (no intersect)

    // 1=intersect in unique point I0

    // 2=overlap in segment from I0 to I1

    int

    intersect2D_Segments( Segment S1, Segment S2, Point* I0, Point* I1 )

    {

    Vector u = S1.P1 - S1.P0;

    Vector v = S2.P1 - S2.P0;

    Vector w = S1.P0 - S2.P0;

    float D = perp(u,v);

    // 验证是否平行(包含一个点的情况)

    if (fabs(D) < SMALL_NUM) { // S1 和 S2 平行 if (perp(u,w) != 0 || perp(v,w) != 0) { return 0; // 不共线 } // they are collinear or degenerate // check if they are degenerate points float du = dot(u,u); float dv = dot(v,v); if (du==0 && dv==0) { // 线段点集 if (S1.P0 != S2.P0) // 在特殊点上 return 0; *I0 = S1.P0; // 在相同点上 return 1; } if (du==0) { // S1 作为一个单独的点 if (inSegment(S1.P0, S2) == 0) // 不在 S2上 return 0; *I0 = S1.P0; return 1; } if (dv==0) { // S2 作为一个单独的点 if (inSegment(S2.P0, S1) == 0) // 不在 S1上 return 0; *I0 = S2.P0; return 1; } // 它们为共线线段 – 部分重叠 (或者不重叠) float t0, t1; Vector w2 = S1.P1 - S2.P0; if (v.x != 0) { t0 = w.x / v.x; t1 = w2.x / v.x; } else { t0 = w.y / v.y; t1 = w2.y / v.y; } if (t0 > t1) { // t0 必须比 t1小

    float t=t0; t0=t1; t1=t; // 如果t0 不比 t1小就交换

    }

    if (t0 > 1 || t1 < 0) {

    return 0; // 不重叠

    }

    t0 = t0<0? 0 : t0; // 控制最小值为 0 t1 = t1>1? 1 : t1; // 控制最大值为 1

    if (t0 == t1) { // 交集是一个点

    *I0 = S2.P0 + t0 * v;

    return 1;

    }

    // 在有效子线段内部分重叠

    *I0 = S2.P0 + t0 * v;

    *I1 = S2.P0 + t1 * v;

    return 2;

    }

    // 线段倾斜,可能相交于一点

    // 取得S1的相交参数

    float sI = perp(v,w) / D;

    if (sI < 0 || sI > 1) // 和 S1没有相交

    return 0;

    // get the intersect parameter for S2

    float tI = perp(u,w) / D;

    if (tI < 0 || tI > 1) // 和 S2没有相交

    return 0;

    *I0 = S1.P0 + sI * u; // 计算 S1 的相交点

    return 1;

    }

    //===============================================================

    // inSegment(): 验证点是否在线段内

    // 输入: a point P, and a collinear segment S

    // 返回值: 1 = P is inside S

    // 0 = P is not inside S

    int

    inSegment( Point P, Segment S)

    {

    if (S.P0.x != S.P1.x) { // S is not vertical

    if (S.P0.x <= P.x && P.x <= S.P1.x) return 1; if (S.P0.x >= P.x && P.x >= S.P1.x)

    return 1;

    }

    else { // S is vertical, so test y coordinate

    if (S.P0.y <= P.y && P.y <= S.P1.y) return 1; if (S.P0.y >= P.y && P.y >= S.P1.y)

    return 1;

    }

    return 0;

    }

    //===============================================================

    // intersect3D_SegmentPlane(): 线段和平面相交

    // Input: S = a segment, and Pn = a plane = {Point V0; Vector n;}

    // Output: *I0 = the intersect point (when it exists)

    // Return: 0 = disjoint (no intersection)

    // 1 = intersection in the unique point *I0

    // 2 = the segment lies in the plane

    int

    intersect3D_SegmentPlane( Segment S, Plane Pn, Point* I )

    {

    Vector u = S.P1 - S.P0;

    Vector w = S.P0 - Pn.V0;

    float D = dot(Pn.n, u);

    float N = -dot(Pn.n, w);

    if (fabs(D) < SMALL_NUM) { // 线段和平面平行

    if (N == 0) // 线段在平面内

    return 2;

    else

    return 0; // 没有交集

    }

    // they are not parallel

    // compute intersect param

    float sI = N / D;

    if (sI < 0 || sI > 1)

    return 0; // 没有交集

    *I = S.P0 + sI * u; // 计算线段的相交点

    return 1;

    }

    //===============================================================

    // intersect3D_2Planes(): 两平面相交

    // Input: two planes Pn1 and Pn2

    // Output: *L = the intersection line (when it exists)

    // Return: 0 = disjoint (no intersection)

    // 1 = the two planes coincide

    // 2 = intersection in the unique line *L

    int

    intersect3D_2Planes( Plane Pn1, Plane Pn2, Line* L )

    {

    Vector u = Pn1.n * Pn2.n; // 叉乘

    float ax = (u.x >= 0 ? u.x : -u.x);

    float ay = (u.y >= 0 ? u.y : -u.y);

    float az = (u.z >= 0 ? u.z : -u.z);

    // test if the two planes are parallel

    if ((ax+ay+az) < SMALL_NUM) { // Pn1 和 Pn2 近似平行 // test if disjoint or coincide Vector v = Pn2.V0 - Pn1.V0; if (dot(Pn1.n, v) == 0) // Pn2.V0 在 Pn1内 return 1; // Pn1 and Pn2 重合 else return 0; // Pn1 and Pn2 不相交 } // Pn1 和 Pn2 相交于一条直线 // 首先定义叉乘的最大坐标值 int maxc; // 最大坐标值 if (ax > ay) {

    if (ax > az)

    maxc = 1;

    else maxc = 3;

    }

    else {

    if (ay > az)

    maxc = 2;

    else maxc = 3;

    }

    // 接下来,取得相交线上的一点

    // 将最大值置为0,求解出另外两个值

    Point iP; // 相交点

    float d1, d2; // 两个平面方程中的常数

    d1 = -dot(Pn1.n, Pn1.V0); // 注: 事先在平面内定义

    d2 = -dot(Pn2.n, Pn2.V0); // 同上

    switch (maxc) { // 选择最大坐标

    case 1: // 相交于 x=0

    iP.x = 0;

    iP.y = (d2*Pn1.n.z - d1*Pn2.n.z) / u.x;

    iP.z = (d1*Pn2.n.y - d2*Pn1.n.y) / u.x;

    break;

    case 2: // 相交于 y=0

    iP.x = (d1*Pn2.n.z - d2*Pn1.n.z) / u.y;

    iP.y = 0;

    iP.z = (d2*Pn1.n.x - d1*Pn2.n.x) / u.y;

    break;

    case 3: // 相交于 z=0

    iP.x = (d2*Pn1.n.y - d1*Pn2.n.y) / u.z;

    iP.y = (d1*Pn2.n.x - d2*Pn1.n.x) / u.z;

    iP.z = 0;

    }

    L->P0 = iP;

    L->P1 = iP + u;

    return 2;

    }

    //===============================================================

    参考文献

    Foley, van Dam, Feiner & Hughes, 计算机图形学( C语言第二版), 3.12节 “线裁减” (1996)

    Francis Hill, “正交点乘运算的乐趣” in 图形几何IV (1994)

    Michael Mortenson, 计算机图形学手册: 几何和数学 (1990)

    Joseph O’Rourke, 基于C的计算几何(第二版), 第7章 “查询和相交” (1998)

    展开全文
  • 二、逐比较法圆弧插补圆弧插补加工:是将加工到圆心的距离与被加工圆弧的名义半径相比较,并根据偏差大小确定坐标进给方向,以逼近被加工圆弧。下面以第一象限逆圆弧为例,讨论圆弧的插补方法。如图 3 — 4 所示...

    二、逐点比较法圆弧插补

    圆弧插补加工:

    是将加工点到圆心的距离与被加工圆弧的名义半径相比较,并根据偏差大小确定坐标进给方向,以逼近被加工圆弧。下面以第一象限逆圆弧为例,讨论圆弧的插补方法。

    如图 3 — 4 所示,设要加工圆弧为第一象限逆圆弧 AB ,原点为圆心 o ,起点为 A(

    1808afad4a1935f9cbbe8fa0baf6021a.gif) ,终点为 B(

    2008621155254201105172315393796.gif) ,半径为 R 。瞬时加工点为 P(

    68406becda28b3e59aa3891bdfcc41f8.gif) ,点 P 到圆心距离为

    2008621155332201105172315393798.gif

    若点 P 正好在圆弧上,则有

    b67e02e76b5ecbec4e85ddb51e84ebc0.gif

    b8166f4fc31f7af7679886b22d2a31e8.gif

    图 3 — 4 逐点比较法第一象限圆弧插补 即

    405440a2c4b55a9296ea687e4a174ac3.gif

    若点 P 在圆弧外侧,则有

    39101baef56bfb65e0b1a4ee5efedb6e.gif

    6423b5a42c861cd3257d2391abe31065.gif

    若点 P 在圆弧内侧,则有

    41c1745baf1849acc5d44951ad4dc7ce.gif

    22426b7f464e1dd28433ea039c58419c.gif

    显然,若令

    bcb982e92e64011bdc0963bcb9ef4e85.gif(3 — 4)

    则有:

    e6427d5689ae9ef240a73b7386796629.gif,则点 P 在圆弧上;

    fa16185f885bbea23c9c377c15919d90.gif,则点 P 在圆弧外侧;

    2008621153739201105172315393809.gif,则点 P 在圆弧内侧。

    bfa659dcb4aa280460aea78d43037036.gif时,为逼近圆弧,应向 --X 方向进给一步;当

    2008621153739201105172315393809.gif时,应向 +y 方向进给一步。这样,就可获得逼近圆弧的折线图。

    与直线插补偏差计算公式相似,圆弧插补的偏差计算也采用递推的方法以简化计算。若加工点

    f09def1b7345b53e7c74f764a11a51e1.gif

    为逼近该圆需沿 --X 方向进给一步,移到新加工点

    a89545e3e7135c901031e3d36193b374.gif,此时新加工点的坐标值为

    3abb0f65ba5532f73d66919133a4c2df.gif

    200862115586201105172315393815.gif

    新加工点的偏差为

    3ee84961d4e86cb5412a4db93151709a.gif

    e2d7a2cc9f13c92a9bcfae8f6198afc5.gif

    95c68afd4b9dc6b8116405e753a33195.gif

    若加工点

    fbeb0ffbcdcd87d3717c02b3dd218c4f.gif

    为逼近该圆需沿十 y 方向进给一步,移到新加工点

    86599d5f24ed35a7e43386621917264e.gif,此时新加工点的坐标值为

    9cf5a52ee309686ee094058f20a9edbd.gif

    200862116018201105172315393822.gif

    新加工点的偏差为

    6c931a6f02a025a9b131349f1d130749.gif

    cb64339a72b6dcc27e2324d9533e6ce3.gif

    2d477e4389b73ca06a62877ceb4bbe6c.gif

    从式 (3 — 5) 和式 (3 — 6) 两式可知,递推偏差计算仅为加法 ( 或减法 ) 运算,大大降低了计算的复杂程度。由于采用递推方法,必须知道开始加工点的偏差,而开始加工点正是圆弧的起点,故

    8ba2de8af7dca7e987acc56e4de6d541.gif。除偏差计算外,还要进行终点判别。一般用 x 、 y 坐标所要走的总步数来判别。令

    200862116129201105172315393827.gif,每走一步则 J 减 l ,直至 J=0 到达终点停止插补。

    综上所述,逐点比较法圆弧插补与直线插补一样,每走一步都要完成位置判别、坐标进给、偏差计算、终点判别四个步骤 ( 节拍 ) 。图 3 — 5 所示为第一象限逆圆弧逐点比较法插补的程序框图。下面举例说明圆弧插补的过程。

    be3af73ffef4035fb13ceae849d01084.png

    例 3-2 设要加工圆弧为第一象限逆圆弧 AB ,如图 3-6 所示。原点为圆心,起点为 A(6 , 0) ,终点为 B(0 , 6) ,终点计数值

    311db2b126d569b0888cc9a991ac02c7.gif,加工过程的运算节拍如表 3 — 3 所示。

    b9610eb05195865d612ea78680590479.gif

    68d9012ec81fafd4b35d44b79bbaeef2.png

    对于第—象限的顺圆及其第二、第三、第四象限的顺圆、逆圆插补计算,可根据相同原理得到其插补计算方法。图 3 — 7 所示为四个象限圆弧插补的进给方向示意图。表 3 — 4 列出了四 个象限的顺圆、逆圆的圆弧插补偏差计算公式,其中偏差计算

    36a22621d33fbf18b0e545da8e5f4ff5.png

    公式中的

    f9e4c47279d5d6c17740e92aeae546c1.gif均为绝对值。表中 SRl 、 SR2 、 SR3 、 SR4 分别代表第一、第二、第三、第四象限顺圆弧, NRI 、 NR2 、 NR3 、 NR4 分别代表第一、第二、第三、第四象限逆圆弧。表中 x 、 y ,均为加工点坐标值的绝对值。

    bbf172b531a247b0357a1f4c40c3817a.png

    展开全文
  • 这次主要实现在窗口上绘制、线以及修改其属性,另外还会分析画直线的原理和相关算法。1、在窗口指定位置画 glBegin(GL_POINTS); glEnd(); 使用glBegin()和glEnd()方法向窗口中添加图形。要添加时,...
  • 目录 0 原理 1 OpenCV中的霍夫变换 0 原理 霍夫变换在检测各种形状的的技术中非常流行,如果...首先将一条直线用一个表示,这样用一个表示直线上所有的,一开始人们使用斜截式y=kx+q中的(k,q)来表示一条...
  • RANSAC估计——以直线拟合为例

    千次阅读 2017-10-01 12:03:41
    RANSAC估计——以直线拟合为例RANSAC(RANdom SAmple Consensus),即随机采样一致性。该方法最早是由Fischler和Bolles提出的一种鲁棒估计方法,最早用于...下面就以直线估计的例子来说明RANSAC的基本思想。直线拟合RANS
  • 霍夫变换检测直线原理及实例

    千次阅读 2018-12-17 09:43:12
    直线可以由直角坐标或极坐标表示,直线可以由直角坐标或极坐标表示,直角坐标表示直线时,垂直于x轴的直线斜率不能表示,所以选择极坐标 对于霍夫变换, 我们将采用第二种方式极坐标系来表示直线. 因此, 直线的...
  • 机器人理论(6)直线轨迹规划:直曲线结合

    万次阅读 多人点赞 2018-10-14 10:32:18
    然而如果单纯地使用直线轨迹,线段间的转折会让速度不连续,如何又能使用直线轨迹又能满足速度连续呢?在这里引出一次多项式(直线)与二次多项式的结合使用。 目录 直线轨迹规划 多段直线轨迹规划 符号的设定...
  • 给定一张图像中的n个点,假设我们希望找到这些点中一个位于直线上的点集,一种可行的解决方法是,先找到所有由每对点确定直线,然后寻找靠近特定直线的点的所有子集。这种方法涉及寻找n(n-1)/2~n^2 条直线,然后对...
  • #[$index]劳尔:#[$index]拉啦啦:#[$index]劳尔:#[$index]拉啦啦:#[$index]劳尔:有一组实验数据,分布近似为一条直线,但不平滑...如果我仅取这组数据开头和末尾的做的直线斜率...曲线拟合还是曲线是啥意思?你...
  • FWIW,以下功能(在C中)都检测线交叉并确定交点。它基于Andre LeMothe的“Windows游戏编程大师的诀窍”中的算法。它与其他答案中的某些算法(例如Gareth's)没有什么不同。LeMothe然后使用Cramer的规则(不要问我)自己...
  • 霍夫变换(主要说明检测直线及圆的原理)

    万次阅读 多人点赞 2018-10-24 17:10:02
    霍夫变换是图像处理中从图像中识别几何形状的基本方法之一,...对于平面中的一条直线,在笛卡尔坐标系中,常见的有点斜式,两点式两种表示方法。然而在hough变换中,考虑的是另外一种表示方式:使用(r,theta)来表...
  • cad画规定长度直线的方法步骤图

    千次阅读 2020-12-21 04:12:30
    绘制直线直线一般由位置和长度个参数确定, 只要指定直线的起点和终点。那么大家知道cad怎么画规定长度的直线吗?下面是学习啦小编整理的绘制方法,希望能给大家解答。cad画规定长度的直线的方法1、打开AutoCAD2010...
  • OpenGL入门5——直线、多边形

    千次阅读 2014-12-21 18:34:13
    1、的细节  设置的大小: void glPointSize( GLfloat size );//设置被渲染的的宽度,以像素为单位。size必须大于0.0, 在默认情况下为1.0。  glGetFloatv( );  GL_ALLASED_POINT_PANGE 查询在未进行抗锯齿...
  • 我需要的是找到直线(由单位向量组成)碰到曲面的。我在建造那条线(我不确定是否有必要)和寻找到达交叉口的最快方法方面遇到了麻烦。谢谢你的帮助。在编辑这是我的坐标和建议我写的code的例子,为了得到我的曲面。在...
  • 直线扫描转换算法

    千次阅读 2017-09-23 14:02:28
    数学上,直线有无穷多个,但是在计算机光栅显示器屏幕上表示直线时需要做一些处理。 用有限的像素去逼近直线上无限的。 为了在光栅显示器上用有限的离散的像素去逼近这条直线,我们需要知道像素的x、y...
  • 基本概述1.1 一些基本问题1.2 以例子说明1.2.1 例子1:直线 y=kx+by = kx + by=kx+b​​​​​​​ 到参数空间的变换(k,b为定值,如k=2,b=4)1.2.2 例子2:极坐标下的直线到参数空间的变换1.2.3 例子3:圆到参数...
  • 我们这里主要用其来进行直线边缘检测。 正文 原理 Canny边缘检测算法主要分为以下五个步骤(参考自:Canny边缘检测算法) 使用高斯滤波器,以平滑图像,滤除噪声。 计算图像中每个像素的梯度强度和方向。 应用非极...
  • Hough变换检测直线、圆等图形的原理

    千次阅读 2014-11-22 11:50:02
    Hough变换的基本原理在于利用与线的对偶性,将原始图像空间的给定的曲线通过曲线表达形式变为参数空间的一个。这样就把原始图像中给定曲线的检测问题转化为寻找参数空间中的峰值问题。也即把检测整体特性转化为...
  • 【拟合专题】直线拟合

    千次阅读 2013-11-22 09:49:32
    直线拟合方法
  • 最小二乘法主要用于解决函数模型最优解问题,是测量工作及其他科学工程领域中,应用最早也是最广泛的算法。 在生产实践中,经常会遇到利用一组观测数据来估计某些未知参数的问题。...理想情况下,只需要在...
  • RANSAC算法(附RANSAC直线拟合C++与Python版本)

    千次阅读 多人点赞 2020-02-29 11:56:35
    RANSAC算法(附RANSAC直线拟合C++与Python版本) 微信公众号:幼儿园的学霸 个人的学习笔记,关于OpenCV,关于机器学习, …。问题或建议,请公众号留言; 之前在利用双目摄像头进行车道线检测时,利用RANSAC算法在三维...
  • 最小二乘法拟合三维直线

    千次阅读 2020-02-05 18:06:30
    在《高等数学》的书中给出了最小二乘法拟合直线的具体实例,但是那个例子是拟合二维直线的f(t)=at+b,那么三维直线怎么使用最小二乘法来拟合呢?我们先来看看《高等数学》书中的例子,由于任何实数的平方都是正数或...
  • 在CAD中,直线是最常用的命令/快捷键之一,那么如果画直线或者通过直线画角度呢?其实学习直线命令比较简单,也很快捷。...下面介绍绘制直线种常用方法。CAD画直线方法一点击直线命令后,在操作界...
  • 史上最详细的Hough直线检测

    万次阅读 多人点赞 2019-01-09 22:32:02
    最后可以检测出条车道线,但是,本课题的目的是通过提供一张图片,经过图像处理操作,经过算法模型得到违章的车辆情况,所以不能有人为的因素。 所以这里再次回顾一下检测直线的算法之——Hough变换。 Hough直线...
  • 直线检测-Radon变换、Hough变换

    千次阅读 2020-05-28 15:43:57
    那么这些像素坐标值(x, y)在霍夫空间对应的曲线一定相交于一个,所以我们只需要将图像中的所有像素(坐标值)变换成霍夫空间的曲线,并在霍夫空间检测曲线交点就可以确定直线了。 1、对边缘二值化图像进行霍夫...
  • Hough变换可以提取图像中的直线,但是提取...因为这种算法假设每个数据点中的x坐标是精确的,Y坐标是带有噪声的,可是在实际的图像中,我们所提取到的坐标的x、y坐标都是带有噪声的。因此,下面将介绍适用于图像中...
  • Hough变换直线检测

    千次阅读 2017-02-24 08:54:17
    作者:云外阳光 ... 来源:知乎 著作权归作者所有。商业转载请联系作者获得...y=k*x+b形式的直线方程没有办法表示x=c形式的直线(这时候,直线的斜率为无穷大)。所以实际应用中,利用极坐标的方式,将直线方程表示成:
  • 本篇博客围绕这篇文章进行一个具体问题的讲解,即使用这种方法的思想对一个平面直线回归问题进行实现、讲解。另外,本文还提供一种调用sklearn库进行求解的实现方法,以便于作对比分析。 文章中使用到的完整...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 27,941
精华内容 11,176
关键字:

两点确定直线的例子