加快边缘选择的几点建议

Question

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

我所拥有的：一个节点类，具有x，y，连通节点列表和F，G和H分数。一个边缘类，具有开始、完成以及它是否被指向。一个图类，它包含节点和边的列表以及A*算法

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

Answer 1

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

您可以很容易地将一个经典的QuadTree扩展到一种PMR QuadTree中，它根据穿越它们的线段的数量添加分裂准则。我已经编写了一个混合PR/PMR QuadTree，它支持点和线的存储，实际上它对10-50k移动对象(再平衡桶！)具有足够高的性能。

Answer 2

所以你的问题是，这个人已经画出了一组节点和边缘，你想要进行测试，找出哪个边被点击得更快了。

边缘是线段。为了过滤到少量可能的候选边缘，将边缘扩展到直线中是没有坏处的。即使你有大量的边，只有一小部分将通过接近一个给定的点，所以迭代通过这些不会是坏的。

现在把边缘分成两组。垂直的而不是垂直的。您可以将垂直边存储在排序的数据结构中，并且很容易地测试哪些垂直线接近任何给定的点。

而非垂直的则更棘手。对于它们，您可以在可以放置节点的区域的左右方向绘制垂直边界，然后将每一行存储为直线与这些直线相交的一对高度。您可以将这些对存储在QuadTree中。您可以在这个QuadTree逻辑中添加一个点，并在QuadTree中搜索在该点一定距离内传递的所有行。(其思想是，在QuadTree中的任何一点上，您都可以为该点以下的所有行构造一对边界线。如果你的观点不是在这些线之间，或者接近它们，你可以跳过树的那个部分。)

Answer 3

我想你已经有所有的原料了。以下是一个建议：

1. 索引空间数据结构中的所有边缘(可以是QuadTree、R-树等)。每个边缘都应该使用它的边界框进行索引。
2. 记录鼠标的位置。
3. 搜索包含鼠标位置的最特定矩形。
4. 这个矩形应该有一个或多个边/节点；根据所需的模式迭代它们。
5. (棘手的部分)：如果用户没有从最特定的矩形中指定任何边缘，那么您应该上升一个级别，并在这个级别中包含的边缘上进行迭代。也许你不用这个就行了。

这应该更快。