瀏覽單個文章
darkangel
Major Member
 
darkangel的大頭照
 

加入日期: Aug 2001
文章: 211
引用:
作者奶油銓
你這個問題,約10年前我有寫過一個程式處理這種問題,當時是用f77 寫的不過當時我是用圓去包,但你現在是正方形。分享一下我的想法 (我的作法不能保證一定是最少),但你上面的例子我一定是3個就框住了。

我的想法如下:

(1) 先把圖形切成非常細的小方格 (越細就會找的越準)

(2) 有被小長方形包住的地方就定為1,沒包到的就定為0

(3) 找尋合適的中心位置,把你要框的130x130正方形放上去,計算範圍內的1的數目,累加數字越大的那個位置就蓋上去。

這個合適的中心位置,可以
(i) 自己寫程式判斷,哪邊長方形比較密集,就從那邊開始放正方形
(ii) 無腦的就scan每個格點。(以這個例子來說最多僅需要scan 140625個位置)

(4) 蓋上去後把被蓋住的數值寫成0,然後重複(3) 直到全部都變成0。

我自己原來是用 (3)-(i), 一開始想說從質心附近開始找,但遇到資料極端分散的情形,就失敗。...


我覺得這方式是可行的。
如果是我來寫,我大概也會寫成這樣,先割成小方格,然後再找出所有的點。
重點是算出各群聚的中心點,這部份可以用到類似 neural network 其中的 SOM 演算法來找出群聚中心點。
__________________
滿招損 謙受益
舊 2012-10-10, 03:30 PM #16
回應時引用此文章
darkangel離線中