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,20becomes
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,10becomes
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)$.
- Start with an empty list of polylines.
- 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.
- Remove the line from the list.
- 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)$?