# Forming polylines from a list of individual lines

I want to optimize a SVG path made entirely of lines. Given a list of lines, each made of two 2D points connected together, I want to find an equivalent list of polylines. For example:

• M10,10 L20,10 M20,10 L20,20 becomes M10,10 L20,10 L20,20.
One line ends where there other begins, it can become a polyline.
• M10,10 L20,10 M20,10 L30,10 becomes M10,10 L30,10.
The second line extends the first line, they can be merged into one line.

I found a basic way to do it in $$O(n^2)$$.

2. Loop over all invidivual lines. If a point of the line is the same as one of the polylines head or tail, extend the polyline. If the slope between the new and last points is the same as the slope between the last and before last points, then only replace the last point with the new point.
3. Remove the line from the list.
4. Repeat until list is empty.

As you can guess this algorithm performs quite badly, taking forever with as little as 20,000 lines.

How to do it in $$O(n)$$?

• Have you considered some kind of sorting? How do you know $O(n)$ is possible? – John L. Nov 30 '18 at 2:31

(My emphasis). How are you doing that test? To take $$\Theta(n^2)$$ time, I think you must be testing each point by linear scan in $$\Theta(n)$$. Use a decent hashmap instead and it will take $$\Theta(1)$$ on average.
• It would effectively make it $\Theta(n)$. The problem with using hashmap is that keys must be unique, but two different polylines can have the same head and/or tail. One solution I found was to connect two polylines into a single one when a collision occurs. – Nicolas Dec 1 '18 at 1:01