What I Did on my
Summer Vacation

Ned Batchelder
@nedbat

https://bit.ly/bospyvaca

Blah blah blah.

What am I talking about?

Software is hard

We're all in this together

Agenda

My Vacation

Matching Points

Ideal

    Pt = namedtuple("Pt", "x, y")
    zigzags = [
        [Pt(10, 20), Pt(15, 21), Pt(20, 25)],
        [Pt(20, 25), Pt(30, 15), Pt(27, 25), Pt(23, 21)],
    ]
    
    zz_by_ends = {
        Pt(10, 20): [ 
            [Pt(10, 20), Pt(15, 21), Pt(20, 25)],
        ],
        Pt(20, 25): [
            [Pt(10, 20), Pt(15, 21), Pt(20, 25)],
            [Pt(20, 25), Pt(30, 15), Pt(27, 25), Pt(23, 21)],
        ],
        Pt(23, 21): [
            [Pt(20, 25), Pt(30, 15), Pt(27, 25), Pt(23, 21)],
        ],
    }
    

Concept: Dicts

    >>> d = {}
    >>> d['hi'] = 'hello'
    >>> d['bye'] = 'goodbye'
    >>> d['hi']
    'hello'
    

Non-string keys

    >>> d = {}
    >>> d[17] = 23
    >>> d[17]
    23

    >>> d[(1, 2)] = 'a point'
    >>> d[(1, 2)]
    'a point'
    >>> d[(1.0, 2.0)]
    'a point'

    >>> d[Pt(10, 20)] = 'another point'
    >>> d[Pt(10, 20)]
    'another point'
    

BUT: Same point, different values

    zigzags = [
        [Pt(10, 20), Pt(15, 21), Pt(20, 25)],
        [Pt(20, 25), Pt(30, 15), Pt(27, 25), Pt(23, 21)],
        [Pt(10, 20.00001), Pt(15, 40)],     # !!!   :(
        ...
    ]
    
    >>> d[Pt(10, 20)] = "hey there"
    >>> d[Pt(10, 20.00001)]
    KeyError: Pt(10, 20.00001)
    
    >>> Pt(10, 20) == Pt(10, 20.00001)
    False
    >>> 20 == 20.00001
    False
    

Concept: Floats

    >>> 0.1 + 0.2 == 0.3
    False
    

Concept: Special methods

Fuzzy equality

    class Pt(namedtuple("Pt", "x, y")):

        def __eq__(self, other):
            x1, y1 = self
            x2, y2 = other
            return (
                math.isclose(x1, x2) and
                math.isclose(y1, y2)
            )
    

Concept: Hashing

Fuzzy equality

    class Pt(namedtuple("Pt", "x, y")):

        def __eq__(self, other):
            x1, y1 = self
            x2, y2 = other
            return (
                math.isclose(x1, x2) and
                math.isclose(y1, y2)
            )
    
        def __hash__(self):
            #  ¯\_(ツ)_/¯
    

Linear search

    zz_by_ends = [
        (Pt(10, 20),  [..zigzags..] ),
        (Pt(20, 25),  [..zigzags..] ),
        (Pt(23, 21),  [..zigzags..] ),
    ]
    
    def find_zigzags(p):
        for pt, zigzags in zz_by_ends:
            if p == pt:     # fuzzy!
                return zigzags
    

Dict-like

    class PointDict:
        def __init__(self):
            # A list of (pt, value) tuples.
            self.items = []

        # pd[pt]  ≡  pd.__getitem__(pt)
        def __getitem__(self, pt):
            for key, value in self.items:
                if key == pt:           # fuzzy!
                    return value

            # Didn't find it: make a new list value and add
            # it to the end.
            value = []
            self.items.append((pt, value))
            return value
    

Advice: abstraction

    pd = PointDict()
    pd[pt1].append(zz1)
    print(pd[pt1])
    

Algorithmic Complexity

Huh?

Figuring out big-O

Linear search: O(N)

    def __getitem__(self, pt):
        for key, value in self.items:       # N/2 + N/2
            if key == pt:                   # N/2
                return value                # 1
    

Ideal: O(1)

The real problem: O(N²)

    pd = PointDict()    # Actually, slow linear search!
    for zz in all_zigzags:
        others = pd[zz[0]]
    

Python time complexities

Lists
mylist.append(val) O(1)
mylist[i] O(1)
val in mylist O(N)
for val in mylist: O(N)
Dicts
mydict[key] = val O(1)
mydict[key] O(1)
key in mydict O(1)
for key in mydict: O(N)
Sets
myset.add(val) O(1)
val in myset O(1)
for val in myset: O(N)

Be reasonable

Faster Point Matching

Next idea: rounding

    class Pt(namedtuple("Pt", "x, y")):

        def rounded(self):
            return (round(self.x), round(self.y))

        def __eq__(self, other):
            return self.rounded() == other.rounded()

        def __hash__(self):
            return hash(self.rounded())
    
    # BUT!
    >>> Pt(11.4999999, 0) == Pt(11.5000001, 0)
    False
    # Because (11.0, 0) != (12.0, 0)
    

Round two ways!

    def rounded(pt, jitter):
        return round(pt.x + jitter), round(pt.y + jitter)

    def pt_equal(p1, p2):
        return (
            rounded(p1, 0) == rounded(p2, 0) or
            rounded(p1, 0.5) == rounded(p2, 0.5)
        )
    
    >>> pt_equal(Pt(10.9999999, 0), Pt(11.0000001, 0))
    True
    >>> pt_equal(Pt(11.4999999, 0), Pt(11.5000001, 0))
    True
    
    class PointDict:
        """Like defaultdict(list), with fuzzy Pt's as keys."""
        def __init__(self):
            self.items = {}     # pt -> value
            self.rounds = {}    # pt -> pt

        def __getitem__(self, pt):      # O(1)
            val = self.items.get(pt)
            if val is not None:
                return val

            for jitter in [0, 0.5]:
                pt_rnd = rounded(pt, jitter)
                pt0 = self.rounds.get(pt_rnd)
                if pt0 is not None:
                    return self.items[pt0]

            # Not found: make an empty list value
            self.items[pt] = val = []
            for jitter in [0, 0.5]:
                pt_rnd = rounded(pt, jitter)
                self.rounds[pt_rnd] = pt

            return val
    

Results

~2100 points

slow: 20 sec

fast: 0.4 sec!

Slow

                def __init__(self):
                    self.items = []

                def __getitem__(self, pt):
                    for key, value in self.items:
                        if key == pt:
                            return value

                    value = []
                    self.items.append((pt, value))
                    return value
            

  O(1)

  O(n)

                def __init__(self):
                    self.items = []

                def __getitem__(self, pt):
                    for key, value in self.items:
                        if key == pt:
                            return value

                    value = []
                    self.items.append((pt, value))
                    return value
            

Fast

                def __init__(self):
                    self.items = {}     # pt -> value
                    self.rounds = {}    # pt -> pt

                def __getitem__(self, pt):
                    val = self.items.get(pt)
                    if val is not None:
                        return val

                    for jitter in [0, 0.5]:
                        pt_rnd = rounded(pt, jitter)
                        pt0 = self.rounds.get(pt_rnd)
                        if pt0 is not None:
                            return self.items[pt0]

                    self.items[pt] = val = []
                    for jitter in [0, 0.5]:
                        pt_rnd = rounded(pt, jitter)
                        self.rounds[pt_rnd] = pt

                    return val
            
                def __init__(self):
                    self.items = {}     # pt -> value
                    self.rounds = {}    # pt -> pt

                def __getitem__(self, pt):
                    val = self.items.get(pt)
                    if val is not None:
                        return val

                    for jitter in [0, 0.5]:
                        pt_rnd = rounded(pt, jitter)
                        pt0 = self.rounds.get(pt_rnd)
                        if pt0 is not None:
                            return self.items[pt0]

                    self.items[pt] = val = []
                    for jitter in [0, 0.5]:
                        pt_rnd = rounded(pt, jitter)
                        self.rounds[pt_rnd] = pt

                    return val
            

Algorithms!

Abstraction

One Thing

Doing less

    class Defuzzer:
        def defuzz(self, pt):
            """Return pt, or a previous equal point."""
    
    >>> defuzz = Defuzzer().defuzz
    >>> defuzz(Pt(1, 2))
    Pt(1, 2)
    >>> defuzz(Pt(3, 4))
    Pt(3, 4)
    >>> defuzz(Pt(1.01, 2))
    Pt(1, 2)
    
    def defuzz_path(path):
        return [defuzz(pt) for pt in path]

    def defuzz_paths(paths):
        return [defuzz_path(path) for path in paths]
    
    def combine_paths(paths):
        paths = defuzz_paths(paths)
        paths_by_ends = defaultdict(list)
        for path in paths:
            paths_by_ends[path[0]].append(path)
            paths_by_ends[path[-1]].append(path)

        for path in paths:
            others = paths_by_ends[path[0]]
            etc()
    

Tip: Be flexible

Representation

Paths

Classes

    class Path:
        def __init__(self, points):
            self.points = points

        def length(self): ...

        def canonicalize(self): ...

        def offset(self, offset): ...
    

Open/closed paths

Collection of Paths

    def paths_length(paths):
        return sum(p.length() for p in paths)

    def defuzz_paths(paths):
        return [p.defuzz() for p in paths]
    

Evolution

namedtuple


    >>> from collections import namedtuple
    >>> Pt = namedtuple("Pt", "x, y")   # Like "class Pt:"
    >>> p = Pt(10, 20)
    >>> p
    Pt(x=10, y=20)
    >>> p.x
    10
    >>> x, y = p                # Unpacking the tuple
    >>> x
    10


    

    >>> p.x = 17
    Traceback (most recent call last):
      File "<console>", line 1, in <module>
    AttributeError: can't set attribute


    

Problems with namedtuple

attrs


    >>> import attr
    >>> @attr.s
    ... class Pt(object):
    ...     x = attr.ib()
    ...     y = attr.ib()
    ... 
    >>> p = Pt(10, 20)
    >>> p
    Pt(x=10, y=20)


    

Clash of the classes

Finding Meaning

Other People's Code

2D transformations

Line intersections

    def segment_intersections(segments):
        isects = defaultdict(list)

        for seg1 in segments:
            for seg2 in segments:
                if seg1 is seg2:
                    continue

                isect_pt = seg1.intersect(seg2)
                if isect_pt is not None:
                    isects[isect_pt].extend([seg1, seg2])

        return isects
    

Better algorithm

But: ouch!

  File ".../poly_point_isect.py", line 576, in isect_segments_impl
    sweep_line.handle(p, events_current)
  File ".../poly_point_isect.py", line 384, in handle
    self.handle_event(e)
  File ".../poly_point_isect.py", line 408, in handle_event
    self.remove(event)
 File ".../poly_point_isect.py", line 346, in remove
    assert(event.in_sweep == False)
AssertionError
    

The horror!

    def intersections():
        for angle in [x/6 for x in range(60)]:
            rotate_everything(angle)

            try:
                isects = isect_segments()
            except AssertionError:
                print(f"Failed at rotation {angle}")
                continue

            rotate_everything(-angle)
            return isects
    

¯\_(ツ)_/¯

Failed at rotation 0.0
Failed at rotation 0.1666666666
Failed at rotation 0.3333333333
Failed at rotation 0.5
Failed at rotation 0.6666666666
Failed at rotation 0.8333333334
Failed at rotation 1.0
Failed at rotation 1.1666666667
1728 intersections
    

Buy vs Build

Tooling

Write "libraries"

    def all_pairs(seq):
        """Produce all pairs from seq, but not (a, a)"""
        return itertools.combinations(seq, 2)
    

Write code to help you debug

First rule of debugging

    """Strappiness for Zellij."""

    import collections
    import itertools
    import random

    from zellij.debug import should_debug
    from zellij.drawing import Drawing, DrawingSequence
    from zellij.euclid import Point, Segment
    from zellij.intersection import segment_intersections
    from zellij.path_tiler import join_paths, offset_path, path_segments, trim_path


    class Xing:
        def __init__(self, under=None, over=None):
            self.under = under
            self.over = over
            self.over_piece = None

        def __repr__(self):
            return f"<Xing under={show_path(self.under)} over={show_path(self.over)}>"

    class Strap:
        def __init__(self, path, width, random_factor=0):
            self.path = path
            if random_factor:
                width *= (1 + random.random() * random_factor)
            self.sides = [offset_path(path, d) for d in [width/2, -width/2]]

        def __repr__(self):
            return f"<Strap path={self.path}>"


    def path_pieces(path, segs_to_points):
        """Produce a new series of paths, split at intersection points.

        Yields a series of pieces (paths).  The pieces trace the same line as the
        original path.  The endpoints of the pieces are all intersection points
        in `segs_to_points`, or the endpoints of the original path, if it isn't
        circular.  The pieces are in order along `path`, so consecutive pieces
        end and begin at the same point. If `path` is closed, then the first piece
        returned will begin at the first cut, not at the path's first point.

        """
        # If path is circular, then the first piece we collect has to be added to
        # the last piece, so save it for later.
        collecting_head = (path[0] == path[-1])
        head = None

        piece = []
        for pt in path:
            if not piece:
                piece.append(pt)
            else:
                seg = Segment(piece[-1], pt)
                cuts = segs_to_points.get(seg)
                if cuts is not None:
                    cuts = seg.sort_along(cuts)
                    for cut in cuts:
                        ptcut = Point(*cut)
                        piece.append(ptcut)
                        if collecting_head:
                            head = piece
                            collecting_head = False
                        else:
                            yield piece
                        piece = [ptcut]
                piece.append(pt)

        if head:
            piece = join_paths(piece, head)
        yield piece


    def pieces_under_over(path, segs_to_points, xings):
        """Produce all the pieces of the path, with a bool indicating if each leads to under
        pieces = list(path_pieces(path, segs_to_points))
        for i, piece in enumerate(pieces):
            xing = xings.get(piece[-1])
            if xing is None:
                continue
            if xing.under == path:
                over = False
            elif xing.over == path:
                over = True
            elif xing.under is not None:
                over = True
            else:
                assert xing.over is not None
                over = False
            ou = [over, not over]
            if i % 2:
                ou = ou[::-1]
            break
        else:
            ou = [True, False]

        yield from zip(pieces, itertools.cycle(ou))


    
    def strapify(paths, **strap_kwargs):
        """Turn paths intro straps."""

        paths = [tuple(path) for path in paths]

        segments = []
        segs_to_paths = {}
        for path in paths:
            for segment in path_segments(path):
                segments.append(segment)
                segs_to_paths[segment] = path

        points_to_segments = segment_intersections(segments)
        isect_points = list(points_to_segments.keys())

        segs_to_points = collections.defaultdict(list)
        for pt, segs in points_to_segments.items():
            for seg in segs:
                segs_to_points[seg].append(pt)

        points_to_paths = collections.defaultdict(list)
        for isect, segs in points_to_segments.items():
            for seg in segs:
                points_to_paths[isect].append(segs_to_paths[seg])

        print(f"{len(isect_points)} intersections")
    
        if 0:
            debug_output(dwgw=DWGW, paths=paths, segments=segments, isects=isect_points)
    
        debug = should_debug("strapify")
        if debug:
            dbgdwgs = iter(DrawingSequence(name="debugs_", paths=paths))

        paths_to_do = set(paths)
        paths_done = set()
        xings = {}      # pt -> xing
        straps = []     # new smaller paths, ending at unders.
        path = None
        while paths_to_do:
            next_paths = set()
            next_paths.add(paths_to_do.pop())
            while next_paths:
                previous_path = path
                path = next_paths.pop()

                if debug:
                    dwg = next(dbgdwgs)
                    dwg.draw_segments(segments, rgb=(0, 0, 0), width=1)
                    dwg.draw_paths(paths_done, rgb=(0, 0, 0), width=3)
                    dwg.draw_paths(next_paths, rgb=(.7, .7, 0), width=9)
                    if previous_path:
                        dwg.draw_path(previous_path, rgb=(1, 0, 0), width=10, dash=[30, 30])
                    dwg.draw_path(path, rgb=(1, 0, 0), width=15)
                    dwg.fill_points([path[0]], rgb=(1, 0, 0), radius=15*3/2)
                    dwg.fill_points([path[1]], rgb=(1, 0, 0), radius=15*2/2)
                    partial_over = [pt for pt, xing in xings.items() if xing.under is None]
                    partial_under = [pt for pt, xing in xings.items() if xing.over is None]
                    dwg.circle_points(partial_over, rgb=(.8, 0, 0), radius=21, width=9)
                    dwg.circle_points(partial_under, rgb=(0, 0, .8), radius=21, width=9)
                    done = [pt for pt, xing in xings.items() if xing.under is not None and x
                    dwg.circle_points(done, rgb=(0, .8, 0), radius=15, width=3)

                prev_piece = None
                last_cut = None
                first_piece = True
                for piece, over in pieces_under_over(path, segs_to_points, xings):
                    if first_piece and debug:
                        dwg.cross_points([piece[0], piece[-1]], radius=20, rgb=(1, 0, 0), wi
                        dwg.finish()
                        if 0 and dwg.num > 10:
                            print()
                            import sys; sys.exit()
                        first_piece = False

                    cut = None
                    if over:
                        assert prev_piece is None
                        prev_piece = piece
                        if last_cut:
                            cut = last_cut
                            xing = xings.get(cut)
                            if xing is None:
                                xing = Xing(under=path)
                                xings[cut] = xing
                            else:
                                assert xing.under is None or xing.under == path
                                xing.under = path
                            last_cut = None
                    else:
                        if prev_piece:
                            cut = prev_piece[-1]
                            assert cut == piece[0]
                            strap = Strap(join_paths(prev_piece, piece), **strap_kwargs)
                            straps.append(strap)
                            xing = xings.get(cut)
                            if xing is None:
                                xing = Xing(over=path)
                                xings[cut] = xing
                            else:
    
                                assert xing.over is None or xing.over == path
                                xing.over = path
                            xing.over_piece = strap
                        else:
                            straps.append(Strap(piece, **strap_kwargs))
                        last_cut = piece[-1]
                        prev_piece = None
                    if cut:
                        for next_path in points_to_paths[cut]:
                            if next_path in paths_to_do:
                                paths_to_do.remove(next_path)
                                next_paths.add(next_path)
                if prev_piece:
                    strap = Strap(prev_piece, **strap_kwargs)
                    straps.append(strap)
                    closed = (path[0] == path[-1])
                    if closed:
                        cut = prev_piece[-1]
                        xing = xings.get(cut)
                        if xing is None:
                            xing = Xing(over=path)
                            xings[cut] = xing
                        else:
                            xing.over = path
                        xing.over_piece = strap

                paths_done.add(path)
                if debug:
                    dwg.cross_points([piece[0], piece[-1]], radius=30, rotate=30, rgb=(0, 0,
                    dwg.finish()
                    if 0 and dwg.num > 10:
                        print()
                        import sys; sys.exit()
    
        if 0:
            bad = [pt for pt, xing in xings.items() if xing.over_piece is None]
            debug_output(dwgw=DWGW, paths=paths, segments=segments, isects=bad)
    
        if debug:
            for strap in straps:
                dwg = next(dbgdwgs)
                dwg.draw_segments(segments, rgb=(0, 0, 0), width=1)
                dwg.draw_path(strap.path, rgb=(1, 0, 0), width=3)
                for s in strap.sides:
                    dwg.draw_path(s, rgb=(0, 0, 1), width=1)
                dwg.finish()

        for strap in straps:
            for end in [0, -1]:
                xing = xings.get(strap.path[end])
                if xing is not None:
                    trimmers = xing.over_piece.sides
                    strap.sides = [trim_path(s, end, trimmers) for s in strap.sides]

        return straps


    def debug_output(dwgw=None, paths=None, segments=None, isects=None):
        dwg = Drawing(paths=paths, name="debug.png")
        dwg.draw_segments(segments, rgb=(0, 0, 0), width=1)
    
        dup_segments = []
        segments.sort()
        for s1, s2 in zip(segments, segments[1:]):
            if s1 == s2:
                dup_segments.append(s1)
    
        dwg.draw_segments(dup_segments, rgb=(1, 0, 0), width=7)
    
        if dwgw is not None:
            with dwg.style(rgb=(0, 0, 1), width=2, dash=[5, 5]):
                dwg.rectangle(0, 0, dwgw, dwgw)
                dwg.stroke()
    
        if isects is not None:
            dwg.circle_points(isects, radius=9, rgb=(0, .5, 0), width=3)
    
        dwg.finish()
    

Wrapping Up

Advice

The End