Re: [程式] 圈地面積 最小面積取得相關 (方向判定)

[azureblaze (AzureBlaze)]

先說一下我對這個規則的理解：

把他當作拿美工刀在紙上割
如果某個區域被割下來的時候，把較小的那個區域丟掉


////////////////
資料結構：

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
→ zop:將圍過的邊都標注cut,還在畫的線標注run,行徑確定產生run之後,
→ zop:只要碰上cut,就等於包覆一個區域,同時作兩個區域的flood fill,
→ zop:比較之後標注小的區域為removed,然後removed內的cut全部清除,
→ zop:只留最外圍的cut,機體只能在cut上還有未removed的區域行走,另
→ zop:外,機體碰上run爆炸！(倒退也爆？XD)
→ azureblaze:確實檢查前面的邊就可以判斷新區域，免去flood fill
推 euph:感謝您的討論 我也想過類似的方法 不過在做FF的時候 要怎麼判

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)
推 euph:我也有想過你的想法 只是你丟進去的第一個FACE會被countinue
→ euph:因為那一個FACE的其中一邊就是CUT 然後就無法遞迴出去
→ azureblaze:只有那邊不做，其他三邊還是會處理啊?
推 euph:了解 我是以一整個FACE為單位 所以再切割成四個邊進去做檢查
→ euph:好 我試著寫看看 感謝 :D
推 euph:感謝 我把FACE分成四邊去做檢查再往外遞迴 就沒問題了!!
→ euph:大感謝!!! 只是效能有點恐怖就是了 XDDD
推 euph:後來我修改了一下 當如果檢查兩邊的時候其中一邊有碰到邊界
→ euph:就回傳false這樣可以加速很多不必要的檢查 邊界是只全體的邊
→ zop:可是如果是四邊都已經不是原先的邊,會不會判定失效？
→ zop:喔,看你敘述,應該是不會