1

我追求一种高效的 2D 映射算法,并且我尝试了许多实现,但它们似乎都缺乏。我希望 stackoverflow 世界可以提供一些指向我可以从中学习的现有、久经考验的算法的指针。

我的目标是根据写作体裁展示文章;对于原型,我使用哲学、编程、政治和诗歌,因为这是我仅有的四种写作风格。

每篇文章根据每个类别进行加权,首页视图将每个类别作为每个角落的标题。然后文章以类似词云的格式排列,“人工重力”将每个项目尽可能靠近其主要类别(或在其主要类别之间),而不重叠。

目前,我正在使用一种效率低下的算法,该算法存储矩形数组以在每次将文章添加到视图时执行命中测试和搜索(使用 A* 搜索模式来查找要填充的空白空间)。通过为所有具有相同权重的文章近似单个目的地,并通过使用循环队列从每个池中挑选文章,我可以获得新的结果(数组按权重排序,然后是时间戳),定位相关性(“人为重力”)。

然而,使用 A* 进行盲目搜索似乎真的很浪费,即使使用启发式方法让每篇文章首先检查最接近它的目标标记。我需要一种更有效的方法来迭代 2D 空间。

我想知道链接列表方法是否会更好。而不是盲目地在各个方向搜索空白空间,我可以遍历连接的节点来询问每个节点是否有a)附近的可用空间,或者b)其他连接的节点要询问(并且总是首先询问最近的节点) .

如果有任何更好的算法可用,或对我的方法的批评,任何和所有的帮助肯定会受到赞赏。

我在这个 gui 中使用 gwt elemental + java,但是任何语言的任何 2D 映射算法肯定会有所帮助。

[EDIT (request for more details)]:这里的主要问题是每个新添加的工作量;它会在 ui 线程中产生明显的故障,尤其是在几乎没有剩余空间的情况下,因为我正在给定半径内搜索许多点以获得足够的可用空间来容纳文章。

如果我过早切断算法,我会得到本来可以填补的空白点。如果我让它运行太久,用户界面会出现非常糟糕的故障,我相信用户会讨厌它。

存储和修改 2D 空间集合的最快/最有效方法是什么?

4

1 回答 1

0

您没有提供足够的信息来说明什么会使算法“更好”。快点?根据某些质量指标生成“更好”的布局?能够处理更大的数据源?

数组当然没有错,A* 也没有。如果他们给出的结果与你试图解决的问题的规模一样大,那么他们怎么能“浪费”呢?链接数据结构只有在减少经常需要的操作的成本时才有价值。

如果你把问题变得尖锐,你更有可能得到一个有用的答案。

无论如何,有大量关于“图形布局”和“图形绘制”的文献。尝试搜索这些术语。如果您可以将所需的布局表示为节点和边的集合,则这些可能适用。许多都基于模拟弹簧系统,这似乎类似于您正在做的事情。

于 2012-09-14T01:00:30.493 回答