有一个算法问题,求大神赐教

撸红薯 发布于 2013/09/22 19:31
阅读 1K+
收藏 2

【开源中国 APP 全新上线】“动弹” 回归、集成大模型对话、畅读技术报告”

最近在做一个项目。里面有很多控件,无窗口的那种。

下面用矩形表示这些控件。

问题抽象如下:

在一个二维平面上面,有很多矩形相互叠加在一起。每个矩形都自己的 z-index。这些矩形的数据存放在一个数组里面。现在给出一点,求这个点所在的矩形是那个一个,如果有多个,给出z-index 最高的一个矩形在数组的index。

暴力的时间复杂度应该是  O(N)的。但是不知道有没有更加好的算法和数据结构。




加载中
0
撸红薯
撸红薯
该评论暂时无法显示,详情咨询 QQ 群:点此入群
0
撸红薯
撸红薯
居然没有人气了! 算法大神都在哪?
0
中山野鬼
中山野鬼

哈,你倒问对人了。我最近在忙个逻辑处理分析问题,在平面的数据结构上和你的模型是一样的。

你定义三个轴。任意控件在每个轴上存在投影。轴的最大分辨率假设就是你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越大的放在最前面。这得看你的实际情况了。

明月惊鹊
明月惊鹊
该评论暂时无法显示,详情咨询 QQ 群:点此入群
0
撸红薯
撸红薯

@中山野鬼  实际上统计在某个投影点下 对应哪些控件的时间复杂度就不低了!

这个如何解决啊?

0
撸红薯
撸红薯

@中山野鬼  我倒是有一个简单的想法。只对一边做加速。比如x轴。根据x轴做下

线段树。然后查询速度就log时间复杂度了。然后从树顶外下遍历,判断y轴是不是也在这个矩阵中,如果在就返回

0
中山野鬼
中山野鬼

引用来自“breakerror”的答案

@中山野鬼  实际上统计在某个投影点下 对应哪些控件的时间复杂度就不低了!

这个如何解决啊?

这是预处理而已。不是具体计算。两个概念。
0
中山野鬼
中山野鬼

引用来自“breakerror”的答案

@中山野鬼  我倒是有一个简单的想法。只对一边做加速。比如x轴。根据x轴做下

线段树。然后查询速度就log时间复杂度了。然后从树顶外下遍历,判断y轴是不是也在这个矩阵中,如果在就返回

都一样。没什么问题。关键公式写清楚,不然数据结构的操作写完了。每个检测方法。哈。
0
泡不烂的凉粉
泡不烂的凉粉
该评论暂时无法显示,详情咨询 QQ 群:点此入群
0
撸红薯
撸红薯

引用来自“正想着改什么名好”的答案

发现仅仅有这些条件还不够. 

体现不出侧重点. 比如, 二维平面很大, 且矩形数据比较少 和 二维平面很小. 矩形数据量很大.  所采用的算法差异很大.

另外一个影响的因素是 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 的值判断是否需要更新缓冲区数据.

最后直接根据缓冲区返回结果.

这样缓存数据块太大!在数据量比较的时候 非常不划算
泡不烂的凉粉
泡不烂的凉粉
不明白所谓的太大是什么意思, 1024*768 分辨率的屏幕图像. 数据量最大范围为 65536 所占用缓冲空间大约为 6M-7M, 如果采用动态管理缓存数据. 根据抽屉原理. 只要系统设置有 z-index 最大范围, 那么取值范围不会超过 x*y*z bit .
0
优游幻世
优游幻世
增加个中间层,将平面分成一个个小矩形,建立一个hash表,如果控件的矩形窗口与某几个平面上的小矩形重叠,放入相应的hash桶,这样每次只需要比较几个矩形窗口就行,和 @正想着改什么名好 的思路差不多。
OSCHINA
登录后可查看更多优质内容
返回顶部
顶部