浏览量:286

6.7. 直线与凸多边形的距离

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

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

6.7. 直线与凸多边形的距离

问题描述:计算直线\(L(t) = Q + t \cdot \vec d\)与凸多边形\({\rm P} = \{ {V_0},{V_1}, \cdots ,{V_{n - 1}}\} \)的距离,设\({\rm P}\)是逆时针顺序且不存在连续的三个顶点共线的情况。

计算直线与多边形的距离,需要遍历多边形的每个顶点,时间复杂度是\(O(n)\),但对于凸多边形这种特殊情况,存在复杂度是\(O(\log n)\)的算法。

\(d(L,{{V}_{i}})\)表示凸多边形上点\({{V}_{i}}\)与直线\(L\)的距离,其中\(0\le i\le n-1\),那么\({\rm P}\)与直线\(L\)的距离就可以表示为\(d(L,P)=\underset{0\le i\le n-1}{\mathop{min}}\,\left\{ d(L,{{V}_{i}}) \right\}\),就是找到\({\rm P}\)上与直线\(L\)距离最近的顶点。设与直线\(L\)垂直的方向是\(\vec{n}\),确保\({\rm P}\)上至少有一个顶点不在直线\(L\)\(\vec{n}\)指向的一侧,那么与直线\(L\)最近的顶点,就是凸多边形\({\rm P}\)沿着方向\(\vec{n}\)的极点,如图6.41所示,\({{V}_{\max }}\)就是沿着方向\(\vec{n}\)的极点。将向量\(\vec{d}\)沿着逆时针方向旋转90,就得到与它垂直的向量\(\vec{n}=\left( -{{{\vec{d}}}_{y}},{{{\vec{d}}}_{x}} \right)\)。若\(\vec{n}\cdot \left( {{V}_{0}}-Q \right)\succ 0\),为了保证\({\rm P}\)上至少有一个顶点不在直线\(L\)\(\vec{n}\)指向的一侧,取\(\vec{n}=-\vec{n}\);否则,\(\vec{n}\)保持不变。接着计算凸多边形的极点,求出凸多边形\({\rm P}\)沿着\(\vec{n}\)方向的最大极点,设最大极点为\({{V}_{\max }}\)。若极点\({{V}_{\max }}\)在直线\(L\)\(\vec{n}\)指向的一侧,说明直线\(L\)与凸多边形\({\rm P}\)相交,距离为零;否则,计算点\({{V}_{\max }}\)与直线\(L\)的距离,算法结束。

2015-3-23 19-40-08

图6.41 直线与凸多边形的距离,(a)距离不为零(b)距离为零

算法伪码如下所示:

计算直线\(L(t)=Q+t\cdot \vec{d}\)与凸多边形\({\rm P} = \{ {V_0},{V_1}, \cdots ,{V_{n - 1}}\} \)的距离,设\({\rm P}\)是逆时针顺序且不存在连续的三个顶点共线的情况
1.    \(\vec{n}=\left( -{{{\vec{d}}}_{y}},{{{\vec{d}}}_{x}} \right)\);
2.    if \(\vec{n}\cdot \left( {{V}_{0}}-Q \right)\succ 0\), then
3.           \(\vec{n}=-\vec{n};\)
4.    end if;
5.    k = EXTREME_OF_CONVEX(\({\rm P}\),\(\vec{n}\));                  //获取多边形\({\rm P}\)上,方向是\(\vec{n}\)的最大极点
6.    if \(\vec{n}\cdot \left( {{V}_{k}}-Q \right)\ge 0\), then
7.           return 0;
8.    else
9.           return 点与直线\(L\)的距离;
10.   end if;

spacer

Leave a reply