Skip to content

Instantly share code, notes, and snippets.

@Higgs1
Last active December 20, 2015 02:39
Show Gist options
  • Save Higgs1/6058245 to your computer and use it in GitHub Desktop.
Save Higgs1/6058245 to your computer and use it in GitHub Desktop.
import math
import zlib
def encode(lines):
if len(lines) == 0: return "0"
# check if 3 points are on the same line, in order
def ison(a, c, b):
within = lambda p, q, r: p <= q <= r or r <= q <= p
return ((b[0] - a[0]) * (c[1] - a[1]) == (c[0] - a[0]) * (b[1] - a[1])
and (within(a[0], c[0], b[0]) if a[0] != b[0] else
within(a[1], c[1], b[1])))
# converts series of lines to 'connect the dots', and looks for single dots
strokes = [[lines[0][0:2]]]; dots = []
for line in lines:
if line[0:2] != strokes[-1][-1]:
if len(strokes[-1]) == 1:
dots += strokes.pop()
strokes += [[line[0:2]]]
if line[2:4] != strokes[-1][-1]:
if len(strokes[-1]) > 1 and \
ison(strokes[-1][-2], strokes[-1][-1], line[2:4]):
strokes[-1][-1] = line[2:4]
else:
strokes[-1] += [line[2:4]]
if len(strokes[-1]) == 1:
dots += strokes.pop()
# big endian, most significant first
def BEVLI4Enc(num):
if num == 0: return '0' * 4
else:
temp = -(-int(math.log(num, 2) + 1) // 3) * 3
temp = [bin(num)[2:].zfill(temp)[i:i+3] for i in range(0, temp, 3)]
return '1'.join([''] + temp[:-1]) + '0' + temp[-1]
# encode dots in binary
data = ''.join(map(BEVLI4enc, [len(dots)] + [i for d in dots for i in d]))
# convert series of points to deltas, then convert to binary
directions = [bin(0x7070563)[2:][i:i+3] for i in range(0,27,3)]
for stroke in strokes:
prev_point = stroke[0]
data += ''.join(map(BEVLI4enc, (len(stroke) - 1,) + prev_point))
for point in stroke[1:]:
dx, dy = point[0] - prev_point[0], point[1] - prev_point[1]
prev_point = point
# format: bit 'is this delta more than 1 pixel?', 3xbits direction
# directions: 111 000 001
# 110 # 010
# 101 100 011
data += ('1' if abs(dx) > 1 or abs(dy) > 1 else '0') + \
directions[cmp(dx, 0) + 1 + (cmp(dy, 0) + 1) * 3]
if abs(dx): data += BEVLI4enc(abs(dx))
if abs(dy): data += BEVLI4enc(abs(dy))
# pad to byte boundry, then convert to binary
data = ''.join(map(lambda x: chr(int(x, 2)), \
[data[i:i+8].ljust(8, '0') for i in range(0,len(data),8)]))
# base 95 encoder
def b95btoa(b):
b95 = ''; n = int(('_' + b).encode('hex'), 16)
while n > 0:
b95 += chr(int(n % 95 + 32)); n /= 95
return b95[::-1]
# compress using zlib if it makes it smaller
z = zlib.compress(data)[2:-4]
if len(z) < len(data):
return 'c' + b95btoa(z)
else:
return 'e' + b95btoa(data)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment