Cocos2dx CrazyTetris 雙線偽裁剪算面積 對于判斷消除的思考（二）
來源：程序員人生 發布時間：2015-01-05 08:19:23 閱讀次數：2529次
上1篇主要講了我對裁剪消除算法的思考，這1篇的主題是計算單行覆蓋面積，以此來肯定是不是到達了裁剪條件。
就像之前所說的，在該游戲中，基本方塊都由4個小方塊構成，4個小方塊的尺寸均是25*25。因此游戲區域是寬可容納10個方塊，高可容納20個方塊。即250*500。每行的間距均是25。
因此，現在的問題就是，如何判定在這個寬250，高25的區域內，方塊所占的面積。如果能夠計算出其面積，而這個區域的總面積為250 * 25 = 6250，那末就能夠據此來判斷是不是滿足消除條件。例如：面積 > 6000。
因此這里主要是討論該套面積應當如何計算。
直接接上1篇。上1篇利用裁剪線將圖形集合上下切割，而這里明顯是要使用兩條線，將圖形進行上、中、下3片切割，然后根據切割結果計算中部的面積。如圖：
其中紅色區域就是要計算的面積。
這時候，算法思想和單線裁剪還是很類似的。這里由于分了3層，因此3層編碼需要兩位：上層（01）、中層（00）、下層（10）。
然后根據該編碼進行裁剪，只保存中部裁剪結果，然后利用裁剪結果（點集）創建PhysicsShapePolygon對象，并用其getArea()方法獲得面積便可。
這其中，雖然進行了裁剪算法，但是并沒有真正實行裁剪，因此叫做偽裁剪算法。
實現代碼以下：
//計算面積算法
float BaseBlock::calculaArea(float y1, float y2)
{
//定義上下多邊形集
float area = 0;
//
for(int i=0; i<shapeAmount; i++)
{
//
std::vector<Vec2> * middleShape;
middleShape = new std::vector<Vec2>();
//逐邊裁剪
for(int j=0; j<shapeVecAmount->at(i); j++)
{
Vec2 startPoint = this->coordinateSpin(shapeVecs->at(i)[j]);
Vec2 endPoint = this->coordinateSpin(shapeVecs->at(i)[(j+1)%shapeVecAmount->at(i)]);
int cStart = 0;
int cEnd = 0;
//
if((fabs(startPoint.y - y1) < 1e⑹) && (fabs(endPoint.y - y1) < 1e⑹))
{
cStart = cEnd = 0;
}
else if(fabs(startPoint.y - y1) < 1e⑹)
{
if(endPoint.y - y1 < 1e⑹)
{
cStart |= 2;
cEnd |= 2;
}
}
else if(fabs(endPoint.y - y1) < 1e⑹)
{
if(startPoint.y - y1 < 1e⑹)
{
cStart |= 2;
cEnd |= 2;
}
}
else
{
if(startPoint.y - y1 < 1e⑹) cStart |= 2;
if(endPoint.y - y1 < 1e⑹) cEnd |= 2;
}
//
if((fabs(startPoint.y - y2) < 1e⑹) && (fabs(endPoint.y - y2) < 1e⑹))
{
cStart = cEnd = 0;
}
else if(fabs(startPoint.y - y2) < 1e⑹)
{
if(endPoint.y - y2 > 1e⑹)
{
cStart |= 1;
cEnd |= 1;
}
}
else if(fabs(endPoint.y - y2) < 1e⑹)
{
if(startPoint.y - y2 > 1e⑹)
{
cStart |= 1;
cEnd |= 1;
}
}
else
{
if(startPoint.y - y2 > 1e⑹) cStart |= 1;
if(endPoint.y - y2 > 1e⑹) cEnd |= 1;
}
if(cStart == cEnd)
{
//兩頂點在同1邊，無需裁剪
if(cStart == 0)
{
//頂點在上邊，記錄到上邊頂點集
middleShape->push_back(coordinateGoBack(startPoint));
}
}
else
{
//兩頂點在不同邊，需要進行裁剪
if(cStart == 0)
{
float cutting_x;
float cutting_y;
if(cEnd == 1)
{
cutting_x = startPoint.x + (endPoint.x - startPoint.x) * (y2 - startPoint.y) / (endPoint.y - startPoint.y);
cutting_y = y2;
}
else
{
cutting_x = startPoint.x + (endPoint.x - startPoint.x) * (y1 - startPoint.y) / (endPoint.y - startPoint.y);
cutting_y = y1;
}
middleShape->push_back(coordinateGoBack(startPoint));
middleShape->push_back(coordinateGoBack(Vec2(cutting_x, cutting_y)));
}
else
{
float cutting_x;
float cutting_y;
if(cStart == 1)
{
cutting_x = startPoint.x + (endPoint.x - startPoint.x) * (y2 - startPoint.y) / (endPoint.y - startPoint.y);
cutting_y = y2;
}
else
{
cutting_x = startPoint.x + (endPoint.x - startPoint.x) * (y1 - startPoint.y) / (endPoint.y - startPoint.y);
cutting_y = y1;
}
middleShape->push_back(coordinateGoBack(Vec2(cutting_x, cutting_y)));
}
}
}
Vec2 * middleTempShape = new Vec2[middleShape->size()];
for(int index = 0; index < middleShape->size(); index++)
{
middleTempShape[index] = middleShape->at(index);
}
area += PhysicsShapePolygon::create(middleTempShape, middleShape->size())->getArea();
}
return area;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
