algorithm - 关于加速选边的建议

Question

我正在用 C# 构建一个图形编辑器，用户可以在其中放置节点，然后将它们与有向或无向边连接起来。完成后，A* 寻路算法确定两个节点之间的最佳路径。

我有什么:具有 x、y、连接节点列表以及 F、G 和 H 分数的节点类。具有开始、结束以及是否定向的边缘类。包含节点和边列表以及 A* 算法的图形类

现在，当用户想要选择一个节点或一条边时，鼠标位置会被记录下来，我会遍历每个节点和边来确定是否应该选择它。这显然很慢。我在想我可以为我的节点实现一个四叉树来加速它，但是我可以做些什么来加速边缘选择？

Answer 1

由于用户正在“绘制”这些图表，因此我假设它们包含人类可能能够生成的许多节点和边(比如最多 1-5k？)。只需将两者存储在同一个四叉树中(假设您已经编写了一个)。

您可以轻松地将经典四叉树扩展到 a PMR QuadTree它根据穿过它们的线段数量添加了分割标准。我写了一个 hybrid PR/PMR QuadTree它支持对点和线进行分桶，实际上它对 10-50k 移动对象具有足够高的性能(重新平衡分桶!)。