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

I am building a graph editor in C# where the user can place nodes and then connect them with either a directed or undirected edge. When finished, an A* pathfinding algorithm determines the best path between two nodes.

我有什么：与连接的节点和F，G和H分数的X，Y，列表的节点类。 边缘类与启动，完成，是否指向。 其中包含节点列表和边以及A *算法的图形类

What I have: A Node class with an x, y, list of connected nodes and F, G and H scores. An Edge class with a Start, Finish and whether or not it is directed. A Graph class which contains a list of Nodes and Edges as well as the A* algorithm

当一个用户想要选择的节点或边缘眼下，鼠标位置被记录，并且我遍历各节点和边，以确定它是否应该被选中。这显然​​是缓慢的。我想我可以实现一个四叉树为我的结点来加快它然而，我能做些什么来加快优势的选择？

Right now when a user wants to select a node or an edge, the mouse position gets recorded and I iterate through every node and edge to determine whether it should be selected. This is obviously slow. I was thinking I can implement a QuadTree for my nodes to speed it up however what can I do to speed up edge selection?

推荐答案

由于用户的绘图这些图我会假设它们包括多个节点和边缘，人类将有可能能够产生（比如1-5k最大？）。只要同时存储在同一个四叉树（假设你已经有一个写的）。

Since users are "drawing" these graphs I would assume they include a number of nodes and edges that humans would likely be able to generate (say 1-5k max?). Just store both in the same QuadTree (assuming you already have one written).

您可以轻松地扩展经典的四叉树成一个PMR四叉树这增加了基于线段通过他们穿越的数量分割标准。我写了一个混合PR / PMR四叉树这支持了瓢泼大雨两者的点和线，而在现实中，它具有足够高的性能就职于10-50k移动物体（再​​平衡桶！）。

You can easily extend a classic QuadTree into a PMR QuadTree which adds splitting criteria based on the number of line segments crossing through them. I've written a hybrid PR/PMR QuadTree which supported bucketing both points and lines, and in reality it worked with a high enough performance for 10-50k moving objects (rebalancing buckets!).