算法 {掃描線}

掃描線

定義

#題目#: 二維空間上 給定若干個(凸多邊形), 求他們的並集的面積;
#思路#: 用若干個x=?(與Y軸平行的線) 將目標區域T劃分成若干個子區域Ai, 即S = A1 + A2 + ..., 然後單獨求每個Ai;

性質

與積分有點類似 都是求一個區域的面積; 他這裡是(凸多邊形)的並集, 如果是其他圖形 比如(圓) 就不適合掃描線了 需要使用(積分法: 參見辛普森積分);

算法

水平矩陣

定義

求若干個(邊長與X|Y軸平行的)矩陣的並集的面積;

代碼

{ // __ScanningLine
//< 時間為`O(N^2)`;
#define  LEF_( i)  @TODO   // 第i個矩陣的 左邊的`X`坐標;
#define  RIG_( i)  @TODO   // 第i個矩陣的 右邊的`X`坐標;
#define  LOW_( i)  @TODO   // 第i個矩陣的 下邊的`Y`坐標;
#define  HIG_( i)  @TODO   // 第i個矩陣的 上邊的`Y`坐標;
using __PosType = decltype( LEF_(0)); // 坐標的類型
    const int __N = @TODO; // 矩陣個數
    ASSERT_( __N > 0);

    vector< __PosType> Xpos( __N*2); // 所有的`LEF_(i)`從小到大排序;
    for( int i = 0; i < __N; ++i){ Xpos[ i*2] = LEF_(i), Xpos[ i*2+1] = RIG_(i);}
    sort( Xpos.begin(), Xpos.end());

    vector< int> Ind( __N); // 矩陣按照`LOW_()`從小到大排序;
    iota( Ind.begin(), Ind.end(), 0);
    sort( Ind.begin(), Ind.end(), [&]( int _a, int _b)->bool{ return LOW_(_a) < LOW_(_b);});

    Tools::Double ANS = 0;
    for( int i = 0; i+1 < __N*2; ++i){
        if( Xpos[i+1] == Xpos[i]){ continue;}
        auto l = Xpos[ i], r = Xpos[ i+1];

        __PosType preLow = 1, preMaxHig = 0; // 表示一個*非法區間*, 因為合法區間一定滿足`preLow <= preMaxHig`;
        for( int j = 0; j < __N; ++j){
            auto ind = Ind[j];
            if( LEF_(ind) <= l  &&  RIG_(ind) >= r){
                if( preLow > preMaxHig){ preLow = LOW_(ind), preMaxHig = HIG_(ind);}
                else{
                    if( LOW_(ind) <= preMaxHig){ preMaxHig = max(preMaxHig, HIG_(ind));}
                    else{
                        ANS += Tools::Double(r - l) * (preMaxHig - preLow);
                        preLow = LOW_(ind), preMaxHig = HIG_(ind);
                    }
                }
            }
        }
        if( preLow <= preMaxHig){
            ANS += Tools::Double(r - l) * (preMaxHig - preLow);
        }
    }

#undef  LEF_
#undef  RIG_
#undef  LOW_
#undef  HIG_
} // __ScanningLine

凸多邊形

定義

求若干個凸多邊形的交集, 此時 將所有{頂點 | 交點}處 都放置掃描線, 對於一個子區域l,r, (一個凸多邊形與x=l | r同時有交點)<->(該多邊形在該掃描線區域上有子區域Ai), 所有Ai的並集 就是當前要求的子區域的面積;
Ai是一個旋轉了90度的梯形(三角形/矩形 也屬於是梯形), 令其底邊(即下側的腰)的坐標為(l,lly) (r,rly) 上腰的坐標為(l,lhy) (r,rhy) 一定滿足lly <= lhy, rly <= rhy;
單調性: 你會得到若干個Ai, 且任意兩個 都滿足: [lly_i <= lly_j]->[rly_i <= rly_j] 且[lhy_i <= lhy_j]->[rhy_i <= rhy_j]; 也就是 對於兩個(上/下)腰(l,ly) (r,ry), ly與ry是保持單調性的, 如果ly_i <= ly_j 則也一定有ry_i <= ry_j, 否則他倆會存在交點 說明x=l | r之間 還存在一條掃描線x=m;
由於有一個單調性, 利用區間合併, 若干個有交集的梯形的並集 仍然會是梯形;

筆記

這個代碼 大概率會超時, 是因為 你獲得pot_l | pot_r所使用的Get_intersectionPoints_withLine這個函數 他的常數非常大; 如果有優化 則想辦法 在不使用該函數的前提下 獲得x=?與凸多邊形的交點;

代碼

{ // __ScanningLine
//< 時間是`O(N^3)`;
#define  CPG_( i)  A[i]  // 第i個凸多邊形`ConvexPolygon`;
    using __PosType = decltype( CPG_(0).Points[0].X);
    const int __N = N; // 凸多邊形個數
    ASSERT_( __N > 0);
    const int Eds = CPG_(0).Points.size(); // 多邊形的邊數

    vector< __PosType> Xpos; // {所有多邊形的頂點的X坐標 | 兩個多邊形的交點的X坐標} 從小到大排序;
    for( int i = 0; i < __N; ++i){
        for( int j = 0; j < Eds; ++j){
            Xpos.push_back( CPG_(i).Points[j].X);
        }
        for( int j = i + 1; j < __N; ++j){
            for( int e1 = 0; e1 < Eds; ++e1){
                for( int e2 = 0; e2 < Eds; ++e2){
                    auto ret = __Geometry2D::Segment( CPG_(i).Points[e1], CPG_(i).Points[ (e1+1)%Eds]).Get_intersectionPoint_withSegment( {CPG_(j).Points[e2], CPG_(j).Points[  (e2+1)%Eds]});
                    if( ret.first == 1){ Xpos.push_back( ret.second.X);}
                }
            }
        }
    }
    sort( Xpos.begin(), Xpos.end());

    Tools::Double ANS = 0;
    for( int i = 0; i+1 < (int)Xpos.size(); ++i){
        if( Xpos[i+1] == Xpos[i]){ continue;}
        auto LX = Xpos[ i], RX = Xpos[ i+1];

        using Interval_ = pair< pair<__PosType,__PosType>, pair<__PosType,__PosType> >;
        vector< Interval_> tpz; // `x=l|r`這兩個直線 會把一個多邊形切成一個*梯形*(與Y軸平行的梯形 他的兩個腰(不與Y軸平行)記作{下腰|上腰}) 用`{{ll,lr},{ul,ur}}`表示(下腰與`x=l|r`的交點的Y坐標為{ll|lr} 上腰與`x=l|r`的交點的Y坐標為{ul|ur}}; (`tpz: trapezoid`);
        for( int j = 0; j < __N; ++j){
            auto pot_l = CPG_( j).Get_intersectionPoints_withLine( {{LX,0}, {LX,1}});;
            auto pot_r = CPG_( j).Get_intersectionPoints_withLine( {{RX,0}, {RX,1}});
            if( pot_l.first == 0  ||  pot_r.first == 0){ continue;}
            if( pot_l.second.size() < 2){ pot_l.second.push_back( pot_l.second.back());}  sort( pot_l.second.begin(), pot_l.second.end());
            if( pot_r.second.size() < 2){ pot_r.second.push_back( pot_r.second.back());}  sort( pot_r.second.begin(), pot_r.second.end());
            tpz.push_back( { {pot_l.second[0].Y, pot_r.second[0].Y}, {pot_l.second[1].Y, pot_r.second[1].Y}});
        }
        { // 對`tpz`進行*區間合併*;
            #define  LOW_( i)  tpz[i].first
            #define  HIG_( i)  tpz[i].second
            const int __N = tpz.size();
            sort( tpz.begin(), tpz.end());
            for( int l=0, r=0; l < __N; ++r,l=r){
                auto maxHig = HIG_( l);
                while( r + 1 < __N  &&  LOW_( r+1) < maxHig){ ++r, maxHig=max( maxHig, HIG_(r));}
                ANS += ((maxHig.first - LOW_(l).first).ABS() + (maxHig.second - LOW_(l).second).ABS()) / 2 * (RX - LX);
            }
            #undef  LLOW_
            #undef  LHIG_
        }
    }

#undef  CPG_
} // __ScanningLine

例題

水平矩陣: @LINK: https://www.acwing.com/problem/content/3071/;

三角形: @LINK: https://www.acwing.com/problem/content/2803/;
目前會超時 問題完全出在求pot_l/pot_r, 即必須要避免使用Get_intersectionPoints_withLine這個函數, 需要進行優化: {將三角形的點 按照X坐標排序; @IF(X[0]<=l && X[2]>=r))[與當前掃描線有交點]-> {@IF(X[0]=X[1]=l)[說明他2個點在x=l上 另一個點在x=r上] @ELIF(X[1]=X[2]=r)[說明兩個點在x=r 另一個點在x=l] @ELSE[遍歷三條邊 他一定與x=l|r都有交點 即直接使用(直線與直線求交點) 不要使用(線段與直線求交點)] }

筆記

要求一個區域S(面積/周長), 我們將他分成若昂個獨立的部分S1,S2...(使得每個子區域裡 不包含頂點) 即S=S1+S2+..., 當然 前提是 Si比較好求 (比如他是若干個矩陣 不可以是不規則圖形 否則就太複雜了), 跟積分是一樣的 都是拆分;