An algorithm to find polylines from line segments

Question

Question: Suppose you are passed a list of size n containing 2D line segments. Each line segment consists of 2 points, (X1,Y1) and (X2,Y2). Present an algorithm and structure to group these lines into continuous polylines (chains). Note: A continuous polyline simply means a chain of entities. Think of a square containing 4 lines and that they are linked in order to move around the square.

My initial solution: To create vertex class and line class. Each line has data members to point to start and end vertices. Then the algorithm goes through each and every vertex to find whether any of line segments have vertex in common and then group them. I'm not sure if it is an efficient to do that

Answer 1

Make a single pass over your list of segments, counter-referencing every vertex to point to each segment that has it as an endpoint. You now have a bipartite graph (vertices and segments) and can efficiently apply known algorithms for finding the closure of an node in the graph. Each closure is a polyline.