我追求一种高效的2D映射算法,我尝试了许多实现,但似乎都缺乏。我希望stackoverflow世界能为我提供一些可以学习的现有、经过测试的算法。
我的目标是展示基于写作风格的文章;作为原型,我使用了哲学、编程、政治和诗歌,因为这是我仅有的四种写作风格。
每篇文章都根据每个类别进行加权,主视图将每个类别作为每个角落的标题。然后,文章以类似单词云的格式排列,"人造重力"将每个项目尽可能靠近其主要类别(或在其主要类别之间),不重叠。
目前,我使用的是一种效率低下的算法,它存储矩形阵列,以便在每次向视图中添加文章时执行命中测试和搜索(使用A*搜索模式来查找要填充的空白)。通过为所有重量相同的文章近似一个目的地,并使用循环队列从每个池中挑选文章,我可以获得新的结果(数组按重量排序,然后按时间戳排序),并按相关性定位("人工重力")。
然而,使用A*盲目搜索似乎真的很浪费,即使使用启发式方法让每篇文章首先检查最接近其目标标记。我需要一种更有效的方法来迭代二维空间。
我想知道链表方法是否能更好地工作;与其盲目地在所有方向上搜索空白空间,我可以遍历连接的节点,询问每个节点是否有a)附近的空闲空间,或者b)其他连接的节点(并且总是先询问最近的节点)。
如果有更好的算法可用,或者对我的方法提出批评,任何和所有的帮助都将不胜感激。
我在这个gui中使用gwt-elemental+java,但任何语言中的任何2D映射算法都肯定会有所帮助。
[EDIT(要求更多详细信息)]:这里的主要问题是每个新添加执行的工作量;它会在ui线程中产生明显的小故障,尤其是在几乎没有空间的情况下,因为我正在给定半径内的许多点上搜索足够的可用空间来放置文章。
如果我过早地切断算法,我会得到本可以填补的空白。如果我让它运行太久,ui就会出现非常严重的故障,我相信用户会讨厌它
存储和修改二维空间集合的最快/最有效的方法是什么?
您没有提供足够的信息来说明什么能让算法"更好"。更快?生成的布局在某种质量指标上"更好"?能够处理更大的数据源吗?
数组当然没有错,A*也没有错。如果他们在你试图解决的问题的规模上给出了可接受的结果,那么他们怎么会"浪费"呢?只有当链接的数据结构降低了经常需要的操作成本时,它们才是值得的。
如果你把问题尖锐化,你更有可能得到有用的答案。
无论如何,有大量关于"图形布局"one_answers"图形绘制"的文献。试着搜索这些术语。如果可以将所需布局表示为节点和边的集合,则这些可能适用。许多都是基于模拟弹簧系统,这似乎与您正在做的类似。