auto_fill_jewel/auto_fill_jewel_v3/RandomGridFiller.cpp

//
//  RandomGridFiller.cpp
//  Test
//
//  Created by 高慕白 on 2024/12/3.
//

#include "RandomGridFiller.hpp"
#include "BoostGeometryTools.hpp"
#include <iostream>
#include <algorithm>
using std::cout;
using std::endl;

void RandomGridFiller::fill( vector<JewelBox>& jewelsArray ,    //需要填充的宝石
          float bottomLeftX,float bottomLeftY,//盘子有效区域
          float topRightX,float topRightY,    //盘子有效区域
          vector<FillResult>& results         //填充结果
          )
{
    srand(_seed) ;
    results.clear() ;
    
    if( jewelsArray.size()==0 ) return ;
    float width = topRightX - bottomLeftX + 1;
    float height = topRightY - bottomLeftY+ 1;
    
    float minJewWid = jewelsArray[0]._width ;
    float minJewHei = jewelsArray[0]._height;
    for(auto it = jewelsArray.begin()+1;it!=jewelsArray.end();++it ) {
        minJewWid = fmin( minJewWid, it->_width ) ;
        minJewHei = fmin( minJewHei, it->_height) ;
    }
    float gridWid = width/20;
    float gridHei = height/20;
    
    int nrows = width / gridWid ;
    int ncols = height/ gridHei ;

    vector<ContourData::Point> potPositions ;
    for(int irow = 0 ; irow < nrows; ++ irow )
    {
        for(int icol=0;icol<ncols;++icol)
        {
            ContourData::Point cp ;
            cp.x = (icol+0.5) * gridWid ;
            cp.y = (irow+0.5) * gridHei ;
            potPositions.push_back(cp) ;
        }
    }
    
    const int TRY_CNT=5 ;
    bool chosen = false ;
    int chosenTotCoverage = 9999999 ;
    float chosenTotDist = 999999 ;
    for(int itry = 0 ;itry < TRY_CNT; ++ itry ) {
        vector<FillResult> fillResults ;
        float jewDistSum=0;
        int cov = 0 ;
        int badcnt = randomFillOneRound(jewelsArray, bottomLeftX, bottomLeftY, topRightX, topRightY, potPositions, fillResults, jewDistSum,gridWid,gridHei,cov);
        cout<<"itry-"<<itry<<" badcnt "<<badcnt<<" jewDistSum "<<jewDistSum<<" cov "<<cov <<endl;
        if( chosen==false ) {
            chosen = true ;
            chosenTotCoverage = cov ;
            chosenTotDist = jewDistSum ;
            results = fillResults ;
        }else{
            if( cov < chosenTotCoverage ) {
                chosenTotCoverage = cov ;
                chosenTotDist = jewDistSum ;
                results = fillResults ;
            }else if( cov == chosenTotCoverage ) {
                if( chosenTotDist < jewDistSum ) {
                    chosenTotCoverage = cov ;
                    chosenTotDist = jewDistSum ;
                    results = fillResults ;
                }
            }
        }
    }
}

int RandomGridFiller::randomFillOneRound( vector<JewelBox>& jewelsArray,
                        float bottomLeftX,float bottomLeftY,//盘子有效区域
                        float topRightX,float topRightY,    //盘子有效区域
                        vector<ContourData::Point> potPositions, //潜在的点位
                        vector<FillResult>& results,
                        float& jewDistanceSum
                        ,const float gridWid
                        ,const float gridHei
                        ,int& resultTotCov
                        )
{
    results.clear() ;
    vector<int> jewIndices ;
    for(int ij=0;ij<jewelsArray.size();++ij ) {
        for(int ic=0 ; ic < jewelsArray[ij]._cnt ; ++ ic ) {
            jewIndices.push_back(ij) ;
        }
    }
    //需要填充的数量
    int num2fill = jewIndices.size() ;
    
    //盘子的有效区域矩形边界
    BoostGeometryTools::BoostPolygon plateBox = BoostGeometryTools::makeRotatedBox(bottomLeftX, bottomLeftY, (topRightX-bottomLeftX+1), (topRightY-bottomLeftY), 0);
    
    //点位从外到内
    vector<DistancePosition> distPositions ;
    generateDistanceRandomSlotPositions((topRightX-bottomLeftX)/2, (topRightY-bottomLeftY)/2, potPositions, distPositions) ;
    
    //使用网格描述盘子点位占用情况
    const int GRID_X_NUM = (topRightX - bottomLeftX+1)/gridWid ;
    const int GRID_Y_NUM = (topRightY - bottomLeftY+1)/gridHei ;
    
    //每个宝石分配一个占用格点数据，用于标记该宝石在盘子中的痕迹
    vector< GridData > jewelGridDataArray(jewIndices.size()) ;
    for(int ij=0;ij<jewIndices.size();++ij ) {
        jewelGridDataArray[ij].reset(bottomLeftX+gridWid/2, bottomLeftY+gridHei/2, gridWid, gridHei, GRID_X_NUM, GRID_Y_NUM) ;
    }
    
    //随机打散宝石顺序
    vector<int> resultsJewIndices ;
    vector<int> randIndicesOfJewIndices = randIndices(jewIndices.size()) ;
    for(int ij = 0 ; ij < randIndicesOfJewIndices.size() ; ++ij ) {
        int randJewIndex = randIndicesOfJewIndices[ij] ;
        int jewTypeIndex = jewIndices[randIndicesOfJewIndices[ij]] ;
        JewelBox& jewBox = jewelsArray[jewTypeIndex] ;
        int rotdeg = rand()%360 ;
        BoostGeometryTools::BoostPolygon jewPoly = BoostGeometryTools::makeRotatedBox(
                                                                                      -jewBox._width/2,
                                                                                      -jewBox._height/2,
                                                                                      jewBox._width,
                                                                                      jewBox._height ,
                                                                                      rotdeg) ;
        vector<FillResult> tempFillResults ;
        vector<int> sumOfTakenCountArray ;//保留占位数求和
        const int NUM_TRY = distPositions.size() ;//最大尝试数量
        int itry = 0 ;//尝试数量
        //将潜在点位按照距离盘子中心的距离进行排序，宝石按照这个距离进行填入盘子
        vector<int> positionIndices ;
        //逐个尝试，尝试NUM_TRY，保留占位数求和最少的。
        for(int ip = 0 ; ip < distPositions.size();++ ip ) {
            if( distPositions[ip]._isTaken ) continue ;//位置占用跳过
            ContourData::Point posi = distPositions[ip]._point ;
            BoostGeometryTools::BoostPolygon jpoly2 = BoostGeometryTools::translatePolygon(jewPoly, posi.x, posi.y) ;
            //是否落在盘子内部
            bool isJewWithinPlate = BoostGeometryTools::isAWithinB(jpoly2, plateBox) ;
            if( isJewWithinPlate ) {
                itry ++ ;
                FillResult fr ;
                fr._jewelTypeId = jewBox._jewelTypeId ;
                fr._rotdeg = rotdeg ;
                fr._x = posi.x ;
                fr._y = posi.y ;
                fr._width = jewBox._width ;
                fr._height = jewBox._height ;
                tempFillResults.push_back(fr) ;
                int tsum = totalCoverageGridCount(jpoly2, jewelGridDataArray) ;
                //cout<<"ij-"<<ij<<" itry-"<<itry<<" tsum "<<tsum<<endl;
                sumOfTakenCountArray.push_back(tsum) ;
                positionIndices.push_back(ip); //positionIndices.push_back(ip) ;
                if( itry == NUM_TRY ) break ;
            }
        }
        
        //保留占位数最少的。
        if( tempFillResults.size()>0 ) {
            FillResult fr = tempFillResults[0] ;
            int tsum = sumOfTakenCountArray[0] ;
            int posiIndex =positionIndices[0] ;
            for(int itry = 1 ; itry < tempFillResults.size();++ itry ) {
                if( tsum > sumOfTakenCountArray[itry]) {
                    tsum = sumOfTakenCountArray[itry] ;
                    fr = tempFillResults[itry] ;
                    posiIndex =positionIndices[itry] ;
                }
            }
            distPositions[posiIndex]._isTaken = true ;//记录位置已经占用
            num2fill-- ;
            BoostGeometryTools::BoostPolygon jpoly2 = BoostGeometryTools::translatePolygon(jewPoly, fr._x, fr._y) ;
            setGridCoverageByBox(jpoly2, jewelGridDataArray[randJewIndex]);//写入子网格数据
            results.push_back(fr);//记录最优结果
            resultsJewIndices.push_back(randJewIndex) ;
            //debug
            //cout<<"ij-"<<ij<<" pos "<<fr._x<<","<<fr._y<< " cov " << tsum <<endl;
        }
    }
    
    //重新计算覆盖度（这个看上去好像解决不了什么问题）后面可以删掉这部分代码
    vector<int> coverageArray(results.size(),0 ) ;
    resultTotCov = 0;
    for(int ij = 0 ; ij < results.size();++ij ) {
        FillResult& fr = results[ij] ;
        int jewIndex = resultsJewIndices[ij] ;
        BoostGeometryTools::BoostPolygon jpoly = BoostGeometryTools::makeRotatedBox(-fr._width/2,-fr._height/2,
                                                                                    fr._width,fr._height ,
                                                                                    fr._rotdeg) ;
        BoostGeometryTools::BoostPolygon jpoly2 = BoostGeometryTools::translatePolygon(jpoly, fr._x, fr._y) ;
        coverageArray[jewIndex] = totalCoverageGridCount(jpoly2, jewelGridDataArray, jewIndex ) ;
        //cout<<"ji-"<<jewIndex<<" cov "<<coverageArray[jewIndex]<<" x,y "<< fr._x<<","<<fr._y <<endl;
        resultTotCov += coverageArray[jewIndex] ;
    }
    
    //计算宝石间距离求和
    jewDistanceSum = 0 ;
    for(int ifr = 0 ; ifr < results.size();++ ifr ) {
        for(int jfr = ifr+1; jfr < results.size();++jfr ) {
            float dx = results[ifr]._x - results[jfr]._x ;
            float dy = results[ifr]._y - results[jfr]._y ;
            jewDistanceSum += sqrtf( dx*dx+dy*dy ) ;
        }
    }
    
    return num2fill ;
}


//随机排序数组索引值
vector<int> RandomGridFiller::randIndices(const int count0 ) {
    int count = count0 ;
    vector<int> indices ;
    unordered_map<int, bool> dict ;
    while( count > 0 ) {
        int r = rand()%count0;
        if( dict.find(r) == dict.end() ) {
            dict[r] = true ;
            indices.push_back(r) ;
            count-- ;
        }
    }
    return indices;
}


int RandomGridFiller::sumOfSubGridTakenCounts(const int x,const int y,const int radius,
                                             const float gridwid,const float gridhei,const vector<vector<int>>& rowColSubGrid)
{
    int sum = 0 ;
    
    int gridXNum = rowColSubGrid[0].size() ;
    int gridYNum = rowColSubGrid.size() ;
    
    int centerGridX = x*1.0 / gridwid + 0.5 ;
    int centerGridY = y*1.0 / gridhei + 0.5 ;
    int gridRadiusX = radius/gridwid ;
    int gridRadiusY = radius/gridhei ;
    for( int igridy = -gridRadiusY; igridy <= gridRadiusY; ++ igridy ) {
        for(int igridx = -gridRadiusX; igridx <= gridRadiusX; ++ igridx ) {
            int gridx = centerGridX + igridx ;
            int gridy = centerGridY + igridy ;
            if( gridx>=0 && gridx < gridXNum && gridy>=0 && gridy < gridYNum ) {
                sum += rowColSubGrid[gridy][gridx] ;
            }
        }
    }
    return sum ;
}

void RandomGridFiller::subGridTakenCountsAddOne(const int x,const int y,const int radius,
                                               const float gridwid,const float gridhei,vector<vector<int>>& rowColSubGrid)
{
    int gridXNum = rowColSubGrid[0].size() ;
    int gridYNum = rowColSubGrid.size() ;
    
    int centerGridX = x*1.0 / gridwid + 0.5 ;
    int centerGridY = y*1.0 / gridhei + 0.5 ;
    int gridRadiusX = radius/gridwid ;
    int gridRadiusY = radius/gridhei ;
    for( int igridy = -gridRadiusY; igridy <= gridRadiusY; ++ igridy ) {
        for(int igridx = -gridRadiusX; igridx <= gridRadiusX; ++ igridx ) {
            int gridx = centerGridX + igridx ;
            int gridy = centerGridY + igridy ;
            if( gridx>=0 && gridx < gridXNum && gridy>=0 && gridy < gridYNum ) {
                rowColSubGrid[gridy][gridx]+=1 ;
            }
        }
    }
}


//多边形盖住的格点数量
int RandomGridFiller::coverageGridCount( BoostGeometryTools::BoostPolygon& box, const GridData& grid )
{
    int sum = 0 ;
    int nrows = grid._rows.size();
    int ncols = 0;
    if( nrows>0 ) ncols = grid._rows[0].size();
    for(int irow = 0 ; irow < grid._rows.size();++ irow ) {
        for(int icol=0;icol<ncols;++icol ) {
            
            bool taken = grid._rows[irow][icol] ;
            if( taken ) {
                BoostGeometryTools::BoostPoint bp ;
                float x = grid._bottomLeftX + icol * grid._stepX ;
                float y = grid._bottomLeftY + irow * grid._stepY ;
                bp.set<0>(x);
                bp.set<1>(y) ;
                sum += BoostGeometryTools::pointIntersetsBox(bp, box)?1:0 ;
            }
        }
    }
    return sum ;
}

int RandomGridFiller::totalCoverageGridCount(BoostGeometryTools::BoostPolygon& box, const vector<GridData>& grids ,int excludeIndex)
{
    int sum = 0 ;
    for(int ij=0;ij<grids.size();++ij ) {
        sum += (ij!=excludeIndex)?coverageGridCount(box, grids[ij]):0 ;
    }
    return sum ;
}


//将覆盖的格点数据赋值
void RandomGridFiller::setGridCoverageByBox( BoostGeometryTools::BoostPolygon& box, GridData& grid )
{
    int nrows = grid._rows.size();
    int ncols = 0;
    if( nrows>0 ) ncols = grid._rows[0].size();
    for(int irow = 0 ; irow < grid._rows.size();++ irow ) {
        for(int icol=0;icol<ncols;++icol ) {
            BoostGeometryTools::BoostPoint bp ;
            float x = grid._bottomLeftX + icol * grid._stepX ;
            float y = grid._bottomLeftY + irow * grid._stepY ;
            bp.set<0>(x);
            bp.set<1>(y) ;
            grid._rows[irow][icol] = BoostGeometryTools::pointIntersetsBox(bp, box) ;
        }
    }
}

void RandomGridFiller::generateDistanceRandomSlotPositions(const float centerx,const float centery,const vector<ContourData::Point>& points, vector<RandomGridFiller::DistancePosition>& results )
{
    results.clear() ;
    vector<int> randindices = randIndices( points.size() ) ;
    for(int ir = 0 ; ir <randindices.size();++ir ) {
        ContourData::Point pt = points[randindices[ir]] ;
        float dx = pt.x - centerx ;
        float dy = pt.y - centery ;
        float dist = sqrtf(dx*dx + dy*dy) ;
        DistancePosition dp ;
        dp._distance = dist ;
        dp._isTaken = false ;
        dp._point = pt ;
        results.push_back(dp) ;
    }
    //排序
    std::sort(results.begin(), results.end(), [](DistancePosition& p1,DistancePosition& p2)->bool{return p1._distance>p2._distance; } );
}