【开源中国 APP 全新上线】“动弹” 回归、集成大模型对话、畅读技术报告”
最近在做一个项目。里面有很多控件,无窗口的那种。
下面用矩形表示这些控件。
问题抽象如下:
在一个二维平面上面,有很多矩形相互叠加在一起。每个矩形都自己的 z-index。这些矩形的数据存放在一个数组里面。现在给出一点,求这个点所在的矩形是那个一个,如果有多个,给出z-index 最高的一个矩形在数组的index。
暴力的时间复杂度应该是 O(N)的。但是不知道有没有更加好的算法和数据结构。
【开源中国 APP 全新上线】“动弹” 回归、集成大模型对话、畅读技术报告”
最近在做一个项目。里面有很多控件,无窗口的那种。
下面用矩形表示这些控件。
问题抽象如下:
在一个二维平面上面,有很多矩形相互叠加在一起。每个矩形都自己的 z-index。这些矩形的数据存放在一个数组里面。现在给出一点,求这个点所在的矩形是那个一个,如果有多个,给出z-index 最高的一个矩形在数组的index。
暴力的时间复杂度应该是 O(N)的。但是不知道有没有更加好的算法和数据结构。
哈,你倒问对人了。我最近在忙个逻辑处理分析问题,在平面的数据结构上和你的模型是一样的。
你定义三个轴。任意控件在每个轴上存在投影。轴的最大分辨率假设就是你1个像素点,
不失一般性的我们假设对X轴进行处理。如果这个轴上对应像素点n,存在多个控件投影,则有
{x(n)}= {c0,c1...cm} 前面一个集合为坐标区间,后面一个投影集合。
以上就是初始状态。
对每个轴进行不定步长的收缩。
也即任意两个相邻的点的投影集合相同时,则进行合并,如果两个投影集合均为空,也即该像素点或坐标区间上不存在任何控件投影,则也进行合并。
每个轴合并后,存在一个有序坐标区间的集合。
你说的已知某点,实际是已知(x0,y0),求所有(x0,y0,z)中,z最大的控件。
那么等同于,存在一个x的坐标区间有 x0落入,其对应的控件集合,与y0落入的坐标区间对应的控件集合的交集中,寻找最大z。 既然区间集合是有序的,则可以进行一些快速搜索方法而不用遍历每个区间。
如果你的问题是仅针对(x,y)平面求最大z,则可以针对每个存在的坐标区间的交集,针对z进行直接排序,而不需要在计算中对z轴进行扫瞄。
简单说,如果你针对一个轴的匹配算法需要o(n)则整体需要 3 * o(n)。这个是逃不掉的。毕竟你轴与轴是正交无关的。
还有种思路是每个控件按照x,y,z进行排序。例如相同x,y的,z越大的放在最前面。这得看你的实际情况了。
@中山野鬼 实际上统计在某个投影点下 对应哪些控件的时间复杂度就不低了!
这个如何解决啊?
@中山野鬼 我倒是有一个简单的想法。只对一边做加速。比如x轴。根据x轴做下
线段树。然后查询速度就log时间复杂度了。然后从树顶外下遍历,判断y轴是不是也在这个矩阵中,如果在就返回
引用来自“breakerror”的答案
@中山野鬼 实际上统计在某个投影点下 对应哪些控件的时间复杂度就不低了!
这个如何解决啊?
引用来自“breakerror”的答案
@中山野鬼 我倒是有一个简单的想法。只对一边做加速。比如x轴。根据x轴做下
线段树。然后查询速度就log时间复杂度了。然后从树顶外下遍历,判断y轴是不是也在这个矩阵中,如果在就返回
引用来自“正想着改什么名好”的答案
发现仅仅有这些条件还不够.
体现不出侧重点. 比如, 二维平面很大, 且矩形数据比较少 和 二维平面很小. 矩形数据量很大. 所采用的算法差异很大.
另外一个影响的因素是 z-index 数据和矩形数据 index 的差异, 是否存在相同的 z-index 数据. 如果存在, 结果显示依据有如何.
最理想的算法 O(1). z-index 为z坐标. 平面数据坐标 为 x0,y0-x1,y1 z
设平面最大坐标为 x,y, 最大 z-index 为z. 开辟缓冲区. 大小为 x*y*常数.
常数不小于最大的数组 index. 也可以动态管理缓冲区大小.
遍历数组数据, 并根据数据中 z-index 的值判断是否需要更新缓冲区数据.
最后直接根据缓冲区返回结果.