algorithm - 一种从线段中找到折线的算法

Question

问题:假设您收到一个大小为 n 的列表，其中包含二维线段。每条线段由 2 个点组成，(X1,Y1) 和 (X2,Y2)。提出一种算法和结构，将这些线组合成连续的折线(链)。注意:连续多段线仅表示实体链。想象一个包含 4 条线的正方形，它们相互连接以便在正方形周围移动。

我最初的解决方案:创建顶点类和线类。每行都有数据成员指向开始和结束顶点。然后该算法遍历每个顶点以查找是否有任何线段具有公共(public)顶点，然后将它们分组。我不确定这样做是否有效

Answer 1

单遍历您的线段列表，反引用每个顶点以指向以它为端点的每个线段。您现在有一个二分图(顶点和线段)，并且可以有效地应用已知算法来查找图中节点的闭包。每个闭包都是一条折线。