<分区>
我有一组线条。一条线由两个点定义。 Point 具有 (x,y) 坐标。 有些线路仅在一个点上与其他线路相连。这组线定义了一张 map 。您可以在下图中看到一个示例。现在假设我想从任何线段上的一个点(不仅仅是一条线的端点)到另一条线上的另一个点。
背景:当我从一个点移动到另一个点时，我想沿途画一条线，所以最后，只会画出走过的路径。将其视为路径的热图。我会使用什么算法？有没有我可以使用的库？
<分区>
我有一组线条。一条线由两个点定义。 Point 具有 (x,y) 坐标。 有些线路仅在一个点上与其他线路相连。这组线定义了一张 map 。您可以在下图中看到一个示例。现在假设我想从任何线段上的一个点(不仅仅是一条线的端点)到另一条线上的另一个点。
背景:当我从一个点移动到另一个点时，我想沿途画一条线，所以最后，只会画出走过的路径。将其视为路径的热图。我会使用什么算法？有没有我可以使用的库？
最佳答案
将图形表示为具有 x-y 坐标的线集不适合路径查找算法，因此您应该从线段集构建适当的图形。 我想你可以使用这些公式: http://en.wikipedia.org/wiki/Distance_from_a_point_to_a_line http://en.wikipedia.org/wiki/Line-line_intersection 用于确定每个线段的相邻线段。两条线的每个交点都应转换为四或三条线，以便它们仅通过端点连接。 在构建每个节点代表一条线并且每条边代表线之间的连接的图形后，您可以使用 Dijkstra 算法来查找任何一对节点(线)之间的最短路径: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
关于c# - 适用于由线集合定义的 map 的寻路算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12939102/