javascript 如何找到点在给定的矩形列表中的位置?(复杂度小于O(n))

2exbekwf  于 2023-02-18  发布在  Java
关注(0)|答案(1)|浏览(98)

this one相关的问题陈述位。
有一个给定2个点的矩形列表。
每个矩形由x0,y0,x1,y1表示。

  1. x0,y0-表示左上角或起点
  2. 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)的复杂度。

  • 是否有更好的解决方案,以更低的复杂度获得解决重叠场景的最佳矩形?*
ffx8fchx

ffx8fchx1#

二进制搜索是行不通的,因为你只能在一个轴上进行分区,但是空间分区算法应该可以工作,例如,a quadtree数据结构可以很容易地将搜索的复杂度降低到O(logn),在非退化成功的情况下。
你可以很容易地建立一个退化的情况,需要线性扫描,但是,你有你的数组的所有元素作为同一个矩形,这真的取决于你的数据是如何进入和如何学究气你想与标签。

相关问题