Forming polylines from a list of individual lines

Question

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)$.

1. Start with an empty list of polylines.
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)$?

Answer 1

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

(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.