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