与this one相关的问题陈述位。
有一个给定2个点的矩形列表。
每个矩形由x0,y0,x1,y1
表示。
x0,y0
-表示左上角或起点x1,y1
-表示右下角或终点
注意:我们可以按任何格式对列表进行排序。假设(可以更改)列表是基于起点排序的。
需要找到给定的最佳矩形点X,Y完全位于。
- 如果有多个矩形重叠,可以选择面积最小的矩形。*
这可以在以后改进为到任何矩形角的最短距离。
输入:
点:(X,Y)=(1450,380)
矩形列表:
[
{
"x0": 1797,
"x1": 1854,
"y0": 333,
"y1": 434
},
{
"x0": 1671,
"x1": 1688,
"y0": 423,
"y1": 434
},
{
"x0": 1565,
"x1": 1594,
"y0": 366,
"y1": 378
},
{
"x0": 1547,
"x1": 1552,
"y0": 112,
"y1": 146
},
{
"x0": 1439,
"x1": 1457,
"y0": 373,
"y1": 396
}
]
输出:
{
"x0": 1439,
"x1": 1457,
"y0": 373,
"y1": 396
}
一个简单的方法是遍历所有的矩形,找到点所在的最小矩形,这可能是O(n)的复杂度。
- 是否有更好的解决方案,以更低的复杂度获得解决重叠场景的最佳矩形?*
1条答案
按热度按时间ffx8fchx1#
二进制搜索是行不通的,因为你只能在一个轴上进行分区,但是空间分区算法应该可以工作,例如,a quadtree数据结构可以很容易地将搜索的复杂度降低到
O(logn)
,在非退化成功的情况下。你可以很容易地建立一个退化的情况,需要线性扫描,但是,你有你的数组的所有元素作为同一个矩形,这真的取决于你的数据是如何进入和如何学究气你想与标签。