|
部分內容參考 http://blog.csdn.net/angelazy/article/details/38489293
1.點到線段的距離
矢量算法
矢量算法過程清晰，如果具有一定的空間幾何基礎，則是解決此類問題時應優先考慮的方法。當需要計算的數據量很大時，這種方式優勢明顯。
由于矢量具有方向性，故一些方向的判斷直接根據其正負號就可以得知，使得其中的一些問題得以很簡單的解決。
用此方法考慮，我們只需要找到向量  在 方向上的投影，具體如下：
上面的  是方向上的單位向量，其意義是給所求向量確定方向。 是的兩個向量的內積，且  ，其中θ為向量AP與AB之間的夾角。是向量長度。
那么 即為上圖中線段AC的長度值，不帶有方向性。此數值與上述表征方向的 整體構成有大小、有方向的新向量 ，即為 在方向上的投影向量，C為投影點。
根據得到的，由向量的方向性可知：如果情況是上圖（a）所示，那么0<r<1;如果是如圖（b）所示的情況，那么r ≥1;如果是如圖（c）所示的情況，那么得到r ≤0;
特殊情況如點在線段上、點在端點、點在線段延長線上等等的情況全部適用于此公式，只是作為特殊情況出現，無需另作討論。這也是矢量算法思想的優勢所在。
故根據r值的不同，最短距離
代碼如下 ：
- double PointTOline( point_t const&a,point_t const&b,point_t const&p){
- double ap_ab = (b.x - a.x)*(p.x - a.x)+(b.y - a.y)*(p.y - a.y);//cross( a , p , b );
- if ( ap_ab <= 0 )
- return sqrt( (p.x-a.x)*(p.x-a.x) + (p.y-a.y)*(p.y-a.y) );
-
- double d2 = ( b.x - a.x ) * ( b.x - a.x ) + ( b.y-a.y ) * ( b.y-a.y ) ;
- if ( ap_ab >= d2 ) return sqrt( (p.x - b.x )*( p.x - b.x ) + ( p.y - b.y )*( p.y - b.y ) ) ;
-
- double r = ap_ab / d2;
- double px = a.x + ( b.x - a.x ) *r;
- double py = a.y + ( b.y - a.y ) *r;
- return sqrt( (p.x - px)*(p.x - px) + (p.y - py)*(p.y - py) );
- }
2. 點在簡單多邊形內，
（1） 如果多邊形是凸多邊形，可用叉積法，先graham逆時針排序，然后旋轉一周，判斷方向是否一致
如圖，點在凸包內，方向一定一致的。
（2）凹包要用射線法判斷；
給定點A與簡單多邊形P[N]，判斷A是否在P上
從A向右做射線，如果射線與P的邊有奇數個交點，A在P上，否則A在P外
剔除幾種特殊情況
·水平邊不判斷
·點在邊上直接給結論
·點與邊的交點恰好是端點，則只計數y值大的那個端點
代碼如下
- /*
- * 點與簡單多邊形相交，使用射線法，剔除三種特殊情況后，判斷交點的奇偶
- * 從0開始標號
- × 注意n <= 2 的時候
- */
- struct point_t{
- int x,y;
- };
- bool isOnline( point_t const&a,point_t const&b, point_t const&po ){
- return po.x >= min( a.x , b.x ) &&
- po.x <= max( a.x , b.x ) &&
- po.y >= min( a.y , b.y ) &&
- po.y <= max( a.y , b.y ) &&
- ( po.x - a.x ) * ( b.y - a.y ) == ( po.y - a.y ) * ( b.x - a.x );
- }
- bool isInSimple( point_t * p ,int n , point_t const&po ){
-
- p[n] = p[0];
- bool flag = 0;
- int tmp;
- for ( int i = 0; i < n;++i ){
- if ( isOnline( p[i] , p[i+1] , po ) ) return true;
- if ( p[i].y == p[i+1].y ) continue;
- p[i].y < p[i+1].y ? tmp = i+1 : tmp = i ;
- if ( po.y == p[tmp].y && po.x < p[tmp].x ) flag ^= 1;
- p[i].y > p[i+1].y ? tmp = i+1 : tmp = i ;
- if ( po.y == p[tmp].y && po.x < p[tmp].x ) continue ;
-
- if ( po.x < max( p[i].x , p[i+1].x ) &&
- po.y > min( p[i].y , p[i+1].y ) &&
- po.y < max( p[i].y , p[i+1].y ) ) flag ^= 1;
- }
- return flag;
- }
3.點與凸多邊形的距離 先判斷是否在多邊形內，在求出到每條邊的距離
代碼如下
- #include <bits/stdc++.h>
- using namespace std;
-
- struct point_t {
- double x,y;
- };
- double cross(point_t const &O,point_t const &A,point_t const &B){
- double xOA = A.x - O.x;
- double yOA = A.y - O.y;
- double xOB = B.x - O.x;
- double yOB = B.y - O.y;
- return xOA * yOB - xOB * yOA;
- }
- double PointTOline( point_t const&a,point_t const&b,point_t const&p){
- double ap_ab = (b.x - a.x)*(p.x - a.x)+(b.y - a.y)*(p.y - a.y);//cross( a , p , b );
- if ( ap_ab <= 0 )
- return sqrt( (p.x-a.x)*(p.x-a.x) + (p.y-a.y)*(p.y-a.y) );
-
- double d2 = ( b.x - a.x ) * ( b.x - a.x ) + ( b.y-a.y ) * ( b.y-a.y ) ;
- if ( ap_ab >= d2 ) return sqrt( (p.x - b.x )*( p.x - b.x ) + ( p.y - b.y )*( p.y - b.y ) ) ;
-
- double r = ap_ab / d2;
- double px = a.x + ( b.x - a.x ) *r;
- double py = a.y + ( b.y - a.y ) *r;
- return sqrt( (p.x - px)*(p.x - px) + (p.y - py)*(p.y - py) );
- }
-
- bool isOnline( point_t const&a,point_t const&b, point_t const&po ){
- return po.x >= min( a.x , b.x ) &&
- po.x <= max( a.x , b.x ) &&
- po.y >= min( a.y , b.y ) &&
- po.y <= max( a.y , b.y ) &&
- ( po.x - a.x ) * ( b.y - a.y ) == ( po.y - a.y ) * ( b.x - a.x );
- }
- bool isInSimple( point_t * p ,int n , point_t const&po ){
- p[n] = p[0];
- bool flag = 0;
- int tmp;
- for ( int i = 0; i < n;++i ){
- if ( isOnline( p[i] , p[i+1] , po ) ) return true;
- if ( p[i].y == p[i+1].y ) continue;
- p[i].y < p[i+1].y ? tmp = i+1 : tmp = i ;
- if ( po.y == p[tmp].y && po.x < p[tmp].x ) flag ^= 1;
- p[i].y > p[i+1].y ? tmp = i+1 : tmp = i ;
- if ( po.y == p[tmp].y && po.x < p[tmp].x ) continue ;
-
- if ( po.x < max( p[i].x , p[i+1].x ) &&
- po.y > min( p[i].y , p[i+1].y ) &&
- po.y < max( p[i].y , p[i+1].y ) ) flag ^= 1;
- }
- return flag;
- }
-
- point_t p[120];
- int main(){
- int n;
- while(cin>>n && n){
- point_t po;
- cin>>po.x>>po.y;
- for (int i = 0;i < n;++i)
- cin>>p[i].x>>p[i].y;
-
- if ( isInSimple( p , n , po ) ) {
- cout <<"0.00"<<endl;
- continue;
- }
- double ans = PointTOline( p[0],p[1],po );
- p[n] = p[0];
- for (int i = 1;i < n ;++i)
- ans = min( ans, PointTOline(p[i] , p[i+1] , po) );
- cout <<ans<<endl;
- }
- return 0;
- }
|
