作者owokko (天天都是好心情)
看板Programming
標題[問題] 如何找出包含某點的所有矩形 ?
時間Fri Apr 6 19:59:56 2007
※ [本文轉錄自 Prob_Solve 看板]
作者: owokko (天天都是好心情) 看板: Prob_Solve
標題: [問題] 如何找出包含某點的所有矩形 ?
時間: Thu Apr 5 23:01:41 2007
問題:
在有限的範圍內(0,0)~(x,x) x為極大的數
(0,0) ┌───→ x
在這個範圍內有K的大小不一的矩形 及一個點 │
│
請找出包含該點的所有矩形 │
↓
y
我的想法:
一個矩形物件有4個值 分別為左上角X及Y作標 右下角X及Y座標
用暴力法比較 左上叫座標與 該點
if (左上角X及Y作標皆小於該點){
if (右下角X及Y座標 皆小於該點)
則點包含於該矩形
}
else { 點不包含於該矩形 }
雖然這是暴力法 不過時間複雜度只要 O(K)
但是似乎有方法可以更快 提示是 quadtree
(
http://en.wikipedia.org/wiki/Quadtree )
關鍵好像是資料結的應用
不過我怎麼想時間複雜度都不會低於O(K)
想請問各位的想法??
--
★boyo 好像一直有人以為瓦斯炸免錢的 沒這回事 現再叫一桶也要600
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.59.252.158
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.59.252.158
1F：推 ephesians:問題怎麼飛到這裏來了? 61.231.66.51 04/06 23:24
2F：→ ephesians:看到這問題我聯想到曾讀過的 R tree 61.231.66.51 04/06 23:25
3F：→ ephesians:為了快速尋找2D電路區塊而設計的索引 61.231.66.51 04/06 23:25