浏览量:491

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

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。

PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry

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

问题描述:判定二维空间上的点\(Y\)与线性对象\(P + t\vec d\)的关系。

点与直线的关系就两种情况:在直线上和不在直线上。可以用式子(3.11)来判定,若\({\Delta _1} = 0\),则点\(Y\)在直线上;否则,点\(Y\)不在直线上。

\[{\Delta _1} = (P – Y) \times \vec d \tag{3.11}\]

\[{\Delta _2} = (P – Y) \cdot \vec d \tag{3.12}\]

2015-3-22 15-27-45

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

点与射线的关系判定与此相似,不同的是,如果点\(Y\)在射线所在的直线上,但它还有可能不在射线上,如图3.2(a)所示,因此需要增加一步判定。如果\({\Delta _1} = 0 \wedge {\Delta _2} \le 0\),则点\(Y\)在射线上;否则,点\(Y\)不在射线上。

对于点与线段的关系判定,也需要注意点在线段所在的直线上的情况判定,如图3.2(b)所示,点\({Y_0}\)、\({Y_1}\)、\({Y_2}\)在线段\(\overline {{P_0}{P_1}} \)所在的直线上,但\({Y_0}\)在线段左侧,\({Y_1}\)在线段右侧,\({Y_2}\)在线段上,有两种方法可以处理在同一条直线上的点与线段的关系判定的问题。

方法一 点积排除法

如等式(3.11)、(3.13)所示,如果\({\Delta _1} \ne 0 \vee {d_0} \cdot {d_1} \succ 0\),则点在线段外;否则,点在线段上。

\[\begin{array}{l}{d_0} = (Y – {P_0}) \cdot ({P_1} – {P_0})\\{d_1} = (Y – {P_1}) \cdot ({P_1} – {P_0})\end{array} \tag{3.13}\]

方法二 坐标对比法

采用对比\(x\)和\(y\)坐标的方法,若点\(Y\)满足(3.14)所示的条件,则点在线段上;否则,点在线段外。

\[\begin{array}{l}\left( {{\Delta _1} = 0} \right) \wedge \left( {\min \{ {P_{0,x}},{P_{1,x}}\} \le {Y_x} \le \max \{ {P_{0,x}},{P_{1,x}}\} } \right) \wedge \\\left( {\min \{ {P_{0,y}},{P_{1,y}}\} \le {Y_y} \le \max \{ {P_{0,y}},{P_{1,y}}\} } \right)\end{array} \tag{3.14}\]

总结下点与线性对象的关系判定,主要分为两个步骤:

  1. 判定点是否在线性对象所在的直线上,若不在,分离关系,若在,进入第ii步判定。
  2. 若在,再判定点是否在线性对象上。
spacer

Leave a reply