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

  • 1
    Have you considered some kind of sorting? How do you know $O(n)$ is possible? – Apass.Jack Nov 30 at 2:31
  1. 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.

  • 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 at 1:01
  • I understood from the question that that was what you're doing. – Peter Taylor Dec 1 at 8:07

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.