Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Remove consecutive points in linear path string if they have zero length or direction does not change #2006

Open
Windowsfreak opened this issue May 14, 2024 · 1 comment

Comments

@Windowsfreak
Copy link

Problem statement:

A path M2 2h2h3v1v3h-2v-1l-1-1l-2-2 could be simplified to M2 2h5v4h-2v-1l-3-3.

If you compare these paths, the same shape as above can be represented with less points, thus saving precious bytes:
image image
Technically, the last step could be replaced with a z, but this goes beyond the scope of this optimisation.

In a nutshell:

  • Add each path to the output stack
  • Compare the direction of the last two entries, e.g. by calculating atan2 of l-1-1 and l-2-2
  • If the direction matches, compare the paths
  • Also remove zero-length segments, e.g. l-1-1h0l-2-2 to l-3-3

Example Python code:

This example code parses a path of Saxony, Germany which contains segments such as: l -1 -1 -2 -2 which could be simplified to l -3 -3 or h3 0 2 which could be simplified to h5 as well as combinations of these. It analyses the segments and combines them. It converts all h and v segments into l and only supports relative coordinates with the exception of mMzZ, which are just passed through. Thus it also doesn't support curves, sorry! Optimising the output back into h and v shorthands, changing precision etc. could be done with the already existing optimisation steps of SVGOMG.

import re
import math

def parse_path(path):
    # Regular expression to match SVG path commands and their parameters
    path_re = re.compile(r'([mlhvz])|(-?\d*\.?\d+(?:e[-+]?\d+)?)', re.IGNORECASE)
    tokens = path_re.findall(path)
    commands = []
    current_command = None

    for token in tokens:
        if token[0]:
            if current_command:
                commands.append(current_command)
            current_command = [token[0]]
        else:
            current_command.append(float(token[1]))
    
    if current_command:
        commands.append(current_command)
    
    return commands

def expand_chained_commands(commands):
    expanded_commands = []
    for command in commands:
        if command[0] in 'hv':
            for i in range(1, len(command)):
                if command[0] == 'h':
                    expanded_commands.append(['l', command[i], 0])
                else:
                    expanded_commands.append(['l', 0, command[i]])
        elif command[0] == 'l':
            for i in range(1, len(command), 2):
                expanded_commands.append(['l', command[i], command[i+1]])
        else:
            expanded_commands.append(command)
    return expanded_commands

def combine_segments(commands):
    combined_commands = []
    stack = []

    def direction(x, y):
        return math.atan2(y, x)

    for command in commands:
        if command[0] == 'l':
            if command[1] == 0 and command[2] == 0:
                continue

            if stack and stack[-1][0] == 'l':
                last_command = stack.pop()
                if direction(last_command[1], last_command[2]) == direction(command[1], command[2]):
                    command = ['l', last_command[1] + command[1], last_command[2] + command[2]]
                else:
                    stack.append(last_command)
            stack.append(command)
        else:
            if stack:
                combined_commands.extend(stack)
                stack = []
            combined_commands.append(command)

    if stack:
        combined_commands.extend(stack)

    return combined_commands

def format_path(commands):
    path_str = ''
    for command in commands:
        path_str += command[0]
        for param in command[1:]:
            path_str += '%.2f ' % param
    return path_str.strip()

def optimize_path(path):
    commands = parse_path(path)
    expanded_commands = expand_chained_commands(commands)
    combined_commands = combine_segments(expanded_commands)
    return format_path(combined_commands)

# Example usage
path = "M621 618h0v-1l-2-1h-2 0l-3-2h-1v-3h0v-1h0l-2-1-1-2h0v-1h-3l-1-1h1v-1h1l1-1h0v-1h0l1-1h0v-2h0l-1-1h0-1v-1h1v-1l1-1 2-2 1-1h0v-1h2l1 1h0v1h2v-1l2-3h2v1h1l1-1h1v-1l1-1v-2l1-2v-1h6l2-2 1-1h0l1-3h0-2 0-1 0v-1h0l-1-1v-1h0l1-1h0l-1-1h0-1 0-1 0v-1l1-1v-1h2v-1l1-1h0v-1h-2v-2l5-2h1l1-2h5l1-2 2-2 2-1h1v-1h7v1h0l1-1 1-1h0l1-1h0v-1l-1-3-2-3-2-1h-1l-1-1-1-1-1-2-2-3h0l-1-4-11-3h-8v-1h0l-1-1v-1h0v-1l-1-1-1-1v-3l-1-1h-1v-1h0l1-1h0v-1h0v-5l-2-2v-3h0v-1h0v-1h0l1-2h1l1-1h0v-1h0v-4h-1v-6h0l-1-1h0v-2h0l1-1h1v-1h0v-1h1v-7l2-1v-1h0l1-1h0v-1h1v1h1l3 1v-1l4-1 5-1h1v-1h0v-2l1-1h0l6 1h1l7-1h0v1h1l1-1 1-1v-1l1-1 1-1 3 1 2 1 1-1 4-3 1-1h2l1 1 1 1h1l1 1h1l1 2 1-1h3l1 2h2l2 3 1 1h1l1-1h0v1h1l1 1h0v2h0v1h0l1 1 1 1v1h1v4h0l-1 1h0v1h0v6h0l-1 1h0-1v1h1v1h0v1h0l1-1h1l1-1h1l1 2h2l6-3h1l1-1h2l3 1 1 1 1 1 1 1h1l1 2 1 1 1-1h1l4 2h11l7-1h8l1-2 4-6 1-3v-1h0l1-1 2-4 1-1 3-2 5-1 3 1 3 1 2 1h3l10-5 3-1h3l2 1 3 2h3v1l2 2 5 1 1 1 2 1 3 1 2 1 1 1 2 2v11h0l1 2v1l1 2 2 2 1 2v4h0l-1 3-1 3-1 3v5h0l-1 1v4l-1 1-3 9-4 8-2 3-1 2v2l-1 3-1 1v1h-1l-1 1h-2l-2-1-3-2-1-1h-3v-3l2-3v-3h-1l-4 2-1-1v-1l1-2 1-1v-3l-1-1-1-1-1-1-2-1h-1v-1l-1-1h0-1 0-3 0l-1 1h-3v-1l-1-1h0l-3-1h-2l-1 1-1 1-1 4-1 1h1l2 1h2l-1 1v1l2 2 3 1 2 1-1 3h0l-2 2-6-1-2 1h0-1l-2 2v1h0l-9 4-1 1-2 1h-1l-3-1-1 1h-1l-1 1v1h-3 0l-1 1v3h0v1h0-1 0l-2 1v1h-7l-2 1h-8 0-1l-3 1-2 1h-1l1 2v2h0l-1 1h0l-1 1v1h0v1h0-1l-1 2h-1l-1 1-1 1-2-1v-1l-1-2h0-1 0-1 0v1h-1l-1 1h0l-1 1h0l-1 2v1h-3l-1-1h-1 0l-3 6-1 2v1l-2 1-3-1-2 1h-2 0-2 0-2v7h0-1 0v1h0v1h0-1 0l-1 1h-1 0-2l-7-4h-1 0-1v1h-4l-1 1h0l-1 1-1 1v1h0-1l-1 1-4-1h-5l-3 1-1 1-1 1h0l-1 1v1h0v1h0v1h0-1 0l-1 1h0l-2 1h0-1v1l-2 3v1h-1v1h-1l-1 1v2h0l-1 2-1 1v3l1 1v1h0l-1 1h-1l-1-1-1-3v-2h-1v-1l-1-1h0v-1h0l1-1h0l-1-1h0-3l-1-1v-3l-1-1-1-1h-4z"
print optimize_path(path)
@KTibow
Copy link
Contributor

KTibow commented May 19, 2024

We already join consecutive h or v.
We already remove 0-length commands when applicable.
We already replace closing lines with z when applicable.
I'm not sure how you missed out on those - maybe SVGOMG is that out of date.

The only thing we don't do is join l when the slope is the same.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants