计算几何 点到线段的距离 点在简单多边形内 点到凸多边形的距离

部分内容参考 http://blog.csdn.net/angelazy/article/details/38489293

1.点到线段的距离 

矢量算法

矢量算法过程清晰，如果具有一定的空间几何基础，则是解决此类问题时应优先考虑的方法。当需要计算的数据量很大时，这种方式优势明显。

由于矢量具有方向性，故一些方向的判断直接根据其正负号就可以得知，使得其中的一些问题得以很简单的解决。

用此方法考虑，我们只需要找到向量 在方向上的投影，具体如下：

             

上面的 是方向上的单位向量，其意义是给所求向量确定方向。是的两个向量的内积，且   ，其中θ为向量AP与AB之间的夹角。是向量长度。

 

那么即为上图中线段AC的长度值，不带有方向性。此数值与上述表征方向的 整体构成有大小、有方向的新向量，即为 在方向上的投影向量，C为投影点。

根据得到的，由向量的方向性可知：如果情况是上图（a）所示，那么0<r<1;如果是如图（b）所示的情况，那么r ≥1;如果是如图（c）所示的情况，那么得到r ≤0;

特殊情况如点在线段上、点在端点、点在线段延长线上等等的情况全部适用于此公式，只是作为特殊情况出现，无需另作讨论。这也是矢量算法思想的优势所在。

故根据r值的不同，最短距离

代码如下 ：

[cpp] view plain copy

print?

1. double PointTOline( point_t const&a,point_t const&b,point_t const&p){  
2.     double ap_ab = (b.x - a.x)*(p.x - a.x)+(b.y - a.y)*(p.y - a.y);//cross( a , p , b );  
3.     if ( ap_ab <= 0 )  
4.         return sqrt( (p.x-a.x)*(p.x-a.x) + (p.y-a.y)*(p.y-a.y) );  
5.   
6.     double d2 = ( b.x - a.x ) * ( b.x - a.x ) + ( b.y-a.y ) * ( b.y-a.y ) ;  
7.     if ( ap_ab >= d2 ) return sqrt( (p.x - b.x )*( p.x - b.x ) + ( p.y - b.y )*( p.y - b.y ) ) ;  
8.   
9.     double r = ap_ab / d2;  
10.     double px = a.x + ( b.x - a.x ) *r;  
11.     double py = a.y + ( b.y - a.y ) *r;  
12.     return sqrt( (p.x - px)*(p.x - px) + (p.y - py)*(p.y - py) );  
13. }  

2. 点在简单多边形内，

（1） 如果多边形是凸多边形，可用叉积法，先graham逆时针排序，然后旋转一周，判断方向是否一致

如图，点在凸包内，方向一定一致的。

（2）凹包要用射线法判断；

给定点A与简单多边形P[N]，判断A是否在P上

从A向右做射线，如果射线与P的边有奇数个交点，A在P上，否则A在P外

剔除几种特殊情况

·水平边不判断

·点在边上直接给结论

·点与边的交点恰好是端点，则只计数y值大的那个端点

代码如下

[cpp] view plain copy

print?

1. /* 
2.  *  点与简单多边形相交，使用射线法，剔除三种特殊情况后，判断交点的奇偶 
3.  *  从0开始标号 
4.  ×  注意n <= 2 的时候 
5.  */  
6. struct point_t{  
7.     int x,y;  
8. };  
9. bool isOnline( point_t const&a,point_t const&b, point_t const&po ){  
10.     return po.x >= min( a.x , b.x ) &&  
11.            po.x <= max( a.x , b.x ) &&  
12.            po.y >= min( a.y , b.y ) &&  
13.            po.y <= max( a.y , b.y ) &&  
14.            ( po.x - a.x ) * ( b.y - a.y ) == ( po.y - a.y ) * ( b.x - a.x );  
15. }  
16. bool isInSimple( point_t * p ,int n , point_t const&po ){  
17.   
18.     p[n] = p[0];  
19.     bool flag = 0;  
20.     int tmp;  
21.     for ( int i = 0; i < n;++i ){  
22.         if ( isOnline( p[i] , p[i+1] , po ) ) return true;  
23.         if ( p[i].y == p[i+1].y ) continue;  
24.         p[i].y < p[i+1].y ? tmp = i+1 : tmp = i ;  
25.         if ( po.y == p[tmp].y && po.x < p[tmp].x ) flag ^= 1;  
26.         p[i].y > p[i+1].y ? tmp = i+1 : tmp = i ;  
27.         if ( po.y == p[tmp].y && po.x < p[tmp].x ) continue ;  
28.   
29.         if ( po.x < max( p[i].x , p[i+1].x ) &&  
30.              po.y > min( p[i].y , p[i+1].y ) &&  
31.              po.y < max( p[i].y , p[i+1].y ) ) flag ^= 1;  
32.     }  
33.     return flag;  
34. }  

3.点与凸多边形的距离

先判断是否在多边形内，在求出到每条边的距离

代码如下

[cpp] view plain copy

print?

1. #include <bits/stdc++.h>  
2. using namespace std;  
3.   
4. struct point_t {  
5.     double x,y;  
6. };  
7. double cross(point_t const &O,point_t const &A,point_t const &B){  
8.     double xOA = A.x - O.x;  
9.     double yOA = A.y - O.y;  
10.     double xOB = B.x - O.x;  
11.     double yOB = B.y - O.y;  
12.     return xOA * yOB - xOB * yOA;  
13. }  
14. double PointTOline( point_t const&a,point_t const&b,point_t const&p){  
15.     double ap_ab = (b.x - a.x)*(p.x - a.x)+(b.y - a.y)*(p.y - a.y);//cross( a , p , b );  
16.     if ( ap_ab <= 0 )  
17.         return sqrt( (p.x-a.x)*(p.x-a.x) + (p.y-a.y)*(p.y-a.y) );  
18.   
19.     double d2 = ( b.x - a.x ) * ( b.x - a.x ) + ( b.y-a.y ) * ( b.y-a.y ) ;  
20.     if ( ap_ab >= d2 ) return sqrt( (p.x - b.x )*( p.x - b.x ) + ( p.y - b.y )*( p.y - b.y ) ) ;  
21.   
22.     double r = ap_ab / d2;  
23.     double px = a.x + ( b.x - a.x ) *r;  
24.     double py = a.y + ( b.y - a.y ) *r;  
25.     return sqrt( (p.x - px)*(p.x - px) + (p.y - py)*(p.y - py) );  
26. }  
27.   
28. bool isOnline( point_t const&a,point_t const&b, point_t const&po ){  
29.     return po.x >= min( a.x , b.x ) &&  
30.            po.x <= max( a.x , b.x ) &&  
31.            po.y >= min( a.y , b.y ) &&  
32.            po.y <= max( a.y , b.y ) &&  
33.            ( po.x - a.x ) * ( b.y - a.y ) == ( po.y - a.y ) * ( b.x - a.x );  
34. }  
35. bool isInSimple( point_t * p ,int n , point_t const&po ){  
36.     p[n] = p[0];  
37.     bool flag = 0;  
38.     int tmp;  
39.     for ( int i = 0; i < n;++i ){  
40.         if ( isOnline( p[i] , p[i+1] , po ) ) return true;  
41.         if ( p[i].y == p[i+1].y ) continue;  
42.         p[i].y < p[i+1].y ? tmp = i+1 : tmp = i ;  
43.         if ( po.y == p[tmp].y && po.x < p[tmp].x ) flag ^= 1;  
44.         p[i].y > p[i+1].y ? tmp = i+1 : tmp = i ;  
45.         if ( po.y == p[tmp].y && po.x < p[tmp].x ) continue ;  
46.   
47.         if ( po.x < max( p[i].x , p[i+1].x ) &&  
48.              po.y > min( p[i].y , p[i+1].y ) &&  
49.              po.y < max( p[i].y , p[i+1].y ) ) flag ^= 1;  
50.     }  
51.     return flag;  
52. }  
53.   
54. point_t p[120];  
55. int main(){  
56.     int n;  
57.     while(cin>>n && n){  
58.         point_t po;      
59.         cin>>po.x>>po.y;  
60.         for (int i = 0;i < n;++i)  
61.             cin>>p[i].x>>p[i].y;  
62.   
63.         if ( isInSimple( p , n , po ) ) {  
64.             cout <<"0.00"<<endl;  
65.             continue;  
66.         }  
67.         double ans = PointTOline( p[0],p[1],po );  
68.         p[n] = p[0];  
69.         for (int i = 1;i < n ;++i)  
70.             ans = min( ans, PointTOline(p[i] , p[i+1] , po) );  
71.         cout <<ans<<endl;  
72.     }  
73.     return 0;  
74. }