作者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