PCDVD數位科技討論區
PCDVD數位科技討論區   註冊 常見問題 標記討論區為已讀

回到   PCDVD數位科技討論區 > 其他群組 > 七嘴八舌異言堂
帳戶
密碼
 

  回應
 
主題工具
老柏(第四)
Senior Member
 
老柏(第四)的大頭照
 

加入日期: Mar 2012
您的住址: 地球
文章: 1,303
因為我是要找出"最少"的圈選框,所以我覺得很困難
(藍色是要被圈的,紅色是圈選框)


假設像這樣四處散倒好辦,反正每人一個圈選框



但假設像這樣一堆又一堆,雖然照上面的手法去做6個框可以淘汰掉右上角那個框變成5個框



但實際上最少的應該是像下面那個只有3個框,我想不出來要怎麼寫才能寫出來自己找到最佳的圈選方式
     
      
__________________
[/url]
老柏                 老柏(第二)

老柏(第三)              老柏(第四)
舊 2012-10-08, 11:07 PM #11
回應時引用此文章
老柏(第四)離線中  
奶油銓
Basic Member
 

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

我的想法如下:

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

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

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

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

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

我自己原來是用 (3)-(i), 一開始想說從質心附近開始找,但遇到資料極端分散的情形,就失敗。後來有一陣子我想說只計算每個長方形方格的幾何中心間的距離,每次都從距離平方和最小數值的那個位置附近來找。 後來我趁空閒時也寫了一個用 (3)-(ii)的方式,(Scan格點的時候不用太密集),但是找到大約位置後要記得也再附近找一下。

整個概念就是把圖形用"0或1的點"來表示,放上去的130x130的正方形能包住的點越多,就越優先把他放上去,並把那些點都擦掉,然後再重複找。

你參考參考吧
 
舊 2012-10-09, 12:00 AM #12
回應時引用此文章
奶油銓離線中  
sandstorm
*停權中*
 

加入日期: Mar 2010
文章: 541
我最喜歡暴力法了!

500*500的2D空間,用130*130的框框,如果是整數座標,那就會有(500-130+1)*(500-130+1)=137641個框框(w0, w1,..., w137640)。

然後每個框框都檢查會框住哪幾些個矩形(r0, r1,...rN),記錄起來。

那我們就有了類似下面的資料:
w0(r1, r4, r15,...)
w1(r0, r3, r4,...)
...
...
w137640(r13, r19,...)

我們希望用最少的框框就包到所有的矩形,
所以我們先只取一個框框,這樣有137641種狀況,檢查哪個滿足(r0, r1,...rN)都有包到。
若取一個找不到,就取二個框框,這樣有C(137641, 2)種狀況,檢查哪個組合滿足(r0, r1,...rN)都有包到。
若取二個找不到,就取三個框框,這樣有C(137641, 3)種狀況,檢查哪個組合滿足(r0, r1,...rN)都有包到。
...
...

我保證這個演算法一定找得到最佳解,但要花多久時間就...
舊 2012-10-09, 08:26 PM #13
回應時引用此文章
sandstorm離線中  
老柏(第四)
Senior Member
 
老柏(第四)的大頭照
 

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

我的想法如下:

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

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

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

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

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

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

比較沒有具體的搜尋方法....
因為這樣靠電腦分析怎麼圈比較多好像沒辦法

引用:
作者sandstorm
500*500的2D空間,用130*130的框框,如果是整數座標,那就會有(500-130+1)*(500-130+1)=137641個框框(w0, w1,..., w137640)。

然後每個框框都檢查會框住哪幾些個矩形(r0, r1,...rN),記錄起來。

那我們就有了類似下面的資料:
w0(r1, r4, r15,...)
w1(r0, r3, r4,...)
...
...
w137640(r13, r19,...)

我們希望用最少的框框就包到所有的矩形,
所以我們先只取一個框框,這樣有137641種狀況,檢查哪個滿足(r0, r1,...rN)都有包到。
若取一個找不到,就取二個框框,這樣有C(137641, 2)種狀況,檢查哪個組合滿足(r0, r1,...rN)都有包到。
若取二個找不到,就取三個框框,這樣有C(137641, 3)種狀況,檢查哪個組合滿足(r0, r1,...rN)都有包到。
...
...

我保證這個演算法一定找得到最佳解,但要花多久時間就...

這樣寫再強的電腦都會掛掉吧
__________________
[/url]
老柏                 老柏(第二)

老柏(第三)              老柏(第四)
舊 2012-10-10, 01:31 PM #14
回應時引用此文章
老柏(第四)離線中  
foxtm
Power Member
 
foxtm的大頭照
 

加入日期: Jan 2002
您的住址: 台北苦命IT工人
文章: 586
Smile

參考方法

先由
50個矩形中任取50個看可不可以用一個正方形包住。
50個矩形中任取49個看可不可以用一個正方形包住。
50個矩形中任取48個看可不可以用一個正方形包住。
50個矩形中任取47個看可不可以用一個正方形包住。
....照這樣一直下去,直到找該正方形。

接下來把剛剛有包住的矩形標記刪除,還沒標記的繼續照這個流程下去跑。
但這只是可以找到一組解而已,是不是最低解需要數學來證明。
舊 2012-10-10, 03:04 PM #15
回應時引用此文章
foxtm離線中  
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離線中  
shou1312
New Member
 

加入日期: Nov 2008
文章: 2
實際想想不是最佳解~錯了

最少要幾個的最佳解我想可以這樣算
以2D系統的Y座標來看
將所有的小方塊的長(Y1, Y2)看可以用多少130來涵蓋
這個用總長/130來算即可,有小數就進位
X座標也相同處理寬的部分

兩個的計算值相乘應該是最小解
實際要算出框起來的位置,就基植於上面的結果來處理應該就可以算出來

我很初步的在腦袋裡運算過感覺應該是這樣吧

此文章於 2012-10-10 03:49 PM 被 shou1312 編輯.
舊 2012-10-10, 03:46 PM #17
回應時引用此文章
shou1312離線中  


    回應


POPIN
主題工具

發表文章規則
不可以發起新主題
不可以回應主題
不可以上傳附加檔案
不可以編輯您的文章

vB 代碼打開
[IMG]代碼打開
HTML代碼關閉



所有的時間均為GMT +8。 現在的時間是09:09 PM.


vBulletin Version 3.0.1
powered_by_vbulletin 2025。