==> PAUL.bbs@bbs.cs.nthu.edu.tw (不事修飾) 在 programming 版提到:
: ※ 引述《Pro-V.bbs@bbs.ntu.edu.tw (與Subject GRE搏鬥)》之銘言：
: > 在特定範圍內Ex 800 X600有一堆小方框(x,y,w,h)，
: > 方框有可能重疊，但絕對有不同處(四參數必定有一個不同)
: > 給一個點，求出包含這個點的方框
: > 我現在的想法是
: > 先按x,y,w,h的大小sort 方框矩陣
: > search時再按x,y,w,h的方式找...
: > 這樣應該是O(n)吧....
: > 有沒有人有其他建議勒?!
: 你的 n 是什麼東西ㄚ?
: sort是 O(nlog n)吧?! or 你的框框都是 integer
: 那還得 depend on 你的 range吧!!
: 你的問題定義的不夠清楚, 想 follow, 可是看得不太懂你的提目
排序就差不多等於搜尋了...
if (x1,y1)-(x2,y2) ... and P(x,y)
if x>=x1 xor x>=x2 and y>=y1 and y>=y2 then
inside
end if
若在矩形內, 可用 XOR, 必然且惟一...
--
______________________________________________________本版因有你們而壯大
T.L. Cheng 子璉
_______________________________________________________________________.
請各位來成大資研BBS BASIC 版坐坐, 也歡迎你討論 WinHelp
請支援成立 BASIC討論版及 News Group, 讓 BASIC有個家!
2-D 徐昇網分析 (含交集分析) http://feitsui.hyd.ncku.edu.tw/TLCheng/Thiessen/
--
Origin: 成大資工BBS站 (vlsi1.csie.ncku.edu.tw) From: 140.116.77.68
> -------------------------------------------------------------------------- <
發信人: "青衫" <cin@jstek.com.tw>, 看板: Programming
標 題: Re: 有誰能想出較快速的演算法???
發信站: SEEDNet News Service (Tue Dec 15 19:20:00 1998)
轉信站: Ptt!news.ntu!spring!feeder.seed.net.tw!news.seed.net.tw!not-for-mail
> : > 在特定範圍內Ex 800 X600有一堆小方框(x,y,w,h)，
> : > 方框有可能重疊，但絕對有不同處(四參數必定有一個不同)
> : > 給一個點，求出包含這個點的方框
> : > 我現在的想法是
> : > 先按x,y,w,h的大小sort 方框矩陣
> : > search時再按x,y,w,h的方式找...
> : > 這樣應該是O(n)吧....
> : > 有沒有人有其他建議勒?!
> : 你的 n 是什麼東西ㄚ?
> : sort是 O(nlog n)吧?! or 你的框框都是 integer
> : 那還得 depend on 你的 range吧!!
> : 你的問題定義的不夠清楚, 想 follow, 可是看得不太懂你的提目
>
> 排序就差不多等於搜尋了...
> if (x1,y1)-(x2,y2) ... and P(x,y)
>
> if x>=x1 xor x>=x2 and y>=y1 and y>=y2 then
> inside
> end if
>
> 若在矩形內, 可用 XOR, 必然且惟一...
Sequential Search最差的情況本來就是O(n), 也不用排序了,
除非排序能加快search, 才有那個必要.
但我看不出能加快多少.
加快的方法應該也是有, 例如可先對x進行矩形排序,
在搜尋時, 對x作二分搜尋法或狠一點用索引法, 直接去除
一部份不必比較的矩形, 但最差的情形也是O(n).
若要再快, 則可以對4邊做4個排序, 用索引法分別比較
4次, 取剩餘區間最小的做Sequential Search,
不過這些Overhead可能便抵消所能加速的部份了...
--
青衫詩客 - 小邱.