浏览量:80

5.2. 点与矩形

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

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

5.2. 点与矩形

5.2.1. 点到矩形的矩离

问题描述:在二维空间上,计算点P到矩形对象\(R:X({{t}_{0}},{{t}_{1}})=C+{{t}_{0}}\cdot {{\vec{e}}_{0}}+{{t}_{1}}\cdot {{\vec{e}}_{1}},-{{u}_{0}}\le {{t}_{0}}\le {{u}_{0}},-{{u}_{1}}\le {{t}_{1}}\le {{u}_{1}}\)的距离。

2015-3-23 13-23-29

图5.2 矩形把平面划分的9个区域

\(\Delta =P-C\),有\({{s}_{0}}=\Delta \cdot {{\vec{e}}_{0}}\)\({{s}_{1}}=\Delta \cdot {{\vec{e}}_{1}}\),矩形上与P最接近的点取决于参数平面\( ({{t}_{0}},{{t}_{1}})\)上9个区域中的哪一个包含\(({{s}_{0}},{{s}_{1}})\),平面上9个区域的划分如图5.2所示。若\(({{s}_{0}},{{s}_{1}})\)落在区域0中,说明点P在矩形内部,它到矩形的距离是0;若\(({{s}_{0}},{{s}_{1}})\)落在区域1、3、5、7上,则\(({{s}_{0}},{{s}_{1}})\)到矩形对应的顶点上的距离最近;若\(({{s}_{0}},{{s}_{1}})\)落在区域2、6上,则最近距离是点P到边\({{\vec{e}}_{1}}\)的投影;若\(({{s}_{0}},{{s}_{1}})\)落在区域4、8上,则最近距离是点P到边\({{\vec{e}}_{0}}\)的投影。

在算法的具体实现中,不需要将参数平面划分成9个区域,然后分成不同的区域来处理,采用每次处理一维,点与矩形距离的伪码如下所示:

求点P到矩形对象\(R:X({{t}_{0}},{{t}_{1}})=C+{{t}_{0}}\cdot {{\vec{e}}_{0}}+{{t}_{1}}\cdot {{\vec{e}}_{1}}\)的距离的平方
1.    计算\(\Delta =P-C\);
2.    计算\({{s}_{0}}=\Delta \cdot {{\vec{e}}_{0}}\)\({{s}_{1}}=\Delta \cdot {{\vec{e}}_{1}}\);
3.    distSquare = 0;
4.    offset = s0 + u0/2;
5.    if offset < 0, then
6.           distSquare += offset*offset;
7.    else
8.           offset = s0 - u0/2;
9.           if offset > 0, then
10.                 distSquare += offset*offset;
11.          end if;
12.   end if;
13.   offset = s1 + u1/2;
14.   if offset < 0, then
15.          distSquare += offset*offset;
16.   else
17.          offset = s1 - u1/2;
18.          if offset > 0, then
19.                 distSquare += offset * offset;
20.          end if;
21.   end if;
22.   return distSquare;

5.2.2. 点与矩形的关系

问题描述:判定点P与矩形对象\(R:X({{t}_{0}},{{t}_{1}})=C+{{t}_{0}}\cdot {{\vec{e}}_{0}}+{{t}_{1}}\cdot {{\vec{e}}_{1}},-{{u}_{0}}\le {{t}_{0}}\le {{u}_{0}},-{{u}_{1}}\le {{t}_{1}}\le {{u}_{1}}\)的关系。

2015-3-23 13-23-39

图5.3 点P与矩形关系的判定

如图5.3所示,设矩形的四个顶点分别是,只需要判断点P是否同时夹在平行对边\({{V}_{0}}{{V}_{1}}\)\({{V}_{2}}{{V}_{3}}\)之间,与\({{V}_{0}}{{V}_{2}}\)\({{V}_{1}}{{V}_{3}}\)之间。如果点P不夹在任意一组平行对边之间,说明点P不在矩形内部;否则,点P位于矩形内部或者边上。

2015-3-23 13-23-49

图5.4 点\({P_0},{P_1}\)在直线的两侧

 

如图5.4所示,点\({{P}_{0}}\)在直线\({{V}_{0}}{{V}_{1}}\)的逆时针方向上,有\(({{V}_{1}}-{{V}_{0}})\times ({{P}_{0}}-{{V}_{0}})\succ 0\);点\({{P}_{1}}\)在直线\({{V}_{0}}{{V}_{1}}\)的顺时针方向上,有\(({{V}_{1}}-{{V}_{0}})\times ({{P}_{0}}-{{V}_{0}})\prec 0\)。因此判定点是否在矩形的平行对边之间,可以采用等式(5.2),若\({{\Delta }_{1}}\prec 0\),则点在平行对边\({{V}_{0}}{{V}_{1}}\)\({{V}_{2}}{{V}_{3}}\)之间;否则,不在。同理,\({{\Delta }_{2}}\)用于判定另一组平行对边与点的关系。

\[\left\{ \begin{array}{l}{\Delta _1} = \left[ {(P - {V_0}) \times ({V_1} - {V_0})} \right] \cdot \left[ {(P - {V_2}) \times ({V_3} - {V_2})} \right]\\{\Delta _2} = \left[ {(P - {V_0}) \times ({V_2} - {V_0})} \right] \cdot \left[ {(P - {V_1}) \times ({V_3} - {V_1})} \right]\end{array} \right. \tag{5.2}\]

算法的伪码如下所示:

求点P与矩形对象\(R:X({{t}_{0}},{{t}_{1}})=C+{{t}_{0}}\cdot {{\vec{e}}_{0}}+{{t}_{1}}\cdot {{\vec{e}}_{1}}\)的关系。
1.    \({{V}_{0}}=C-{{u}_{0}}\cdot {{\vec{e}}_{0}}-{{u}_{1}}\cdot {{\vec{e}}_{1}}\);
2.    \({{V}_{1}}=C+{{u}_{0}}\cdot {{\vec{e}}_{0}}-{{u}_{1}}\cdot {{\vec{e}}_{1}}\);
3.    \({{V}_{2}}=C-{{u}_{0}}\cdot {{\vec{e}}_{0}}+{{u}_{1}}\cdot {{\vec{e}}_{1}}\);
4.    \({{V}_{3}}=C+{{u}_{0}}\cdot {{\vec{e}}_{0}}+{{u}_{1}}\cdot {{\vec{e}}_{1}}\);
5.    \({{\Delta }_{1}}=\left[ (P-{{V}_{0}})\times ({{V}_{1}}-{{V}_{0}}) \right]\cdot \left[ (P-{{V}_{2}})\times ({{V}_{3}}-{{V}_{2}}) \right]\);
6.    if \({{\Delta }_{1}}\succ 0\), then
7.           点P在矩形外;
8.    end if;
9.    \({{\Delta }_{2}}=\left[ (P-{{V}_{0}})\times ({{V}_{2}}-{{V}_{0}}) \right]\cdot \left[ (P-{{V}_{1}})\times ({{V}_{3}}-{{V}_{1}}) \right]\);
10.   if \({{\Delta }_{2}}\succ 0\), then
11.          点P在矩形外;
12.   end if;
13.   if \({{\Delta }_{1}}==0\) || \({{\Delta }_{2}}==0\), then
14.          点P在矩形的边上;
15.   end if;
16.   点P在矩形内;

spacer

Leave a reply