[問題] 如何找出包含某點的所有矩形 ?
※ [本文轉錄自 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
推
04/06 23:24, , 1F
04/06 23:24, 1F
→
04/06 23:25, , 2F
04/06 23:25, 2F
→
04/06 23:25, , 3F
04/06 23:25, 3F
討論串 (同標題文章)
Programming 近期熱門文章
PTT數位生活區 即時熱門文章
