我需要模拟Fluxbox窗口管理器的窗口放置策略.
作为一个粗略的指南,可视化随机大小的窗口一次一个地填满屏幕,其中每个窗口的粗略大小导致屏幕上平均80个窗口,而没有任何窗口与另一个窗口重叠.
如果您的系统上安装了Fluxbox和Xterm,您可以尝试使用xwinmidiarptoy BASH脚本来查看我想要发生的事情的粗略原型.请参阅我写过的xwinmidiarptoy.txt说明,解释它的作用以及如何使用它.
重要的是要注意窗口将关闭,并且关闭先前占用的窗口的空间再次可用于放置新窗口.
该算法需要是一个在线算法处理数据"以串行方式逐个处理,即按照输入被提供给算法的顺序,而不需要从一开始就提供整个输入."
Fluxbox窗口放置策略有三个我想模拟的二元选项:
Windows构建水平行或垂直列(可能)
Windows从左到右或从右到左放置
Windows从上到下或从下到上放置
目标算法与窗口放置算法之间的差异
坐标单位不是像素.将放置块的网格将是128 x 128个单位.此外,放置区域可以通过放置在网格内的边界区域进一步收缩.
为什么算法有问题？
它需要在音频应用程序中运行到实时线程的最后期限.
此刻我只关心获得快速算法,不关心实时线程的含义以及编程带来的所有障碍.
虽然算法永远不会放置一个与另一个重叠的窗口,但是用户将能够放置和移动某些类型的块,将存在重叠的窗口.用于存储窗口和/或空闲空间的数据结构需要能够处理这种重叠.
到目前为止,我有两个选择,我已经建立了松散的原型:
1)Fluxbox放置算法的一个端口到我的代码中.
问题是,当我尝试使用该算法放置256块的最坏情况时,客户端(我的程序)被踢出音频服务器(JACK).该算法在放置第256个窗口时对已经放置的块列表执行超过14000次完整(线性)扫描.
为了演示这一点,我创建了一个名为text_boxer-0.0.2.tar.bz2的程序,该程序将文本文件作为输入并将其排列在ASCII框中.问题make来构建它.有点不友好,使用--help(或任何其他无效选项)的命令行选项列表.您必须使用该选项指定文本文件.
2)我的替代方法.
仅部分实现,该方法对矩形空闲未使用空间的每个区域使用数据结构(窗口列表可以完全分离,并且不需要用于测试该算法).数据结构充当双向链表中的节点(具有排序插入),并且包含左上角的坐标以及宽度和高度.
此外,每个块数据结构还包含四个链接,这四个链接连接到四个边中的每一个上的每个紧邻(触摸)块.
重要规则:每个块每侧只能触摸一个块.这是一种特定于算法存储空闲未使用空间的方法的规则,并且不会影响实际窗口可能相互接触的数量.
这种方法的问题是,它非常复杂.我已经实现了直接的情况,其中1)从块的一个角去除空间,2)分割相邻的块以便遵守重要的规则.
不太直接的情况,其中要移除的空间只能在一列或一排框中找到,只是部分实现 - 如果要移除的一个块完全适合宽度(即列)或高度(即然后出现问题.甚至没有提到这个事实,它只检查一个框宽的列,并排一个框高.
我已经用C语言实现了这个算法 - 我正在使用这个项目的语言(我几年没有使用过C++,在把注意力都集中在C开发之后使用它很不舒服,这是一个爱好).实现是700多行代码(包括大量空行,支撑线,注释等).该实现仅适用于水平行+左右+上下放置策略.
所以我要么添加一些方法来使这些+700行代码适用于其他7个放置策略选项,或者我将不得不为其他7个选项复制那些+700行代码.这些都不具吸引力,第一,因为现有代码足够复杂,第二,因为膨胀.
由于缺少功能,该算法甚至不能在实时最坏情况下使用它,因此我仍然不知道它实际上是否比第一种方法更好或更差.
该算法的C实现的当前状态是freespace.c.我用它gcc -O0 -ggdb freespace.c来构建,并以xterm大小运行它至少至少124 x 60个字符.
那里还有什么？
我撇去并打折:
Bin Packing算法:它们对最佳拟合的强调与该算法的要求不匹配.
递归二分位置算法:听起来很有希望,但这些都是用于电路设计的.他们的重点是最佳的电线长度.
在算法开始之前,所有这些元素,特别是后者,所有要放置的元素/包都是已知的.
你对此有何看法？你会怎么做？我应该看看还有哪些其他算法？或者甚至我应该研究哪些概念,因为我没有学过计算机科学/软件工程？
如果需要进一步的信息,请在评论中提问.
自提出这个问题后开发的其他想法
我的"替代算法"与空间散列图的某种组合,用于识别要放置的大窗口是否会覆盖几个可用空间块.
Victor Liu.. 5
我会考虑某种空间哈希结构.想象一下,你的整个自由空间被粗略地网格化,称之为块.当窗户来来往往时,它们占据了一些连续的矩形块.对于每个块,跟踪每个角落中最大的未使用矩形,因此您需要为每个块存储2*4个实数.对于空块,每个角上的矩形的大小等于块.因此,块只能在其角落"用完",因此最多4个窗口可以位于任何块中.
现在,每次添加窗口时,都必须搜索窗口适合的矩形块集,并在此时更新自由边角大小.您应该调整块的大小,以便少量(~4x4)它们适合典型的窗口.对于每个窗口,跟踪它接触的块(您只需要跟踪范围),以及哪个窗口触摸给定块(在此算法中最多4个).块的粒度与每个窗口插入/移除的工作量之间存在明显的权衡.
移除窗口时,在其触摸的所有块上循环,对于每个块,重新计算自由角大小(您知道哪些窗口会触摸它).这很快,因为内环最多长度为4.
我想像一个数据结构
struct block{
int free_x[4]; // 0 = top left, 1 = top right,
int free_y[4]; // 2 = bottom left, 3 = bottom right
int n_windows; // number of windows that occupy this block
int window_id[4]; // IDs of windows that occupy this block
};
block blocks[NX][NY];
struct window{
int id;
int used_block_x[2]; // 0 = first index of used block,
int used_block_y[2]; // 1 = last index of used block
};
编辑
这是一张图片:
它显示了两个示例块.有色点表示块的角,从它们发出的箭头表示该角的最大自由矩形的范围.
你在编辑中提到你的窗口所在的网格已经非常粗糙(127x127),因此块大小可能就像一侧有4个网格单元,这可能不会给你带来太大的好处.如果你的窗口角坐标可以采用很多值(我认为它们是像素),这种方法是合适的,但在你的情况下并不是那么多.你仍然可以尝试,因为它很简单.你可能还想保留一个完全空块的列表,这样如果一个窗口进入大于2个块宽度的窗口,那么你先查看该列表中的第一个,然后在块网格中寻找一些合适的空闲空间.
我会考虑某种空间哈希结构.想象一下,你的整个自由空间被粗略地网格化,称之为块.当窗户来来往往时,它们占据了一些连续的矩形块.对于每个块,跟踪每个角落中最大的未使用矩形,因此您需要为每个块存储2*4个实数.对于空块,每个角上的矩形的大小等于块.因此,块只能在其角落"用完",因此最多4个窗口可以位于任何块中.
现在,每次添加窗口时,都必须搜索窗口适合的矩形块集,并在此时更新自由边角大小.您应该调整块的大小,以便少量(~4x4)它们适合典型的窗口.对于每个窗口,跟踪它接触的块(您只需要跟踪范围),以及哪个窗口触摸给定块(在此算法中最多4个).块的粒度与每个窗口插入/移除的工作量之间存在明显的权衡.
移除窗口时,在其触摸的所有块上循环,对于每个块,重新计算自由角大小(您知道哪些窗口会触摸它).这很快,因为内环最多长度为4.
我想像一个数据结构
struct block{
int free_x[4]; // 0 = top left, 1 = top right,
int free_y[4]; // 2 = bottom left, 3 = bottom right
int n_windows; // number of windows that occupy this block
int window_id[4]; // IDs of windows that occupy this block
};
block blocks[NX][NY];
struct window{
int id;
int used_block_x[2]; // 0 = first index of used block,
int used_block_y[2]; // 1 = last index of used block
};
编辑
这是一张图片:
它显示了两个示例块.有色点表示块的角,从它们发出的箭头表示该角的最大自由矩形的范围.
你在编辑中提到你的窗口所在的网格已经非常粗糙(127x127),因此块大小可能就像一侧有4个网格单元,这可能不会给你带来太大的好处.如果你的窗口角坐标可以采用很多值(我认为它们是像素),这种方法是合适的,但在你的情况下并不是那么多.你仍然可以尝试,因为它很简单.你可能还想保留一个完全空块的列表,这样如果一个窗口进入大于2个块宽度的窗口,那么你先查看该列表中的第一个,然后在块网格中寻找一些合适的空闲空间.
京公网安备 11010802040832号 | 京ICP备19059560号-6 