作者azureblaze (AzureBlaze)
看板GameDesign
标题Re: [程式] 圈地面积 最小面积取得相关 (方向判定)
时间Wed Feb 27 12:12:29 2013
先说一下我对这个规则的理解：
把他当作拿美工刀在纸上割
如果某个区域被割下来的时候，把较小的那个区域丢掉
////////////////
资料结构：
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
1F：→ zop:将围过的边都标注cut,还在画的线标注run,行径确定产生run之後, 02/27 12:31
2F：→ zop:只要碰上cut,就等於包覆一个区域,同时作两个区域的flood fill, 02/27 12:32
3F：→ zop:比较之後标注小的区域为removed,然後removed内的cut全部清除, 02/27 12:33
4F：→ zop:只留最外围的cut,机体只能在cut上还有未removed的区域行走,另 02/27 12:34
5F：→ zop:外,机体碰上run爆炸！(倒退也爆？XD) 02/27 12:35
6F：→ azureblaze:确实检查前面的边就可以判断新区域，免去flood fill 02/27 13:03
7F：推 euph:感谢您的讨论 我也想过类似的方法 不过在做FF的时候 要怎麽判 02/27 13:09
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)
8F：推 euph:我也有想过你的想法 只是你丢进去的第一个FACE会被countinue 02/27 13:45
9F：→ euph:因为那一个FACE的其中一边就是CUT 然後就无法递回出去 02/27 13:47
10F：→ azureblaze:只有那边不做，其他三边还是会处理啊? 02/27 13:50
11F：推 euph:了解 我是以一整个FACE为单位 所以再切割成四个边进去做检查 02/27 13:55
12F：→ euph:好 我试着写看看 感谢 :D 02/27 13:55
13F：推 euph:感谢 我把FACE分成四边去做检查再往外递回 就没问题了!! 02/27 19:10
14F：→ euph:大感谢!!! 只是效能有点恐怖就是了 XDDD 02/27 19:10
15F：推 euph:後来我修改了一下 当如果检查两边的时候其中一边有碰到边界 02/28 15:48
16F：→ euph:就回传false这样可以加速很多不必要的检查 边界是只全体的边 02/28 15:49
17F：→ zop:可是如果是四边都已经不是原先的边,会不会判定失效？ 02/28 16:45
18F：→ zop:喔,看你叙述,应该是不会 02/28 16:45