Re: [程式] 圈地面積 最小面積取得相關 (方向判定)
先說一下我對這個規則的理解：
把他當作拿美工刀在紙上割
如果某個區域被割下來的時候，把較小的那個區域丟掉
////////////////
資料結構：
class Face{
Edge top,bottom,left,right;
bool removed;
};
class Edge{
Face first,second;
bool cut;
};
考慮到更複雜的網格時你可能要把Face改成接受不定多數的Edge，
然後再加個Vertex來紀錄Edge間連接的狀況這樣才可以行走。
不過現在要的好像沒這麼複雜，所以使用格子的xy座標和上左方向就好了
////////
演算法:
當我割了一條新的邊的時候，我需要知道:
有沒有形成新的區域?
檢查方法：
把這個Edge標記為cut
從兩個Face中隨便挑一個，就統一用first好了
開始對first做flood fill
如果fill到了second，代表這條邊沒有產生新的區域，所以可以照常繼續。
如果形成新的區域，接下來的問題就是哪塊比較大:
對first和second各作一次flood fill，
在fill的時候可以用一個counter，每多fill一塊就加1
(更一般的狀況就在Face中紀錄面積，一樣加上去)
最後就可以比較兩邊大小了
(計算大小其實可以在檢蹅新區域的時候就順便做)
最後看哪邊比較小，就再對first或second做一次flood fill，
把那邊所有的Face標為removed
(也可以在比大小時就紀錄該區域有哪些face，
不過flood fill其實也沒多慢)
希望對你有幫助
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 1.171.56.169
→
02/27 12:31, , 1F
02/27 12:31, 1F
→
02/27 12:32, , 2F
02/27 12:32, 2F
→
02/27 12:33, , 3F
02/27 12:33, 3F
→
02/27 12:34, , 4F
02/27 12:34, 4F
→
02/27 12:35, , 5F
02/27 12:35, 5F
→
02/27 13:03, , 6F
02/27 13:03, 6F
推
02/27 13:09, , 7F
02/27 13:09, 7F
void FloodFill( Face f,byRef int area){
f.flag();
area += 1;
foreach(Edge e in f.edges){
if(e.cut) continue; //邊被切過了不用處理
Face n = e.getNeighbor(f); //取得跟這個邊相接的另外一個面
if(n.removed) continue; //面被切掉了不用處理
if(n.flaged()) continue; //面被處理過了
FloodFill(n,area);
}
}
//while new region created if Edge e is added:
FloodFill(e.first,areaFirst);
ClearFaceFlags();
FloodFill(e.second,areaSecond);
ClearFaceFlags();
if(areaFirst > areaSecond){
FloodFillRemove(e.first);
}else{
...
}
※ 編輯: azureblaze 來自: 1.171.56.169 (02/27 13:35)
推
02/27 13:45, , 8F
02/27 13:45, 8F
→
02/27 13:47, , 9F
02/27 13:47, 9F
→
02/27 13:50, , 10F
02/27 13:50, 10F
推
02/27 13:55, , 11F
02/27 13:55, 11F
→
02/27 13:55, , 12F
02/27 13:55, 12F
推
02/27 19:10, , 13F
02/27 19:10, 13F
→
02/27 19:10, , 14F
02/27 19:10, 14F
推
02/28 15:48, , 15F
02/28 15:48, 15F
→
02/28 15:49, , 16F
02/28 15:49, 16F
→
02/28 16:45, , 17F
02/28 16:45, 17F
→
02/28 16:45, , 18F
02/28 16:45, 18F
討論串 (同標題文章)
完整討論串 (本文為第 5 之 5 篇)：