关于加快选边速度的建议
我正在用 C# 构建一个图形编辑器，用户可以在其中放置节点，然后将它们与有向或无向边连接。完成后，A* 寻路算法确定两个节点之间的最佳路径。
我拥有的： 一个 Node 类，包含 x、y、连接节点列表以及 F、G 和 H 分数。 具有 Start、Finish 以及是否有向的 Edge 类。 包含节点和边列表以及 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.
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?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
由于用户正在“绘制”这些图表，我假设它们包含人类可能能够生成的许多节点和边（例如最多 1-5k？）。只需将两者存储在同一个四叉树中（假设您已经编写了一个四叉树）。
您可以轻松地将经典四叉树扩展为PMR四叉树，其中添加了分割条件基于穿过它们的线段的数量。我编写了一个混合 PR/PMR QuadTree，它支持对点和线进行存储，并且在事实上，它对于 10-50k 移动物体（重新平衡桶！）具有足够高的性能。
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).
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!).
所以你的问题是，这个人已经绘制了一组节点和边，并且你想进行测试以更快地找出哪条边被单击。
边是一条线段。为了过滤到少量可能的候选边缘，将边缘延伸成线没有坏处。即使您有大量边，也只有少量边会接近给定点，因此迭代这些边也不会很糟糕。
现在将边分为两组。垂直的，也不是垂直的。您可以将垂直边存储在排序的数据结构中，并轻松测试哪些垂直线靠近任何给定点。
非垂直的则更棘手。对于它们，您可以在可以放置节点的区域的左侧和右侧绘制垂直边界，然后将每条线存储为该线与这些线相交的一对高度。您可以将这些对存储在四叉树中。您可以添加到此四叉树逻辑，以便能够获取一个点，并在四叉树中搜索经过该点一定距离内的所有线。 （这个想法是，在四叉树中的任何点，您都可以为该点下方的所有线构造一对边界线。如果您的点不在这些线之间或靠近它们，则可以跳过树的该部分.)
So your problem is that the person has already drawn a set of nodes and edges, and you'd like to make the test to figure out which edge was clicked on much faster.
Well an edge is a line segment. For the purpose of filtering down to a small number of possible candidate edges, there is no harm in extending edges into lines. Even if you have a large number of edges, only a small number will pass close to a given point so iterating through those won't be bad.
Now divide edges into two groups. Vertical, and not vertical. You can store the vertical edges in a sorted datastructure and easily test which vertical lines are close to any given point.
The not vertical ones are more tricky. For them you can draw vertical boundaries to the left and right of the region where your nodes can be placed, and then store each line as the pair of heights at which the line intersects those lines. And you can store those pairs in a QuadTree. You can add to this QuadTree logic to be able to take a point, and search through the QuadTree for all lines passing within a certain distance of that point. (The idea is that at any point in the QuadTree you can construct a pair of bounding lines for all of the lines below that point. If your point is not between those lines, or close to them, you can skip that section of the tree.)
我想你已经准备好了所有的原料。
这里有一个建议：
这应该会更快。
I think you have all the ingredients already.
Here's a suggestion:
This should be faster.